Алгоритм можно представить в виде последовательности из 7 пунктов (этапов). Он справедлив как для неориентированных, так и ориентированных графов.
1. Все ребра (дуги) перенумеровываются от 1 до m, где m – число ребер (дуг) в графе.
2. Составляются различные перестановки последовательностей ребер (дуг), например, для трех ребер в графе последовательности
1 – d1, d2, d3; 2 – d1, d3, d2; 3 – d2, d1 d3;
4 – d2, d3, d1; 5 – d3, d1, d2; 6 – d3, d2, d1.
3. Выбрав определенную последовательность, строим дерево (для неориентированного графа – сильно связный граф без циклов, для ориентированного графа не должно быть двух путей в одну вершину). Если очередное ребро (дуга) увеличивает дерево, т.е. увеличивает число ребер (дуг) в нем, то оно включается в дерево. Если же оно приводит к образованию цикла (в случае неориентированного графа) или образует два пути в одну вершину (для ориентированного графа), то данное ребро (дуга) вычеркивается из списка данной последовательности и вносится в список «Пропущенное ребро (дуга)».
4. После каждого включения ребра (дуги) в дерево просматривается список «Пропущенное ребро». После использования в дереве пропущенного ребра (дуги) оно вычеркивается из списка «Пропущенное ребро». Ребро (дуга) вычеркивается из списка «Пропущенное ребро» также и в том случае, если пропущенное ребро (дуга) приводит к образованию цикла (для неориентированного графа) или к двум путям в вершину (для ориентированного графа).
|
|
5. Пункты 3,4 повторяются до тех пор, пока не будут просмотрены все ребра (дуги) данной последовательности. Для ориентированного графа необходимо убедиться, что полученное дерево есть остовное дерево графа, т.е. из вершины-корня достижимы все вершины графа.
6. Полученное остовное дерево сравнить с имеющимися и, если нет повторения, занести в память (список деревьев).
7. Если число остовных деревьев меньше максимального (п.3.5.2), то перейти к п.3.
Определение кратчайшего остова неориентированного