如何更改此 prim 的算法函数以接收并返回邻接列表？

Question

我想在以邻接列表结构的图中找到最小生成树。我能够使用PRIM的算法来弄清MST，但我当前的解决方案不使用邻接列表。

from collections import defaultdict
from heapq import *
def prim( nodes, edges ):
   conn = defaultdict( list )
   for n1,n2,c in edges:
    conn[ n1 ].append( (c, n1, n2) )
    conn[ n2 ].append( (c, n2, n1) )
mst = []
used = set( nodes[ 0 ] )
usable_edges = conn[ nodes[0] ][:]
heapify( usable_edges )
while usable_edges:
    cost, n1, n2 = heappop( usable_edges )
    if n2 not in used:
        used.add( n2 )
        mst.append( ( n1, n2, cost ) )
        for e in conn[ n2 ]:
            if e[ 2 ] not in used:
                heappush( usable_edges, e )
 return mst
#test
nodes = list("ABCDEFG")
edges = [("A", "B", 7), ("A", "D", 5),
         ("B", "C", 8), ("B", "D", 9), ("B", "E", 7),
         ("C", "E", 5),
         ("D", "E", 15), ("D", "F", 6),
         ("E", "F", 8), ("E", "G", 9),
         ("F", "G", 11)]
 print "prim:", prim( nodes, edges )

我需要它采取并返回这样的东西：

 {'A': [('B', 2)],
  'B': [('A', 2), ('C', 5)],
  'C': [('B', 5)]}

谢谢！

Answer 1

将MST作为边缘列表后，您只需要迭代它即可填充字典。

这正是您在prim函数开始时所做的：

conn = defaultdict(list)
for n1, n2, c in edges:
    conn[n1].append((c, n1, n2))
    conn[n2].append((c, n2, n1))

您需要为mst列表而不是edges做同样的事情。