minimum-spanning-tree

0зной

2ответ

Алгоритм Prim для минимальных связующих деревьев - путаница в алгоритме

Я изучаю книгу Cormen и др., И я немного смущен относительно алгоритма, который они предоставили. Я понял, как концепция алгоритма Prim's работает через википедию, но я не могу имитировать работу, исп

1зной

1ответ

Есть ли способ динамического программирования для вычисления k минимальных остовных деревьев?

Мой учитель попросил нас применить решение для динамического программирования к этой проблеме, но я думаю, что одного не существует, так как я не мог найти его с помощью Google. В любом случае, учитыв

22зной

4ответ

Реализация всех минимальных связующих деревьев

Я искал реализацию (я использую библиотеку networkx), которая найдет все минимальные связующие деревья (MST) неориентированного взвешенного графа. Я могу только найти реализации алгоритма Крускала и а

7зной

4ответ

Существует ли минимальное остовное дерево, которое не содержит взвешенного края min/max?

Если мы (произвольный), соединенный неориентированный граф G, ребро которого имеет различные веса, делает каждый из G МСТ содержит минимальное взвешенное ребро? есть ли MST из G, который не содержит м

3зной

1ответ

Алгоритм (ы) для минимального связующего дерева с ограниченной степенью + ограниченным диаметром?

Предположим, что у меня есть 3 типа ограничений на вычисления связующего дерева: стесненных степень (например: узел в связующего дерева может быть только подключены до 3 других узлов) ограниченного ди

3зной

1ответ

Как возможно, сложность алгоритма Boruvka - O (E * logV)?

1 Begin with a connected graph G containing edges of distinct weights, and an empty set of edges T 2 While the vertices of G connected by T are disjoint: 3 Begin with an empty set of edges E 4 For