минимальное связующее дерево из матрицы смежности

#java #graph #minimum-spanning-tree

#java — язык #График #минимальное связующее дерево #java

Вопрос:

У меня проблема, с которой я действительно борюсь. У меня есть набор точек с взвешенными ребрами, и мне нужно создать минимальное связующее дерево, чтобы найти наименьшее количество необходимых ребер. Мне нужно сделать это на java. Прямо сейчас я создаю матрицу смежности, и на этом я застрял. Я действительно понятия не имею, куда идти дальше. Любая помощь была бы потрясающей.

1. Вот подсказка — напишите какой-нибудь код и опубликуйте его. Мы не делаем домашнюю работу. Вы получите лучший ответ, если приложите некоторые усилия и зададите конкретные вопросы. Также отметьте это как домашнее задание. И прочитайте это: catb.org /~esr/faqs/smart-questions.html

2. @debracey, о чем ты говоришь? Дейкстра — это кратчайший путь, оператору требуется минимальное связующее дерево, как в алгоритмах Prim или Kruskal.

3. @debracey: Я не думаю, что алгоритм Дейкстры можно использовать для нахождения минимального связующего дерева. Его можно использовать для нахождения кратчайшего пути между двумя узлами, но это все. Возможно, вы думаете об алгоритме Крускала.

Ответ №1:

Взгляните на алгоритмы Kruskal и Prim, мне действительно нравится Prim, потому что он очень прост в реализации и понимании: http://en.wikipedia.org/wiki/Prim’s_algorithm

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

Ответ №2:

Если вы пытаетесь найти минимальное связующее дерево, у вас всегда будет одинаковое количество ребер, веса будут просто разными. Метод, который я рекомендую использовать для решения этой проблемы, — алгоритм Прима. Это работает лучше всего, когда у вас есть отдельные взвешенные ребра. Хотя кто-то еще обсуждал это как возможность, я объясню это полностью здесь, чтобы решить проблему минимального связующего дерева с неориентированным, связным графом.

Первый шаг к Prim — это начать с любой вершины V и добавить ее к (в настоящее время) пустому набору вершин, называемых «Обнаруженными». Оттуда вы посмотрите на все ребра, которые примыкают к V (используя вашу матрицу смежности) и соединены с вершинами, которых нет в «Обнаруженном» (используя ваш обнаруженный набор), и добавьте их в минимальную структуру кучи. Куча позволит вам взять минимальное ребро и добавить его в новую древовидную структуру. Другой конец этого ребра — ваша следующая новая начальная вершина. Повторяйте этот процесс, пока не получите минимальное связующее дерево.