Основные пункты алгоритма Краскала

1. Для всех пар вершин полного подграфа по уравнению (3) и (4) рассчитываем длины соединяющих их рёбер , где
2. Упорядочиваем рёбра графа по возрастанию их длин
3. Последовательно просматриваем множество U` и соединяем вершины теми рёбрами, которые не образуют цикла с рёбрами уже вошедшими в дерево.
4. Конец работы алгоритма.

Пример:

Алгоритм Прима:

Использует тот же принцип, что и алгоритм Краскала. Но на каждом шаге строящемуся дереву присоединяется ближайшая изолированная вершина.

Исходные данные:

1. Находим минимальный элемент матрицы . Номера строки и столбца (q и p), на пересечении которых он находится, определяются номера вершин соединяемых ребром.
2. Заносим номера вершин в множество , а построенное дерево в множество
3. Подсчитываем число ветвей , принадлежащих на данном шаге вершинам.
4. Для соединяемых вершин проверяем условие: . Индексы вершин, для которых условия выполняются заносим в множество .
5. Находим следующий элемент матрицы , т.е. среди ещё не вошедших в дерево вершин, находим вершину , минимально-удалённую от вершины дерева .
6. Дополняем множество
7. Проверяем, все ли вершины графа соединены ветвями. , если “ДА”, то на пункт 8, “ИНАЧЕ” на пункт 3.
8. Конец работы алгоритма.

Дата добавления: 2014-01-20