사전을 사용하여 깊이 검색 수정

Question

this one과 같이 실제로 DFS python 구현이 많이 있지만 비용은 포함되어 있지 않습니다. DFS 경로의 총 비용을 기록 할 수 있기를 원하지만이 구현은 그래프를 사전 집합으로 나타냅니다.

graph = {'A': set(['B', 'C']), 
     'B': set(['A', 'D', 'E']), 
     'C': set(['A', 'F']), 
     'D': set(['B']), 
     'E': set(['B', 'F']), 
     'F': set(['C', 'E'])} 

def dfs(graph, start): 
    visited, stack = set(), [start] 
    while stack: 
     vertex = stack.pop() 
     if vertex not in visited: 
      visited.add(vertex) 
      stack.extend(graph[vertex] - visited) 
    return visited 

dfs(graph, 'A') # {'E', 'D', 'F', 'A', 'C', 'B'} 

세트가 적절하게 비용을 기록 할 수 있다고 생각하지 않습니다. 따라서 사전을 사전으로 표현하는 것이 비용을 구현하는 좋은 방법이라고 생각합니다. 예 :

graph = {'A' : {'C' : 10, 
       'D' : 7} 
       etc..... 

제 질문은이 알고리즘을 어떻게이 새로운 유형의 그래프를 사용하도록 수정할 수 있습니까? 파이썬 구문에 대해서는 아직 익숙하지 않으므로 이와 같은 예제를 보면 실제로 도움이됩니다. 좋아, 그것에 대해 생각의 다른 방법이있다 : 비용을 표현하기 더 쉬운 방법이 있다면

는 다른 방법으로, 나는 제안

편집에 열려있어. 위의 코드를 수정하여 중첩 된 사전을 집합과 유사하게 처리하려면 어떻게해야합니까?

EDIT2 : 사전의 keys() 함수가 목록을 반환한다는 것을 알게되었으므로 직접 해결했다고 생각합니다.

Answer 1

모양은 NetworkX와 같습니다. DFS는 패키지에 포함되어 있으며 그래프 구현은 원하는 것입니다. 희망이 도움이됩니다.