1

我试图弄清楚如何从给定的边列表中打印生成树列表。例如，如果我读到：

0 1

2 1

0 2

1 3

我想打印出一个生成树列表：

[[1], [0,2,3], [1], [1]]

我知道如何使用以下代码创建邻接列表：

n = int(input("Enter number of vertices: "))
adjList = [[] for i in range(n)]
with open("graph.txt") as edges:
    for line in edges:
        line = line.replace("\n", "").split(" ")
        adjList[int(line[0])].append(int(line[1]))
        adjList[int(line[1])].append(int(line[0]))
    print(l)

但是创建生成树是另一回事。鉴于生成树未加权，我不确定是否需要在这里使用 Prim 算法的某个版本？

任何帮助表示赞赏！

4

1 回答 1

1

这个实现是基于networkx包的（它的文档在这里）。请注意，我认为您可以为该组连接获得一些不同的生成树。此代码将通过其边集合表示生成树，但我会看看是否可以修改它以按照您喜欢的方式表示树。

import networkx as nx

def spanning_tree_from_edges(edges):
    graph = nx.Graph()

    for n1, n2 in edges:
        graph.add_edge(n1, n2)

    spanning_tree = nx.minimum_spanning_tree(graph)
    return spanning_tree

if __name__ == '__main__':
    edges = [(0, 1), (2, 1), (0, 2), (1, 3)]
    tree = spanning_tree_from_edges(edges)
    print(sorted(tree.edges()))

输出

[(0, 1), (0, 2), (1, 3)]

这种替代方法似乎将树表示为节点连接的集合（即以您想要的格式）。请注意，此集合是不同的，因为它与您获得的生成树不同：

if __name__ == '__main__':
    edges = [(0, 1), (2, 1), (0, 2), (1, 3)]
    tree = spanning_tree_from_edges(edges)
    print([list(nx.all_neighbors(tree, n)) for n in tree.nodes()])

输出

[[1, 2], [0, 3], [0], [1]]

起始图

生成的生成树

于 2017-01-16T22:40:44.703 回答