[알고리즘] BFS(Breadth First Search)

 

BFS란?

- 큐를 통해 구현이 가능하다.

- 노드를 방문하면서 인접한 노드 중 방문하지 않았던 노드의 정보만 큐에 넣고, 큐어 들어있던 노드부터 방문한다.

- 파이썬에서 큐를 구현할 때, list를 사용하는 경우가 대부분인데. list.pop(0)은 시간복잡도가 O(N)이기 때문에 이렇게 구현할 경우 시간적으로 비효율적이다. 따라서 collections 라이브러리의 deque를 사용하면 시간을 절약할 수 있다.

- 또한 인접한 노드 중 방문하지 않았던 노드를 큐에 넣을 때는 set 데이터 타입을 이용하면 쉽게 구현할 수 있다.

타이틀 입력부분2

 

BFS 구현

- 동작 과정

  1) root 노드부터 시작하기 위해 deque에 root를 넣는다.

  2) 큐가 빌 떄까지 loop를 돌린다.

  3) 큐의 맨앞 노드를 꺼낸다. (pop)

  4) 해당 노드가 방문 리스트(visited)에 없다면 추가하고, 해당 노드의 자식 노드를 큐에 넣는다.

from collections import deque

graph_list = {1: set([3, 4]),
              2: set([3, 4, 5]),
              3: set([1, 5]),
              4: set([1]),
              5: set([2, 6]),
              6: set([3, 5])}
root_node = 1

def bfs(graph, root):
    visited = []
    queue = deque([root])

    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            queue += graph[n] - set(visited)
    return visited
  
print(bfs(graph_list, root_node))

 

 

참고

1.commons.wikimedia.org/wiki/File:Breadth-First-Search-Algorithm.gif

File:Breadth-First-Search-Algorithm.gif - Wikimedia Commons