0

我想在结构为邻接列表的图中找到最小生成树。我能够使用 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)]}

谢谢你！

4

1 回答 1

0

一旦你有一个 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.

于 2017-04-28T18:41:49.900 回答