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

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

728x90

너비 우선 탐색 (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']} """

from http://every-time-i-pass-this-place.tistory.com/26 by ccl(A) rewrite - 2021-09-21 16:00:00