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

Question

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

Answer 1

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

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

Answer 2

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

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