<p>我没有仔细阅读你的代码,你真的应该看看指南<a href="https://stackoverflow.com/help/mcve">Minimal, complete, verifiable example</a>。在</p>
<p>然而,将一个边列表转换成一个图,然后使用标准的<code>mst</code>算法,例如Prim的:</p>
<pre><code>def create_graph(edgelist):
graph = {}
for e1, e2 in edgelist:
graph.setdefault(e1, []).append(e2)
graph.setdefault(e2, []).append(e1)
return graph
# Prim's
def mst(start, graph):
closed = set()
edges = []
q = [(start, start)]
while q:
v1, v2 = q.pop()
if v2 in closed:
continue
closed.add(v2)
edges.append((v1, v2))
for v in graph[v2]:
if v in graph:
q.append((v2, v))
del edges[0]
assert len(edges) == len(graph)-1
return edges
>>> graph = create_graph([[10, 2], [7, 4], [11, 3], [1, 12], [6, 8], [10, 3], [4, 9], [5, 7], [8, 12], [2, 11], [1, 6], [0, 10], [7, 2], [12, 5]])
>>> min_gragh = create_graph(mst(0, graph))
>>> min_graph
{0: [10],
1: [6],
2: [11, 7],
3: [10, 11],
4: [7, 9],
5: [7, 12],
6: [8, 1],
7: [2, 5, 4],
8: [12, 6],
9: [4],
10: [0, 3],
11: [3, 2],
12: [5, 8]}
>>> [sorted(min_graph[k]) for k in sorted(min_graph)]
[[10], [6], [7, 11], [10, 11], [7, 9], [7, 12], [1, 8], [2, 4, 5], [6, 12], [4], [0, 3], [2, 3], [5, 8]]
</code></pre>
<p>一个图可能有多个有效的MST,例如,较小的<code>edgelist</code>生成{<cd3>},这也是一个有效的MST,但与预期的输出不同。在</p>