#java #minimum-spanning-tree #adjacency-matrix
#java #минимальное связующее дерево #матрица смежности
Вопрос:
У меня есть матрица смежности, созданная для одного из моих проектов, и мне нужно иметь возможность построить минимальное связующее дерево из этой матрицы. Судя по чтению, алгоритм Прима лучше всего подходит для этого случая, однако мы не можем предположить, что граф представляет собой один большой подключенный компонент, поскольку я точно знаю, что по крайней мере один из графиков, над которыми нам приходится работать, содержит около нескольких тысяч подключенных компонентов. Является ли алгоритм Prim все еще жизнеспособным здесь, и если да, есть ли что-то еще, что мне нужно сделать?
Здесь я пишу на Java, и я могу нормально построить матрицу смежности, просто я застрял на этой части.
Ответ №1:
То есть вы имеете в виду, что существует вероятность отсутствия связующего дерева? В этом случае с простыми числами все в порядке, вам просто нужно добавить проверку наличия возможного пути в выбранных столбцах. В случае, если связующего дерева нет, будет сложно попытаться что-либо с ним сделать, вам придется удалить все вершины, которые вы добавили в дерево, и обработать остаток как новый граф.
Редактировать: Если вы выполняете простые числа вручную в матрице (google ‘D1 prims matrix’), то легко визуализировать, что я имею в виду под отсутствием дуг в выбранных столбцах.
Комментарии:
1. Хорошо, мой профессор сказал, что если нет ни одного связующего дерева, то мы должны вычислить сумму всех связующих деревьев для каждого подключенного компонента. Означает ли это, что мне придется перебирать каждый отдельный подключенный компонент…
2. @Chris Song, Нет, вы найдете этап в prims, когда вы знаете, что сети нет, а затем вы можете начать с другого узла, которого нет в коллекции, и просто добавить его. Это имело бы точно такой же эффект, как при рисовании фиктивной дуги от узла в коллекции к одному внешнему. Как я уже сказал, возьмите какую-нибудь бумагу и попробуйте.
Ответ №2:
Нет такого понятия, как минимальное связующее дерево, если граф не подключен.
Итак, вы можете захотеть сделать одну из двух вещей: либо построить минимальный связующий лес из всех ваших подключенных компонентов; либо построить MST для всего графика, добавив ребра для соединения ваших компонентов. Какой из них это зависит от вашей проблемной области.
Или, может быть, вы просто должны обнаружить, что график не подключен, и указать, что это невозможно? Это легко сделать.
Комментарии:
1. Оба случая можно встроить в алгоритм prim, скорее как отдельные проверки в начале. Конечно, первый случай во многом зависит от цели относительно того, жизнеспособен ли он.
2. По словам моего профессора, он говорит, что для случаев, в которых нет минимального связующего дерева, мы должны создать минимальное связующее дерево для всех наших подключенных компонентов. Мы просто находим сумму весов для всех ребер, так что технически это должно сработать.