С#. Алгоритм Прима (lazy вариант)

Git

Своими словами.

Обходятся все вершины. Для каждой вершины выбираются инцидентные ребра.

Просматриваются противоположные вершины инцидентных ребер и добавляются в очередь.

Просматривается очередь и выбирается ребро с наименьшим весом.  Оно добавляется в финальную очередь.

Также должна быть проверка на то, что дерево это дерево, то есть Ациклический граф, поэтому если в нашем дереве есть 2 вершины, соединенные ребром, то такие ребра надо исключать.

Но есть 2 реализации алгоритма Прима – ленивая (ребра, образующие циклы не исключаются сразу) и энергичная (ребра, образующие циклы, исключаются сразу)

Теперь немного теории из Сэйджвика

 

 

 

Теперь немного кода на C#

Попробуем этот алгоритм на таком графе

Вот тестовый клиент

 

А вот и результат

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

This entry was posted in C#. Bookmark the permalink.