BFS(Breadth First Search) - 너비 우선 탐색

BFS란?

한 노드를 시작으로 인접한 모든 노드들을 우선 방문하는 방법.

더 이상 방문하지 않은 노드가 없을 때까지 방문하지 않은 모든 노드들에 대해서도 BFS를 적용한다.

 

BFS 구현 방법

1. 큐

BFS는 현재 인접한 노드들을 먼저 방문해야 한다. 

이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고

가장 처음에 넣은 노드를 꺼내서 탐색하면 된다.

-> 처음에 넣은 노드를 꺼낸다. -> 큐를 쓰면 되겠구나

 

큐를 사용한다는 점 말고는 DFS에서 스택을 사용하는 방법과 매우 유사하다.

코드로 직접 살펴보자

graph = {
    1: [2, 3, 4],
    2: [1, 5],
    3: [1, 6, 7],
    4: [1, 8],
    5: [2, 9],
    6: [3, 10],
    7: [3],
    8: [4],
    9: [5],
    10: [6]
}
# 1. 시작 노드를 큐에 넣는다.
# 2. 현재 큐의 노드를 빼서 visited에 추가
# 3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가

def bfs_queue(adj_graph, start_node):
    queue = [start_node]
    visited = []

    while queue:
        curr_node = queue.pop(0) # queue이기 때문에 앞에서부터 꺼낸다.
        visited.append(curr_node)
        for adj_node in adj_graph[curr_node]:
            if adj_node not in visited:
                queue.append(adj_node)
    return visited

print(bfs_queue(graph, 1))  # 1 이 시작노드
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력되어야함