해시 테이블로 그래프 해석 (파이썬 DICT)

Question

나는이 같은 간단한 지시 그래프 해석 이해 :

graph = {1: [2], 2: [3], 3: [4, 5, 1], 4: [], 5: [4]} 
#    1 
#   /. 
#   / \ 
#   .  \ 
#  4--.3 ------.2 
#  \ . 
#   \ | 
#   .5 

을하지만 같은 dicts의 DICT, 해석하는 방법을 알고하지 않습니다

{1: {2: 3, 3: 8, 5: -4}, 2: {4: 1, 5: 7}, 3: {2: 4}, 4: {1: 2, 3: -5}, 5: {4: 6}} 

을 가중치 그래프입니까? 이런 종류의 그래프는 어떻게 이해해야합니까?

이 질문을 downvote로 결정하면 의견에 해당 기사와 링크를 남겨주세요.

Answer 1

예, 가중치가 적용된 유향 그래프입니다. 다음 그래프

같이 표현된다 ..

L = {'A': {'C':2, 'D':6}, 'B': {'D':8, 'A':3}, 
    'C': {'D':7, 'E':5}, 'D': {'E':-2}, 'E': {}} 

Answer 2

이 가중 에지 관한 그래프이다.

당신은 그것을 통해 경로를 탐색 할 수 Dijkstra's Algorithm 같은 것을 사용할 수 있습니다이 그래픽 표현을 생산

nestedg={1: {2: 3, 3: 8, 5: -4}, 
    2: {4: 1, 5: 7}, 
    3: {2: 4}, 
    4: {1: 2, 3: -5}, 
    5: {4: 6}} 

with open('/tmp/graph.dot','w') as out: 
    for line in ('digraph G {','size="16,16";','splines=true;'): 
     out.write('{}\n'.format(line)) 
    for start,d in nestedg.items(): 
     for end,weight in d.items(): 
       out.write('{} -> {} [ label="{}" ];\n'.format(start,end,weight)) 
    out.write('}\n')   

: 당신은 또한 당신의 특정 데이터를 시각화 할 수 graphviz를 사용할 수 있습니다. 예 사용이 특정 경로가 더 큰 '비용'을 갖는 라우팅 될 것이다 :

def find_all_paths(graph, start, end, path=[]): 
     path = path + [start] 
     if start == end: 
      return [path] 
     if start not in graph: 
      return [] 
     paths = [] 
     for node in graph[start]: 
      if node not in path: 
       newpaths = find_all_paths(graph, node, end, path) 
       for newpath in newpaths: 
        paths.append(newpath) 
     return paths  

def min_path(graph, start, end): 
    paths=find_all_paths(graph,start,end) 
    mt=10**99 
    mpath=[] 
    print '\tAll paths from {} to {}: {}'.format(start,end,paths) 
    for path in paths: 
     t=sum(graph[i][j] for i,j in zip(path,path[1::])) 
     print '\t\tevaluating: {}, cost: {}'.format(path, t) 
     if t<mt: 
      mt=t 
      mpath=path 

    e1=' '.join('{}->{}:{}'.format(i,j,graph[i][j]) for i,j in zip(mpath,mpath[1::])) 
    e2=str(sum(graph[i][j] for i,j in zip(mpath,mpath[1::]))) 
    print 'Best path: '+e1+' Total: '+e2+'\n' 

if __name__ == "__main__": 
    nestedg={1: {2: 3, 3: 8, 5: -4}, 
     2: {4: 1, 5: 7}, 
     3: {2: 4}, 
     4: {1: 2, 3: -5}, 
     5: {4: 6}} 

    min_path(nestedg,1,5) 
    min_path(nestedg,1,4) 
    min_path(nestedg,2,1) 

데이터를 사용하여 그래프를 통해 몇 가지 예를 들어 경로는 다음과 같습니다

All paths from 1 to 5: [[1, 2, 5], [1, 3, 2, 5], [1, 5]] 
     evaluating: [1, 2, 5], cost: 10 
     evaluating: [1, 3, 2, 5], cost: 19 
     evaluating: [1, 5], cost: -4 
Best path: 1->5:-4 Total: -4 

    All paths from 1 to 4: [[1, 2, 4], [1, 2, 5, 4], [1, 3, 2, 4], [1, 3, 2, 5, 4], [1, 5, 4]] 
     evaluating: [1, 2, 4], cost: 4 
     evaluating: [1, 2, 5, 4], cost: 16 
     evaluating: [1, 3, 2, 4], cost: 13 
     evaluating: [1, 3, 2, 5, 4], cost: 25 
     evaluating: [1, 5, 4], cost: 2 
Best path: 1->5:-4 5->4:6 Total: 2 

    All paths from 2 to 1: [[2, 4, 1], [2, 5, 4, 1]] 
     evaluating: [2, 4, 1], cost: 3 
     evaluating: [2, 5, 4, 1], cost: 15 
Best path: 2->4:1 4->1:2 Total: 3