python - Python中从边缘列表生成树列表

Question

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

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 算法？

感谢任何帮助!

Answer 1

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

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]]

起始图表

生成的生成树