[알고리즘] 너비 우선 탐색(BFS) (Python)

[알고리즘] 너비 우선 탐색(BFS) (Python)

반응형

1. BFS란...?

한 단계씩 내려가면서 같은 레벨에 있는 노드들을 먼저 순회

2. 구현 전 생각정리

탐색할 그래프를 딕셔너리와 데크를 활용하여 구현해보자

need_visit 데크의 왼쪽에서 하나씩 node를 뽑아오며 탐색, 탐색할 때 그 node와 연결된 노드들을 need_visit 데크의 오른쪽에 추가해줌

3. 코드 구현

from collections import deque graph = dict() graph['A'] = deque(['B', 'C']) graph['B'] = deque(['A', 'D']) graph['C'] = deque(['A', 'G', 'H', 'I']) graph['D'] = deque(['B', 'E', 'F']) graph['E'] = deque(['D']) graph['F'] = deque(['D']) graph['G'] = deque(['C']) graph['H'] = deque(['C']) graph['I'] = deque(['C', 'J']) graph['J'] = deque(['I']) def bfs(graph, start_node): visited = deque() need_visit = deque() need_visit.append(start_node) while need_visit: node = need_visit.popleft() if node not in visited: #아직 탐색 안된 상태라면 visited.append(node) need_visit.extend(graph[node])#아래 level도 need_visit에 추가되겠지만 현 level이 다 탐색 된 이후에 탐색됨 return visited bfs(graph,'A')

4. 시간 복잡도

while문이 '노드 수' + '간선 수' 만큼 실행된다고 함

위의 코드를 예시로 생각해보면 need_visit 데크에 A B C A D A G H I B E F D D C C C J I 순서대로 원소가 들어가고, need_visit안에 있는 모든 친구들을 visited에 있는지 여부 판단 후 탐색하기 때문에 총 19번 시행됨

노드 수: 10 / 간선 수: 9 이므로 공식이 맞음을 확인

반응형

from http://tipsyziasu.tistory.com/108 by ccl(A) rewrite - 2021-08-08 20:00:32