58. Стягивающие деревья. Нахождение стягивающего дерева методом поиска в ширину

Для про­извольного неориентированного графа G = <V, Е> каждое дерево <V, Т>, где ТсЕ, будем называть стягиваю­щим деревом или каркасом графа G. Ребра такого графа (дерева) назовем ветвями, а остальные ребра графа G будем называть хордами.

Поиск в ширину. О(n+m)

1.BEGIN

2.FOR uV DO НОВЫЙ[u] := true; {инициализация}

3.T :=; {множество найденных к этому времени ветвей}

4.ОЧЕРЕДЬ := ; ОЧЕРЕДЬ  r;

5. НОВЫЙ[r] := false; {г - корень стягивающего дерева}

6.WHILE ОЧЕРЕДЬ DO BEGIN

7.v <= ОЧЕРЕДЬ;

8.FOR u СПИСОК[u] DO

9.IF НОВЫЙ[u] THEN BEGIN

10.ОЧЕРЕДЬ <= и; НОВЫЙ[u] := false; Т := Т {v, u}

END END END return T

59. Стягивающие деревья. Нахождение стягивающего дерева методом поиска в глубину.

Для про­извольного неориентированного графа G = <V, Е> каждое дерево <V, Т>, где ТсЕ, будем называть стягиваю­щим деревом или каркасом графа G. Ребра такого графа (дерева) назовем ветвями, а остальные ребра графа G будем называть хордами.

В глубину. С(n+m)

исходный граф G = <V, E> задан списками инцидентности.

Алгоритм DFS-T(G)

1. For each v do Mark[v]<-0

2.T 3.dfst(v0)

Dfst(v)1.Mark[v]1

2.for each wV, смеж. С v do

3.if Mark[v]=0 then

4.TT{(v,w)}

5.dfst(w)

6.end if;end for

60.Минимальные покрывающие деревья. Алгоритм Прима

Остовным(покрывающим) деревом называется подграф, не содержащий циклов, включающий все вершины исходного графа, для которого сумма весов ребер минимальна. Минимальное остовное дерево в связанном, взвешенном, неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер. В методе Прима от исходного графа переходим к его представлению в виде матрицы смежности. На графе выбирается произвольная вершина. Выбранная вершина образует первоначальный фрагмент остовного дерева. Затем анализируются веса ребер от выбранной вершины до оставшихся невыбранных вершин. Выбирается минимальное ребро, которое указывает на следующую выбранную вершину, и т.д. процесс продолжается до тех пор, пока в остновное дерево не будут включены все вершины исходного графа.

Алгоритм Prim(G,T)

1.T ; w {v0};

2.while wv do

3.среди ребер, соед. W и V-W найти ребро (w,v) с наименьшим весом; 4.TT{(w,v)};5.WV{v};

6.end while;

7.return T

61.Минимальные покрывающие деревья. Алгоритм Крускала.

Остовным (покрывающим) деревом называется подграф, не содержащий циклов, включающий все вершины исходного графа, для которого сумма весов ребер минимальна. Минимальное остовное дерево в связанном, взвешенном, неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер. Алгоритм Крускала. Вычислительная сложность: Сортировка(mlogn), Основная часть(n²). Первоначально каждая вершина(v1,v2…) исходного графа помещается в одноэлементное множество, где все вершины изолированы (поэтому считается что множество W­_s­ имеет вид: W_s={{v₁},{v₂},…,{v_n}}. Ребра сортируются по возрастанию. Ребро включается в остовное дерево, если оно связывает вершины, принадлежащие разным множествам. Алгоритм заканчивает работу, когда все вершины объединяются в одно множество, при этом оставшиеся ребра не включаются в оставное дерево. E-количества ребер,V-вершин.

Алгоритм Kruskal(G)

1.for each v_­iV do Mark[v_i]I;

2.T<-; L_ESort[E];

3.while |T|<|v|-1 do

4.(v,w)min(L_E)

5.if Mark[v]Mark[w] then

6.TT{(v,w)};

7.zMark[w];

8.for each uV do

9.if Mark[u]=z then

10.Mark[u]Mark[v] end if;

11.end for;

12.end if;

13.L_E L_E –{(v,w)};

14.end while.