BFS

BFS란

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

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

BFS 특징

• 직관적이지 않다.
  - BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다
• BFS는 재귀적으로 동작하지 않는다.
• 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다.
• 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐를 사용한다.

BFS 구현

자 이번에는, BFS 를 구현해보도록 하겠습니다!
우선 DFS 와 BFS 의 차이점을 다시 곱씹어볼게요!
DFS 는 탐색하는 원소를 최대한 깊게 따라가야 합니다.
이를 구현하기 위해 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 마지막에 넣은 노드를 꺼내서 탐색하면 됩니다. → 그래서 스택을 썼죠!
BFS 는 현재 인접한 노드 먼저 방문해야 합니다.
이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 가장 처음에 넣은 노드를 꺼내서 탐색하면 됩니다.
가장 처음에 넣은 노드들..? → 큐를 이용하면 BFS 를 구현할 수 있습니다!
구현의 방법은 다음과 같습니다.
1. 루트 노드를 큐에 넣습니다.
2. 현재 큐의 노드를 빼서 visited 에 추가한다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.
4. 2부터 반복한다.
5. 큐가 비면 탐색을 종료한다.

예시를 한 번 들어보겠습니다!

# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
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]
}
visited = [] # 방문한 걸 저장하기 위한 배열
queue = [1] # 시작 노드인 1을 넣어둔다.

1. 현재 큐에서 가장 처음에 넣은 1을 빼서, visited 에 추가합니다. 
# queue -> [] visited -> [1]

2. 인접한 노드들인 [2, 3, 4] 에서 방문하지 않은 것들인 [2, 3, 4]를 queue 에 추가합니다. 
# queue -> [2, 3, 4] visited -> [1]

3. 현재 큐에서 가장 처음에 넣은 2을 빼서, visited 에 추가합니다. 
# queue -> [3, 4] visited -> [1, 2]

4. 인접한 노드들인 [1, 5] 에서 방문하지 않은 것들인 [5]를 queue 에 추가합니다. 
# queue -> [3, 4, 5] visited -> [1, 2]

5. 현재 큐에서 가장 처음에 넣은 3을 빼서, visited 에 추가합니다. 
# queue -> [4, 5] visited -> [1, 2, 3]

6. 인접한 노드들인 [1, 6, 7] 에서 방문하지 않은 것들인 [6, 7]를 queue 에 추가합니다. 
# queue -> [4, 5, 6, 7] visited -> [1, 2, 3]

7. 현재 큐에서 가장 처음에 넣은 4을 빼서, visited 에 추가합니다. 
# queue -> [5, 6, 7] visited -> [1, 2, 3, 4]

8. 인접한 노드들인 [1, 8] 에서 방문하지 않은 것들인 [8]를 queue 에 추가합니다. 
# queue -> [5, 6, 7, 8] visited -> [1, 2, 3, 4]

9. 현재 큐에서 가장 처음에 넣은 5을 빼서, visited 에 추가합니다. 
# queue -> [6, 7, 8] visited -> [1, 2, 3, 4, 5]

10. 인접한 노드들인 [2, 9] 에서 방문하지 않은 것들인 [9]를 queue 에 추가합니다. 
# queue -> [6, 7, 8, 9] visited -> [1, 2, 3, 4, 5]

11. 현재 큐에서 가장 처음에 넣은 6을 빼서, visited 에 추가합니다. 
# queue -> [7, 8, 9] visited -> [1, 2, 3, 4, 5, 6]

12. 인접한 노드들인 [3, 10] 에서 방문하지 않은 것들인 [10]를 queue 에 추가합니다. 
# queue -> [7, 8, 9, 10] visited -> [1, 2, 3, 4, 5, 6]

13. 현재 큐에서 가장 처음에 넣은 7을 빼서, visited 에 추가합니다. 
# queue -> [8, 9, 10] visited -> [1, 2, 3, 4, 5, 6, 7]

14. 인접한 노드들인 [3] 에서 방문하지 않은 것들이 없으니 추가하지 않습니다.
# queue -> [8, 9, 10] visited -> [1, 2, 3, 4, 5, 6, 7]

15. 현재 큐에서 가장 처음에 넣은 8을 빼서, visited 에 추가합니다. 
# queue -> [9, 10] visited -> [1, 2, 3, 4, 5, 6, 7, 8]

16. 인접한 노드들인 [4] 에서 방문하지 않은 것들이 없으니 추가하지 않습니다.
# queue -> [9, 10] visited -> [1, 2, 3, 4, 5, 6, 7, 8]

17. 현재 큐에서 가장 처음에 넣은 9을 빼서, visited 에 추가합니다. 
# queue -> [10] visited -> [1, 2, 3, 4, 5, 6, 7, 8, 9]

18. 인접한 노드들인 [5] 에서 방문하지 않은 것들이 없으니 추가하지 않습니다.
# queue -> [10] visited -> [1, 2, 3, 4, 5, 6, 7, 8, 9]

19. 현재 큐에서 가장 처음에 넣은 10을 빼서, visited 에 추가합니다. 
# queue -> [] visited -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

20. 인접한 노드들인 [6] 에서 방문하지 않은 것들이 없으니 추가하지 않습니다.
# queue -> [] visited -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

21. 현재 큐에서 꺼낼 것이 없습니다. BFS 가 끝났습니다.

자... 어마어마한 내용들이 있었는데요!
이 코드를 보면 어떤 순서대로 BFS 가 이루어지는 지 조금은 이해가 가실 것 같습니다.
모든 순서를 외우실 필요는 없습니다 다만! 탐색의 순서와 느낌에 대해 이해가셨으면 좋겠습니다.

1. 시작 노드를 큐에 넣습니다.
2. 현재 큐의 노드를 빼서 visited 에 추가합니다.
3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.
   이 과정을 큐가 빌때까지 반복하면 됩니다!
   현재 방문한 노드와 인접한 노드는 adjacent_node[current_node] 로 구할 수 있습니다!
   방문하지 않은 걸 확인 하기 위해서는 visited 를 이용하시면 됩니다!

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

    while queue:
        current_node = queue.pop(0)
        visited.append(current_node)
        for adjacent_node in adj_graph[current_node]:
            if adjacent_node not in visited:
                queue.append(adjacent_node)

    return visited