너비 우선탐색 BFS (Breath First Search)

이번 포스팅은 너비 우선탐색에 대해서 소개하려고 한다. 

 

BFS는 DFS와 같이 그래프 탐색의 대표적인 알고리즘이기도 하다.

 

deque를 사용하고 선입선출 형식을 사용한다. 

일반적으로 DFS보다 검색속도가 빠르다고 한다. 

 

바로 탐색 과정을 살펴보도록 하자.

 

---

BFS 방문과정 

빨강이 방문완료, 회색이 방문중이라는 표시이다. 

 

Root node를 queue에 넣는다. 

 

 

1을 방문처리 및 삭제한 후 인접노드인 2, 3을 queue에 넣는다. 

 

인접노드 중에 먼저 들어간 2를 방문처리 및 삭제한 후 4, 5를 queue에 집어 넣는다. 

 

 

이후 3을 방문처리 및 삭제한 후 3의 인접노드인 6, 7을 queue에 추가한다. 

 

 

 

남은 4개는 인접노드가 없으므로, 차례대로 방문처리 및 삭제를 진행한다. 

 

 

따라서 최종 방문순서는 1, 2, 3, 4, 5, 6, 7이 된다. 

 

시간복잡도는 DFS와 같이 O(V + E)이다. 

(V: 노드의 개수, E: 간선의 개수) 

 

 

---

구현코드

 

from collections import deque

def bfs(graph, start):

    need_visited, visited = deque(), [] # 방문해야할 노드와 이미 방문한 노드의 방문록 작성
    # 탐색 시작시점을 넣음
    need_visited.append(start)

    while need_visited: # 방문해야할 지점이 있을때까지 탐색
        
        node = need_visited.popleft() # 먼저 들어간 노드부터 chlid 탐색

        visited.append(node)

        for child in graph[node]: # 방문한 노드의 child를 차례대로 탐색
            if child not in visited: # 만약 방문을 안했다면 탐색할 노드로 넣음
                need_visited.append(child)

    return visited

graph = dict()
 
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

print(bfs(graph, 'A'))

 

실행결과