너비우선탐색
-
[알고리즘] 너비 우선 탐색 (BFS)Algorithms & Data Structure 2021. 8. 20. 18:23
너비 우선 탐색 (Breadth-First Search) 노드와 같은 레벨에 있는 형제 노드들부터 먼저 탐색하는 방식 그래프를 표현 할 때 딕셔너리와 리스트 자료 구조 활용 시간 복잡도 : O(V+E), (V: 노드 갯수, E: 간선 갯수) 알고리즘 구현 방법 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'] def bfs..