368 369

368 Programowanie sieciowe

8.2.1. Reguły postępowania przy poszukiwaniu minimalnego drzewa rozpinającego

Iteracja 1

Wybieramy w sposób arbitralny dowolny wierzchołek i łączymy go z wierzchołkiem leżącym najbliżej.

Iteracja k (k = 2, n- 1)

W konstruowanym drzewie znajduje się już k wierzchołków i k- 1 łączących je krawędzi. Wierzchołki te nazywamy wierzchołkami połączonymi, pozostałe tworzą zbiór wierzchołków niepołączonych. Identyfikujemy najbliższy zbiorowi wierzchołków połączonych wierzchołek niepołączony i dołączamy go do zbioru wierzchołków połączonych. Krok ten wykonujemy tak długo, aż do zbioru wierzchołków połączonych dołączymy ostatni wierzchołek niepołączony.

8.2.2. Kolejne iteracje

Prześledzimy przebieg kolejnych iteracji dla zadania sformułowanego w przykładzie 8.1.

Iteracja 1

Algorytm minimalnego drzewa rozpinającego możemy rozpocząć od dowolnego wierzchołka. W rozważanym przez nas przykładzie najbardziej naturalne jest

Rysunek 8.2

rozpoczęcie od wierzchołka 1, odpowiadającego nowo powstającemu centrum komputerowemu (rys. 8.1). W celu zidentyfikowania najbliższego wierzchołka rozpatrujemy wszystkie wierzchołki połączone z wierzchołkiem 1 i wybieramy krawędź prowadzącą do najbliższego wierzchołka. Jest nią krawędź 1-2 (rys. 8.2).

Iteracja 2

Skonstruowany przez nas fragment drzewa zawiera wierzchołki 1 i 2 (są to wierzchołki połączone) oraz łączącą je krawędź 1-2. Do drzewa nie należą wierzchołki: 3, 4, 5 i 6 (wierzchołki niepołączone). Identyfikujemy wszystkie połączenia od wierzchołków połączonych do wierzchołków niepołączonych. Są to krawędzie: 1-3, 1-4, 2-3, 2-5, 2-6. Wybieramy jedną z. krawędzi o najmniejszej długości — mając wybór między krawędziami 2-3 oraz 2-5, arbitralnie wybieramy tę pierwszą możliwość. Przebieg iteracji ilustruje rys. 8.3.

Rysunek 8.3

Iteracja 3

Wierzchołkami połączonymi są wierzchołki 1,2, 3 oraz krawędzie 1-2 i 2-3. Do zbioru wierzchołków niepołączonych zaliczamy: 4, 5 i 6. Identyfikujemy ponownie wszystkie połączenia od wierzchołków połączonych do wierzchołków niepołączonych — są to krawędzie 1-4, 2-5, 2-6, 3-4, 3-5, 3-6. Ponownie mamy możliwość wyboru między dwoma najkrótszymi krawędziami — są to krawędzie 3-4 oraz 3-6. Wybieramy krawędź 3-4. Przebieg iteracji 3 ilustruje rys. 8.4.