[그래프] 너비 우선 탐색 (BFS)

BFS 소개

그래프는 노드와 간선을 이용한 비선형 데이터 구조입니다. 너비 우선 탐색(Breadth First Search)은 시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘 입니다. 여기서 거리는 시작 노드와 목표 노드까지의 차수를 말합니다. BFS 알고리즘은 루트 노드에서 가까운 노드부터 탐색하므로, 가중치가 없는 그래프에서 최단 경로를 보장합니다.

 

알고리즘 동작 방식

BFS는 주로 큐를 이용해 구현합니다.

 

일단 시작 노드를 정하고, 큐에 시작 노드를 푸시합니다.

• 시작 노드를 큐에 푸시하면서, 방문 처리를 합니다.
• 큐에 있는 노드는 이미 방문 처리했고, 그 노드와 인접한 노드는 아직 탐색하지 않은 상태입니다.

이후, 큐가 비어있는지 확인합니다.

• 큐가 비었다면, 방문할 수 있는 모든 노드를 방문했다는 뜻이기 때문에 탐색을 종료합니다.
• 큐가 비지 않았다면, 큐에서 노드를 팝하여 팝한 노드와 인접한 모든 노드를 확인하고, 그 중 아직 방문하지 않은 노드를 큐에 푸시하며 방문처리 합니다.

 

BFS 구현

  

    
    
    
    
  
from collections import deque

def bfs(start_node):
    # 방문 표시
    visited = [False for i in range(len(graph)+1)]
    visited[start_node] = True
    queue = deque([start_node])

    while queue:
        node = queue.popleft()
        print(node)
        for adj_node in graph[node]:
            # 방문하지 않았을 경우
            if not visited[adj_node]:
                queue.append(adj_node)
                visited[adj_node] = True

graph = {
    1: [4,5],
    2: [3],
    3: [],
    4: [2,3],
    5: [4]
}

bfs(1)  # 1 4 5 2 3

 

 

 

BFS 순회 구현

  

    
    
    
    
  
from collections import defaultdict, deque

adj_list = defaultdict(list)
visited = set()
result = []

def bfs(start):
    queue = deque([start])
    visited.add(start)
    result.append(start)

    while queue:
        node = queue.popleft()
        for adj_node in adj_list[node]:
            # 방문하지 않았을 경우
            if adj_node not in visited:
                queue.append(adj_node)
                visited.add(adj_node)
                result.append(adj_node)



def solution(graph, start):
    for u,v in graph:
        adj_list[u].append(v)
    bfs(start)

    return result
    


# test case 1
graph = [(1,2),(1,3),(2,4),(2,5),(3,6),(3,7),(4,8),(5,8),(6,9),(7,9)]
start = 1

# test case 2
graph = [(0,1),(1,2),(2,3),(3,4),(4,5),(5,0)]
start = 1

print(solution(graph, start))