알고리즘 : 너비 우선 탐색(Breadth-First Search)

너비 우선 탐색 (BFS)은?

• 너비 우선 탐색(Breath-First Search) : 정점들과 같은 위치에 있는 노드(형제노드)들을 먼저 탐색하는 방식

 

BFS방식 A - B - C - D - G - H - I - E - F - J

• 한 단계씩 내려가면서 해당노드와 같은 위치에 있는 노드(형제노드)들을 먼저 순회함

 

파이썬으로 그래프를 표현하는 방법

• 파이썬에서 제공하는 딕셔너리와 리스트 자료 구조를 활용해서 그래프를 표현할 수 있음

Key	Values
A	B	C
B	A	D
C	A	G	H	I
D	B	E	F
E	D
F	D
G	C
H	C
I	C	J
J	I

 

graph = dict()

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

graph

"""출력결과
{'A': ['B', 'C'],
 'B': ['A', 'D'],
 'C': ['A', 'G', 'H', 'I'],
 'D': ['B', 'E', 'F'],
 'E': ['D'],
 'F': ['D'],
 'G': ['C'],
 'H': ['C'],
 'I': ['C', 'J'],
 'J': ['I']}
"""