(Python) 너비 우선 탐색(BFS) 구현하기

(Python) 너비 우선 탐색(BFS) 구현하기¶

---

In [1]:

from IPython.display import Image

Image("img/bfs_graph.png") ## code안에서 그림이 나오게 할 떄
# ![title](img/bfs_graph.png) ## markdown안에서 그림이 나오게 할 때

Out[1]:

DFS에서는 반복문(iteration), 재귀(recursive)적인 방법으로 구현했었는데
BFS의 경우 반복문(iteration)을 이용해서 구현을 해야 한다.

반복문(iteration)

• DFS : stack 이용
• DFS 방문 순서 : A B D E F C G H (왼쪽 노드부터 방문한다고 가정할때)
• BFS : queue 이용
• BFS 방문 순서 : A B C D E G H F (왼쪽 노드부터 방문한다고 가정할때)

---

In [2]:

graph = {'A':['B','C'],
         'B':['A','D','E'],
         'C':['A','G','H'],
         'D':['B'],
         'E':['B','F'],
         'F':['E'],
         'G':['C'],
         'H':['C']}

stack과 queue를 만들어야 할때, 리스트보다는 collections.deque 객체를 사용하면 효율적이다

In [3]:

from collections import deque

1. 방문했던 노드 목록을 저장해둔 리스트가 필요하다.
2. 다음으로 방문할 노드의 목록을 차례대로 저장할 리스트(큐)를 만들어야 한다.
3. 더이상 방문할 노드가 없을때까지 루프를 돌려준다.

In [4]:

def bfs_iteration(graph, root):
    visited = [] ## visited = 방문한 노드들을 기록한 리스트
    queue = deque([root]) ## bfs는 queue개념을 이용한다.
    
    while(queue): ## queue에 남은 것이 없을 때까지 반복
        node = queue.pop() ## node : 현재 방문하고 있는 노드
        
        ## 현재 node를 방문한 적 없다. -> visited에 추가
        ## visited에 추가 후, 해당 노드의 자식 노드들을 queue에 추가
        if node not in visited:
            visited.append(node)
            queue.extendleft(graph[node])
    return visited

In [5]:

bfs_iteration(graph,'A')

Out[5]:

['A', 'B', 'C', 'D', 'E', 'G', 'H', 'F']