■ 그래프에서 너비 우선 탐색(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 36 37 38 39 40 41 42 |
from collections import deque def getBreadthFirstSearchShortestPathTuple(graphDictionary, startNode, distanceDictionary): visitedNodeList = [startNode] adjacentNodeDeque = deque([startNode]) while adjacentNodeDeque: node = adjacentNodeDeque.popleft() for adjacentNode in graphDictionary[node]: if adjacentNode not in visitedNodeList: visitedNodeList.append(adjacentNode) adjacentNodeDeque.append(adjacentNode) distanceDictionary[adjacentNode] = distanceDictionary[node] + 1 return visitedNodeList, distanceDictionary 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" ] } distanceDictionary = dict.fromkeys(graphDictionary.keys(), 0) shortestPathTuple = getBreadthFirstSearchShortestPathTuple(graphDictionary, "B", distanceDictionary) print(shortestPathTuple) """ ( ['B', 'A', 'E', 'C', 'F', 'I', 'G', 'D', 'H'], # B 노드에서 제일 가까운 노드 순서로 나열된다. {'A' : 1, 'B' : 0, 'C' : 1, 'D' : 2, 'E' : 1, 'F' : 2, 'G' : 2, 'H' : 3, 'I' : 2} # B 노드에서 각 노드의 가중치를 나타낸다. ) """ |