Список связующего дерева из списка ребер в 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)

Но создание Spanning Tree - это отдельная история. Учитывая, что связующее дерево будет невзвешенным, я не уверен, нужно ли мне использовать какую-то версию алгоритма Прима здесь?

Любая помощь приветствуется!

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

Начальный график

Сгенерированное остовное дерево