Ребер или дуг

Алгоритм можно представить в виде последовательности из 7 пунктов (этапов). Он справедлив как для неориентированных, так и ориентированных графов.

1. Все ребра (дуги) перенумеровываются от 1 до m, где m – число ребер (дуг) в графе.

2. Составляются различные перестановки последовательностей ребер (дуг), например, для трех ребер в графе последовательности

1 – d₁, d₂, d₃; 2 – d₁, d₃, d₂; 3 – d₂, d₁ d₃;

4 – d₂, d₃, d₁; 5 – d₃, d₁, d₂; 6 – d₃, d₂, d₁.

3. Выбрав определенную последовательность, строим дерево (для неориентированного графа – сильно связный граф без циклов, для ориентированного графа не должно быть двух путей в одну вершину). Если очередное ребро (дуга) увеличивает дерево, т.е. увеличивает число ребер (дуг) в нем, то оно включается в дерево. Если же оно приводит к образованию цикла (в случае неориентированного графа) или образует два пути в одну вершину (для ориентированного графа), то данное ребро (дуга) вычеркивается из списка данной последовательности и вносится в список «Пропущенное ребро (дуга)».

4. После каждого включения ребра (дуги) в дерево просматривается список «Пропущенное ребро». После использования в дереве пропущенного ребра (дуги) оно вычеркивается из списка «Пропущенное ребро». Ребро (дуга) вычеркивается из списка «Пропущенное ребро» также и в том случае, если пропущенное ребро (дуга) приводит к образованию цикла (для неориентированного графа) или к двум путям в вершину (для ориентированного графа).

5. Пункты 3,4 повторяются до тех пор, пока не будут просмотрены все ребра (дуги) данной последовательности. Для ориентированного графа необходимо убедиться, что полученное дерево есть остовное дерево графа, т.е. из вершины-корня достижимы все вершины графа.

6. Полученное остовное дерево сравнить с имеющимися и, если нет повторения, занести в память (список деревьев).

7. Если число остовных деревьев меньше максимального (п.3.5.2), то перейти к п.3.

Определение кратчайшего остова неориентированного