너비 우선 탐색
이전 블로그: 깊이우선탐색(DFS)
1. 파이썬으로 그래프를 표현하는 방법
- 파이썬에서 제공하는 딕셔너리와 리스트 자료 구조를 활용해서 그래프를 표현할 수 있음.
그래프 예와 파이썬 표현
1
2
3
4
5
6
7
8
9
10
11
12
13
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']
2. BFS 알고리즘 구현
- 자료구조 큐를 활용함 - need_visit 큐와 visited 큐 두개의 큐를 생성
![]()
1
2
3
4
5
6
7
8
9
10
11
12
13
def bfs(graph, start_node):
visited = list()
need_visit = list()
need_visit.append(start_node)
while need_visit:
node = need_visit.pop(0)
if node not in visited:
visited.append(node)
need_visit.extend(graph[node])
return visited
1
2
bgs(graph, 'A')
# ['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']
3. 시간 복잡도
- 일반적인 BFS 시간 복잡도
- 노드 수 : V
- 간선 수: E
- 위 코드에서 while need_visit 은 V + E 번 만큼 수행함
- 시간 복잡도 : O (V + E)