如何改变这个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 )

我需要它来取回这样的东西：

^{pr2}$

谢谢你！在

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。在