■ 그래프에서 깊이 우선 탐색(Depth-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 |
def getDepthFirstSearchShotestPathList(graphDictionary, startNode): visitedNodeList = [] adjacentNodeList = [startNode] while adjacentNodeList: node = adjacentNodeList.pop() if node not in visitedNodeList: visitedNodeList.append(node) adjacentNodeList.extend(graphDictionary[node]) return visitedNodeList graphDictionary = { "A" : ["B", "F", "I"], # A 노드에 인접한 노드들이 B, F, I 노드이다. "B" : ["A", "C", "E"], "C" : ["B", "D", "E"], "D" : ["C", "G", "H"], "E" : ["B", "C", "G"], "F" : ["A", "G" ], "G" : ["D", "E", "F"], "H" : ["D" ], "I" : ["A" ] } shortestPathList = getDepthFirstSearchShotestPathList(graphDictionary, "B") print(shortestPathList) """ ['B', 'E', 'G', 'F', 'A', 'I', 'D', 'H', 'C'] # B 노드에서 제일 가까운 노드 순서로 나열된다. """ |