■ 그래프에서 너비 우선 탐색(Breadth-First Search)을 사용해 최단 경로를 구하는 방법을 보여준다.
▶ 예제 코드 (PY)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
from collections import deque def getBreadthFirstSearchShortestPathList(graphDictionary, startNode): visitedNodeList = [] adjacentNodeDeque = deque([startNode]) while adjacentNodeDeque: node = adjacentNodeDeque.popleft() if node not in visitedNodeList: visitedNodeList.append(node) adjacentNodeDeque.extend(graphDictionary[node]) return visitedNodeList graphDictionary = { "A" : ["B", "F", "I"], # A 노드에 인접한 노드들이 B, F, I 노드이다. "B" : ["A", "E", "C"], "C" : ["B", "E", "D"], "D" : ["C", "G", "H"], "E" : ["B", "C", "G"], "F" : ["A", "G" ], "G" : ["E", "F", "D"], "H" : ["D" ], "I" : ["A" ] } shortestPathList = getBreadthFirstSearchShortestPathList(graphDictionary, "B") print(shortestPathList) """ ['B', 'A', 'E', 'C', 'F', 'I', 'G', 'D', 'H'] # B 노드에서 제일 가까운 노드 순서로 나열된다. """ |