Алгоритм Прима для динамических локаций

Question

Предположим, у вас есть входной файл:

<total vertices>
<x-coordinate 1st location><y-coordinate 1st location>
<x-coordinate 2nd location><y-coordinate 2nd location>
<x-coordinate 3rd location><y-coordinate 3rd location>
...

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

Answer 1

Если вы уже знаете prim, это легко. Создать матрицу смежности adj[i][j] = расстояние между местоположением i и местоположением j

Answer 2

Я просто собираюсь описать некоторые реализации Prim, и, надеюсь, это поможет вам.

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

Предполагая, что у вас есть ребра (и веса этих ребер. Как сказано выше @doomster, это может быть плоское расстояние между точками, поскольку они являются координатами), мы можем начать думать о нашей реализации. Википедия описывает три разные структуры данных, которые приводят к трем различным временам выполнения: http://en.wikipedia.org/wiki/Prim's_algorithm # Time_complexity

Самым простым является матрица смежности. Как можно догадаться по названию, матрица описывает "смежные" узлы. Чтобы быть точным, есть |v| строки и столбцы (где |v| это количество вершин). Значение в adjacencyMatrix[i][j] варьируется в зависимости от использования. В нашем случае это вес ребра (т.е. расстояние) между узлами i а также j (это означает, что вам нужно каким-то образом индексировать вершины. Например, вы можете добавить вершины в список и использовать их положение в списке).

Теперь с использованием этой матрицы смежности наш алгоритм выглядит следующим образом:

1. Создайте словарь, который содержит все вершины и имеет ключевое слово "расстояние". Первоначально расстояние всех узлов равно бесконечности.
2. Создайте еще один словарь, чтобы отслеживать "родителей". Мы используем это для генерации MST. Более естественно отслеживать границы, но на самом деле это проще реализовать, отслеживая "родителей". Обратите внимание, что если вы корень дерева (то есть назначить некоторый узел в качестве корня), то каждый узел (кроме корня) имеет точно один родительский. Так что, производя этот словарь родителей, мы получим наш MST!
3. Создать новый список со случайно выбранным узлом v из первоначального списка.
   1. Удалить v из словаря расстояния и добавьте его в родительский словарь с нулем в качестве родителя (т. е. это "корень").
   2. Пройдите строку в матрице смежности для этого узла. Для любого узла w это связано (для несвязанных узлов вы должны установить значение их матрицы смежности в какое-то специальное значение. 0, -1, int макс и т. д.) обновите его "расстояние" в словаре до adjacencyMatrix[v][w], Идея состоит в том, что это больше не "бесконечно далеко"... мы знаем, что можем добраться от v,
4. Пока словарь не пустой (то есть, когда есть узлы, к которым нам еще нужно подключиться)
   1. Просмотрите словарь и найдите вершину с наименьшим расстоянием x
   2. Добавьте его в наш новый список вершин
   3. Для каждого из соседей обновите расстояние до min(adjacencyMatrix[x][neighbor], distance[neighbor]) а также обновить своих родителей, чтобы x, В принципе, если есть более быстрый способ добраться до neighbor тогда словарь расстояния должен быть обновлен, чтобы отразить это; и если мы добавим neighbor к новому списку мы знаем, какое ребро мы фактически добавили (потому что родительский словарь говорит, что его родитель x).
5. Были сделаны. Выведите MST как хотите (все, что вам нужно, содержится в словаре родителей)

Я признаю, что есть некоторый скачок от страницы википедии к фактической реализации, как описано выше. Я думаю, что лучший способ преодолеть этот разрыв - просто перебор кода. Под этим я подразумеваю, что если псевдокод говорит: "найдите мин [бла], такой, что [foo] истинно", то напишите любой код, который вам необходим для выполнения этого, и вставьте его в отдельный метод. Это определенно будет неэффективно, но это будет правильная реализация. Проблема с графовыми алгоритмами заключается в том, что существует 30 способов их реализации, и все они сильно различаются по производительности; страница википедии может только концептуально описать алгоритм. Хорошо, что, как только вы реализуете его каким-то образом, вы можете быстро находить оптимизации ("о, если я буду отслеживать это состояние в этой отдельной структуре данных, я смогу ускорить поиск!"). Кстати, время выполнения этого O(|V|^2), Мне лень детализировать этот анализ, но в основном это потому, что:

1. Вся инициализация O(|V|) в худшем
2. Мы делаем петлю O(|V|) раз и взять O(|V|) время, чтобы просмотреть словарь, чтобы найти минимальный узел. Таким образом, общее время нахождения минимального узла несколько раз O(|V|^2),
3. Время, необходимое для обновления словаря расстояния: O(|E|) потому что мы обрабатываем каждое ребро только один раз. поскольку |E| является O(|V|^2) это тоже O(|V|^2)
4. Отслеживание родителей O(|V|)
5. Вывод дерева O(|V| + |E|) = O(|E|) в худшем случае
6. Добавляя все это (ни один из них не должен быть умножен, кроме как в (2)) мы получим O(|V|^2)

Реализация с кучей есть O(|E|log(|V|) и это очень очень похоже на вышесказанное. Единственная разница в том, что обновление расстояния O(log|V|) вместо O(1) (потому что это куча), НО поиск / удаление элемента min O(log|V|) вместо O(|V|) (потому что это куча). Временная сложность в анализе очень похожа, и в итоге получается что-то вроде O(|V|log|V| + |E|log|V|) = O(|E|log|V|) по желанию.

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