Поиск минимального остовного дерева с матрицей смежности с более чем 1 компонентом связности

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

Я кодирую здесь на Java, и я могу прекрасно построить матрицу смежности, просто я застрял на этой части.


java adjacency-matrix minimum-spanning-tree
person Chris Song    schedule 04.05.2011    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Так вы имеете в виду, что существует вероятность того, что остовного дерева нет? В этом случае с prims все в порядке, вам просто нужно добавить проверку, что в выбранных столбцах есть возможный путь. Однако в случае отсутствия остовного дерева будет сложно попытаться что-либо с ним сделать, вам придется удалить все вершины, которые вы добавили в дерево, и рассматривать оставшуюся часть как новый граф.

Редактировать: если вы выполняете prims вручную на матрице (Google «матрица prims D1»), тогда легко визуализировать то, что я имею в виду под отсутствием дуг в выбранных столбцах.

person Matt    schedule 04.05.2011
comment
Хорошо, мой профессор сказал, что если нет одного связующего дерева, то мы должны сделать сумму всех связующих деревьев для каждого связанного компонента. Означает ли это, что мне придется перебирать каждый подключенный компонент... - person Chris Song; 05.05.2011
comment
@Chris Song, нет, вы найдете этап в prims, где вы знаете, что сети нет, а затем вы можете начать с другого узла, не входящего в коллекцию, и просто добавить его. Это будет иметь точно такой же эффект, как если бы вы рисовали фиктивную дугу от узла в коллекции к узлу снаружи. Как я уже сказал, возьмите бумагу и попробуйте. - person Matt; 05.05.2011

arrow_upward
0
arrow_downward

Нет такой вещи, как минимальное остовное дерево, если граф не связан.

Таким образом, вы можете захотеть сделать одно из двух: либо создать минимальный остовный лес из всех подключенных компонентов; или же построить MST для всего графа, добавив ребра для соединения ваших компонентов. Какой из них зависит от вашей проблемной области.

Или, может быть, вы просто должны обнаружить, что граф не связан, и указать, что это невозможно? Это легко сделать.

person user738252    schedule 04.05.2011
comment
Оба случая можно встроить в алгоритм prim, а не как отдельные проверки в начале. Конечно, первый случай во многом зависит от цели, насколько он жизнеспособный. - person Matt; 04.05.2011
comment
По словам моего профессора, он говорит, что для случаев, когда нет минимального остовного дерева, мы должны сделать минимальное остовное дерево для всех наших подключенных компонентов. Мы просто находим сумму весов всех ребер, так что технически это должно работать. - person Chris Song; 04.05.2011