BFS 구현하기

BFS

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]
}


def bfs_queue(adj_graph, start_node):
    queue = [start_node]
    visited = []
    while queue:
        cur_node = queue.pop(0)
        visited.append(cur_node)
        for adj_node in adj_graph[cur_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] 이 출력되어야 합니다!

루트노드를 먼저 큐에 넣고, 이를 빼서 방문한 노드에 넣는다. 그 후 인접한 노드 중 방문하지 않은 노드를 큐에 추가한 후 큐가 빌 때까지 이 과정을 반복한다.