Serwis Edukacyjny w I-LO w Tarnowie ![]() Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2023 mgr Jerzy Wałaszek |
ProblemDla danego spójnego i nieskierowanego grafu ważonego należy wyznaczyć minimalne drzewo rozpinające. Drzewo rozpinające ( ang. Spanning Tree ) grafu jest drzewem, które zawiera wszystkie wierzchołki grafu oraz niektóre z jego krawędzi ( drzewa nie zawierają cykli ). Minimalne drzewo rozpinające ( ang. Minimum Spanning Tree ) jest drzewem rozpinającym, którego suma wag krawędzi jest najmniejsza ze wszystkich pozostałych drzew rozpinających danego grafu. W danym grafie może istnieć kilka drzew o tych własnościach. Wystarczy wskazać jedno z nich. Istnieje kilka sposobów rozwiązania tego problemu. My omówimy dwa: algorytm Kruskala i algorytm Prima. |
Idea algorytmu Kruskala jest następująca:
Tworzymy pusty zbiór krawędzi T oraz listę L wszystkich krawędzi grafu uporządkowaną według rosnących wag.
Dopóki w T nie mamy wszystkich wierzchołków grafu, wybieramy z listy L krawędź i, jeśli nie tworzy ona cyklu z krawędziami już obecnymi w T, dodajemy ją do zbioru T.
Gdy algorytm zakończy pracę, w T będzie minimalne drzewo rozpinające.
W poniższej tabelce podajemy przykład znajdowania minimalnego drzewa rozpinającego za pomocą algorytmu Kruskala.
![]() |
|
|
Oto nasz graf ważony, dla którego mamy znaleźć minimalne drzewo rozpinające. Tworzymy pusty zbiór krawędzi T oraz uporządkowaną wg rosnących wag listę L krawędzi grafu. | ||||
![]() |
|
|
Pobieramy z listy L krawędź 4–6:1 i
dodajemy ją do zbioru T. Krawędź ta będzie należała do minimalnego
drzewa rozpinającego. Suma wag = 1 |
||||
![]() |
|
|
Pobieramy z L kolejną krawędź
4–5:2
i dodajemy ją do zbioru T. Suma wag = 1 + 2 = 3 |
||||
![]() |
|
|
Pobieramy z L krawędź 2–7:3 i dołączamy
do T. Suma wag = 1 + 2 + 3 = 6 |
||||
![]() |
|
|
Pobieramy z L krawędź 0–6:3 i dołączamy
do T. Suma wag = 1 + 2 + 3 + 3 = 9 |
||||
![]() |
|
|
Pobieramy z L krawędź 2–4:4 i dołączamy
do T. Suma wag = 1 + 2 + 3 + 3 + 4 = 13 |
||||
![]() |
|
|
Pobieramy z L krawędź 0–1:5 i dołączamy
do T. Suma wag = 1 + 2 + 3 + 3 + 4 + 5 = 18
|
||||
![]() |
|
|
Pobieramy z L krawędzie: 2–6:5, 1–5:6, 5–6:6, 1–7:7 i 1–4:8, lecz nie dodajemy ich do T, ponieważ utworzyłyby one cykle z krawędziami już obecnymi w T. | ||||
![]() |
|
|
Pobieramy z L krawędź 3–6:8 i dołączamy
do T. Suma wag = 1 + 2 + 3 + 3 + 4 + 5 + 8 = 26 |
||||
![]() |
|
|
Zbiór T obejmuje wszystkie wierzchołki grafu, otrzymaliśmy minimalne drzewo rozpinające o sumie wag krawędzi równej 26. |
Aby zrealizować praktycznie ten algorytm, musimy dobrać odpowiednie struktury danych do wykonywanych w algorytmie operacji.
Lista L musi być posortowana. Można tutaj wykorzystać zwykłą listę, dodać do niej wszystkie krawędzie grafu i posortować ją rosnąco względem ich wag. Lepszym rozwiązaniem może okazać się odpowiednio skonstruowana kolejka priorytetowa, która będzie przechowywać krawędzie w kolejności od najmniejszej do największej wagi. Można tutaj wykorzystać kolejkę opartą na kopcu.
Algorytm wymaga sprawdzania, czy dodawana do T krawędź nie tworzy cyklu z krawędziami, które już znajdują się w T. Wykrywanie cyklu jest czasochłonne. Lepszym rozwiązaniem będzie zastosowanie struktury zbiorów rozłącznych, w której będziemy przechowywać wierzchołki grafu. Przed dodaniem krawędzi u–v do T sprawdzamy, czy wierzchołki u i v znajdują się w rozłącznych zbiorach. Jeśli tak, to zbiory te łączymy operacją UnionSets ( u, v ) i krawędź dodajemy do T. Jeśli nie, to oznacza to, iż u oraz v należą do tej samej spójnej składowej i dodanie krawędzi spowodowałoby powstanie cyklu. W takim przypadku krawędź odrzucamy.
n | – | liczba wierzchołków w grafie, n ∈ C. |
graf | – | zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. Graf musi być spójny. |
Q | – | kolejka priorytetowa. Elementami są krawędzie wraz z wagami. Pierwszy element posiada najniższą wagę. Kolejka powinna pomieścić wszystkie krawędzie grafu. |
Z | – | Struktura zbiorów rozłącznych. Elementami są numery wierzchołków grafu. |
u, v | – | numery wierzchołków w grafie, u, v ∈ C . |
w | – | waga krawędzi, w ∈ R. |
MakeSet ( x ) | – | tworzy jednoelementowy zbiór zawierający x. |
FindSet ( x ) | – | zwraca reprezentanta zbioru z x. |
UnionSets ( x, y ) | – | łączy ze sobą zbiory zawierające x i y. |
K01: | Utwórz n elementową
strukturę zbiorów rozłącznych Z |
|
K02: | Utwórz pustą kolejkę Q | |
K03: | Utwórz pusty zbiór T | zbiór dla minimalnego drzewa rozpinającego |
K04: | Dla v = 0, 1, ...,
n - 1: wykonuj kroki K05...K06 |
przeglądamy kolejne wierzchołki grafu |
K05: | MakeSet ( Z [ v ] ) | tworzymy zbiory rozłączne, po jednym dla każdego wierzchołka |
K06: | Dla każdego
sąsiada u wierzchołka v : wykonuj: Q.push ( v–u:w ) |
przeglądamy sąsiadów wierzchołka v i w kolejce Q umieszczamy krawędzie wraz z ich wagami |
K07: | Dla i = 1, 2, ...,
n
- 1: wykonuj kroki K08...K11 |
główną pętlę wykonujemy n-1 razy |
K08: | v–u:w ← Q.front( ); Q.pop( ) | pobieramy krawędź z początku kolejki |
K09: | Jeśli FindSet
( Z [ v ] ) = FindSet ( Z [ u
] ), to idź do kroku K08 |
sprawdzamy, czy u i v leżą w różnych składowych w drzewie T |
K10: | Dodaj v–u:w do T | jeśli tak, to krawędź dodajemy do drzewa T |
K11: | UnionSets ( Z [ u ], Z [ v ] ) | a zbiory z u i v łączymy ze sobą |
K12: | Zakończ z wynikiem T |
Uwaga:
Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program odczytuje definicję spójnego, ważonego grafu nieskierowanego i wyznacza dla niego minimalne drzewo rozpinające algorytmem Kruskala. |
Dane przykładowe (przekopiuj do
schowka i wklej do okna konsoli ):
|
Pascal// Minimalne drzewo rozpinające // Algorytm Kruskala // Data: 6.04.2014 // (C)2014 mgr Jerzy Wałaszek //-------------------------------- // Definicja obiektu kolejki priorytetowej //---------------------------------------- type Edge = record v1, v2 : integer; // Wierzchołki krawędzi weight : integer; // Waga krawędzi end; Queue = object private Heap : array of Edge; hpos : integer; public constructor init ( n : integer ); destructor destroy; function front : Edge; procedure push ( e : Edge ); procedure pop; end; // Definicja obiektu struktury zbiorów rozłącznych //------------------------------------------------ DSNode = record up : integer; rank : integer; end; DSStruct = object private Z : array of DSNode; public constructor init ( n : integer ); destructor destroy; procedure MakeSet ( v : integer ); function FindSet ( v : integer ) : integer; procedure UnionSets ( e : Edge ); end; // Definicja obiektu minimalnego drzewa rozpinającego //--------------------------------------------------- PTNode = ^TNode; TNode = record next : PTNode; v : integer; weight : integer; end; MSTree = object private A : array of PTNode; // Tablica list sąsiedztwa Alen : integer; // Liczba komórek w tablicy weight : integer; // Waga całego drzewa public constructor init ( n : integer ); destructor destroy; procedure addEdge ( e : Edge ); procedure print; end; // Definicje metod obiektu Queue //------------------------------ // Konstruktor - tworzy n elementową tablicę heap na kopiec //--------------------------------------------------------- constructor Queue.init ( n : integer ); begin SetLength ( Heap, n ); // Tworzymy tablicę hpos := 0; // Pozycja w kopcu end; // Destruktor - usuwa kopiec z pamięci //------------------------------------ destructor Queue.destroy; begin SetLength ( Heap, 0 ); end; // Zwraca krawędź z początku kopca //-------------------------------- function Queue.front : Edge; begin front := Heap [ 0 ]; end; // Umieszcza w kopcu nową krawędź i odtwarza strukturę kopca //---------------------------------------------------------- procedure Queue.push ( e : Edge ); var i, j : integer; begin i := hpos; // i ustawiamy na koniec kopca inc ( hpos ); // W kopcu będzie o 1 element wiecej j := ( i - 1 ) Shr 1; // Obliczamy pozycję rodzica // Szukamy miejsca w kopcu dla e while( i > 0 ) and ( Heap [ j ].weight > e.weight ) do begin Heap [ i ] := Heap [ j ]; i := j; j := ( i - 1 ) Shr 1; end; Heap [ i ] := e; // Krawędź e wstawiamy do kopca end; // Usuwa korzeń z kopca i odtwarza jego strukturę //----------------------------------------------- procedure Queue.pop; var i, j : integer; e : Edge; begin if hpos > 0 then begin dec ( hpos ); e := Heap [ hpos ]; i := 0; j := 1; while j < hpos do begin if( j + 1 < hpos ) and ( Heap [ j + 1 ].weight < Heap [ j ].weight ) then inc ( j ); if e.weight <= Heap [ j ].weight then break; Heap [ i ] := Heap [ j ]; i := j; j := ( j Shl 1 ) + 1; end; Heap [ i ] := e; end; end; // Definicje metod obiektu DSStruct //--------------------------------- // Konstruktor constructor DSStruct.init ( n : integer ); begin SetLength ( Z, n ); // Tworzymy tablicę dla elementów zbiorów end; // Destruktor //----------- destructor DSStruct.destroy; begin SetLength ( Z, 0 ); // Usuwamy tablicę ze zbiorami end; // Tworzy wpis w tablicy Z //------------------------ procedure DSStruct.MakeSet ( v : integer ); begin Z [ v ].up := v; Z [ v ].rank := 0; end; // Zwraca indeks reprezentanta zbioru, w którym jest wierzchołek v //---------------------------------------------------------------- function DSStruct.FindSet ( v : integer ) : integer; begin if Z [ v ].up <> v then Z [ v ].up := FindSet ( Z [ v ].up ); FindSet := Z [ v ].up; end; // Łączy ze sobą zbiory z v i u //----------------------------- procedure DSStruct.UnionSets ( e : Edge ); var ru, rv : integer; begin ru := FindSet ( e.v1 ); // Wyznaczamy korzeń drzewa z węzłem u rv := FindSet ( e.v2 ); // Wyznaczamy korzeń drzewa z węzłem v if ru <> rv then // Korzenie muszą być różne begin if Z [ ru ].rank > Z [ rv ].rank then // Porównujemy rangi drzew Z [ rv ].up := ru // ru większe, dołączamy rv else begin Z [ ru ].up := rv; // równe lub rv większe, dołączamy ru if Z [ ru ].rank = Z [ rv ].rank then inc ( Z [ rv ].rank ); end; end; end; // Definicje metod obiektu MSTree //------------------------------- // Konstruktor - tworzy tablicę pustych list sąsiedztwa //----------------------------------------------------- constructor MSTree.init ( n : integer ); var i : integer; begin SetLength ( A, n ); // Tworzymy tablicę dynamiczną for i := 0 to n - 1 do A [ i ] := nil; // i wypełniamy ją pustymi listami Alen := n - 1; // Zapamiętujemy długość tablicy weight := 0; // Zerujemy wagę drzewa end; // Destruktor - usuwa listy oraz tablicę sąsiedztwa //------------------------------------------------- destructor MSTree.destroy; var i : integer; p, r : PTNode; begin for i := 0 to Alen do begin p := A [ i ]; while p <> nil do begin r := p; // Zapamiętujemy wskazanie p := p^.next; // Przesuwamy się do następnego elementu listy dispose ( r ); // Usuwamy element end; end; SetLength ( A, 0 ); // Usuwamy tablicę list sąsiedztwa end; // Dodaje krawędź do drzewa //------------------------- procedure MSTree.addEdge ( e : Edge ); var p : PTNode; begin inc ( weight, e.weight ); // Do wagi drzewa dodajemy wagę krawędzi new ( p ); // Tworzymy nowy węzeł p^.v := e.v2; // Wierzchołek końcowy p^.weight := e.weight; // Waga krawędzi p^.next := A [ e.v1 ]; // Dodajemy p do listy wierzchołka v1 A [ e.v1 ] := p; new ( p ); // To samo dla krawędzi odwrotnej p^.v := e.v1; // Wierzchołek końcowy p^.weight := e.weight; // Waga krawędzi p^.next := A [ e.v2 ]; // Dodajemy p do listy wierzchołka v2 A [ e.v2 ] := p; end; // Wyświetla zawartość drzewa oraz jego wagę //------------------------------------------ procedure MSTree.print; var i : integer; p : PTNode; begin writeln; for i := 0 to Alen do begin write ( 'Vertex ', i, ' - ' ); p := A [ i ]; while p <> nil do begin write ( p^.v, ':', p^.weight, ' ' ); p := p^.next; end; writeln; end; writeln; writeln ( 'Minimal Spanning Tree Weight = ', weight ); writeln; end; // ********************** // *** PROGRAM GŁÓWNY *** // ********************** var n, m : integer; // Liczba wierzchołków i krawędzi e : Edge; i : integer; Z : DSStruct; // Struktura zbiorów rozłącznych Q : Queue; // Kolejka priorytetowa oparta na kopcu T : MSTree; // Minimalne drzewo rozpinające begin read ( n, m ); // Czytamy liczbę wierzchołków i krawędzi Z.init ( n ); // Inicjujemy strukturę zbiorów rozłącznych Q.init ( m ); // Inicjujemy kolejkę priorytetową T.init ( n ); // Inicjujemy minimalne drzewo rozpinające for i := 0 to n - 1 do Z.MakeSet ( i ); // Dla każdego wierzchołka tworzymy osobny zbiór for i := 1 to m do begin read ( e.v1, e.v2, e.weight ); // Odczytujemy kolejne krawędzie grafu Q.push ( e ); // i umieszczamy je w kolejce priorytetowej end; for i := 1 to n - 1 do begin repeat e := Q.front; // Pobieramy z kolejki krawędź Q.pop; // Krawędź usuwamy z kolejki until Z.FindSet ( e.v1 ) <> Z.FindSet ( e.v2 ); T.addEdge ( e ); // Dodajemy krawędź do drzewa Z.UnionSets ( e ); // Zbiory z wierzchołkami łączymy ze sobą end; // Wyświetlamy wyniki T.print; // Usuwamy struktury Z.destroy; Q.destroy; T.destroy; end. |
C++// Minimalne drzewo rozpinające // Algorytm Kruskala // Data: 6.04.2014 // (C)2014 mgr Jerzy Wałaszek //-------------------------------- #include <iostream> using namespace std; // Definicja obiektu kolejki priorytetowej //---------------------------------------- struct Edge { int v1, v2, weight; // Wierzchołki krawędzi, waga krawędzi }; class Queue { private: Edge * Heap; int hpos; public: Queue ( int n ); ~Queue( ); Edge front( ); void push ( Edge e ); void pop( ); }; // Definicja obiektu struktury zbiorów rozłącznych //------------------------------------------------ struct DSNode { int up, rank; }; class DSStruct { private: DSNode * Z; public: DSStruct ( int n ); ~DSStruct( ); void MakeSet ( int v ); int FindSet ( int v ); void UnionSets ( Edge e ); }; // Definicja obiektu minimalnego drzewa rozpinającego //--------------------------------------------------- struct TNode { TNode * next; int v, weight; }; class MSTree { private: TNode ** A; // Tablica list sąsiedztwa int Alen; // Liczba komórek w tablicy int weight; // Waga całego drzewa public: MSTree ( int n ); ~MSTree( ); void addEdge ( Edge e ); void print( ); }; // Definicje metod obiektu Queue //------------------------------ // Konstruktor - tworzy n elementową tablicę heap na kopiec //--------------------------------------------------------- Queue::Queue ( int n ) { Heap = new Edge [ n ]; // Tworzymy tablicę hpos = 0; // Pozycja w kopcu } // Destruktor - usuwa kopiec z pamięci //------------------------------------ Queue::~Queue( ) { delete [ ] Heap; } // Zwraca krawędź z początku kopca //-------------------------------- Edge Queue::front( ) { return Heap [ 0 ]; } // Umieszcza w kopcu nową krawędź i odtwarza strukturę kopca //---------------------------------------------------------- void Queue::push ( Edge e ) { int i, j; i = hpos++; // i ustawiamy na koniec kopca j = ( i - 1 ) >> 1; // Obliczamy pozycję rodzica // Szukamy miejsca w kopcu dla e while( i && ( Heap [ j ].weight > e.weight ) ) { Heap [ i ] = Heap [ j ]; i = j; j = ( i - 1 ) >> 1; } Heap [ i ] = e; // Krawędź e wstawiamy do kopca } // Usuwa korzeń z kopca i odtwarza jego strukturę //----------------------------------------------- void Queue::pop( ) { int i, j; Edge e; if( hpos ) { e = Heap [ --hpos ]; i = 0; j = 1; while( j < hpos ) { if( ( j + 1 < hpos ) && ( Heap [ j + 1 ].weight < Heap [ j ].weight ) ) j++; if( e.weight <= Heap [ j ].weight ) break; Heap [ i ] = Heap [ j ]; i = j; j = ( j << 1 ) + 1; } Heap [ i ] = e; } } // Definicje metod obiektu DSStruct //--------------------------------- // Konstruktor DSStruct::DSStruct ( int n ) { Z = new DSNode [ n ]; // Tworzymy tablicę dla elementów zbiorów } // Destruktor //----------- DSStruct::~DSStruct( ) { delete [ ] Z; // Usuwamy tablicę ze zbiorami } // Tworzy wpis w tablicy Z //------------------------ void DSStruct::MakeSet ( int v ) { Z [ v ].up = v; Z [ v ].rank = 0; } // Zwraca indeks reprezentanta zbioru, w którym jest wierzchołek v //---------------------------------------------------------------- int DSStruct::FindSet ( int v ) { if( Z [ v ].up != v ) Z [ v ].up = FindSet ( Z [ v ].up ); return Z [ v ].up; } // Łączy ze sobą zbiory z v i u //----------------------------- void DSStruct::UnionSets ( Edge e ) { int ru, rv; ru = FindSet ( e.v1 ); // Wyznaczamy korzeń drzewa z węzłem u rv = FindSet ( e.v2 ); // Wyznaczamy korzeń drzewa z węzłem v if( ru != rv ) // Korzenie muszą być różne { if( Z [ ru ].rank > Z [ rv ].rank ) // Porównujemy rangi drzew Z [ rv ].up = ru; // ru większe, dołączamy rv else { Z [ ru ].up = rv; // równe lub rv większe, dołączamy ru if( Z [ ru ].rank == Z [ rv ].rank ) Z [ rv ].rank++; } } } // Definicje metod obiektu MSTree //------------------------------- // Konstruktor - tworzy tablicę pustych list sąsiedztwa //----------------------------------------------------- MSTree::MSTree ( int n ) { int i; A = new TNode * [ n ]; // Tworzymy tablicę dynamiczną for( i = 0; i < n; i++ ) A [ i ] = NULL; // i wypełniamy ją pustymi listami Alen = n - 1; // Zapamiętujemy długość tablicy weight = 0; // Zerujemy wagę drzewa } // Destruktor - usuwa listy oraz tablicę sąsiedztwa //------------------------------------------------- MSTree::~MSTree( ) { int i; TNode *p, *r; for( i = 0; i <= Alen; i++ ) { p = A [ i ]; while( p ) { r = p; // Zapamiętujemy wskazanie p = p->next; // Przesuwamy się do następnego elementu listy delete r; // Usuwamy element } } delete [ ] A; // Usuwamy tablicę list sąsiedztwa } // Dodaje krawędź do drzewa //------------------------- void MSTree::addEdge ( Edge e ) { TNode *p; weight += e.weight; // Do wagi drzewa dodajemy wagę krawędzi p = new TNode; // Tworzymy nowy węzeł p->v = e.v2; // Wierzchołek końcowy p->weight = e.weight; // Waga krawędzi p->next = A [ e.v1 ]; // Dodajemy p do listy wierzchołka v1 A [ e.v1 ] = p; p = new TNode; // To samo dla krawędzi odwrotnej p->v = e.v1; // Wierzchołek końcowy p->weight = e.weight; // Waga krawędzi p->next = A [ e.v2 ]; // Dodajemy p do listy wierzchołka v2 A [ e.v2 ] = p; } // Wyświetla zawartość drzewa oraz jego wagę //------------------------------------------ void MSTree::print( ) { int i; TNode *p; cout << endl; for( i = 0; i <= Alen; i++ ) { cout << "Vertex " << i << " - "; for( p = A [ i ]; p; p = p->next ) cout << p->v << ":" << p->weight << " "; cout << endl; } cout << endl << endl << "Minimal Spanning Tree Weight = " << weight << endl << endl; } // ********************** // *** PROGRAM GŁÓWNY *** // ********************** int main( ) { int n, m; // Liczba wierzchołków i krawędzi Edge e; int i; cin >> n >> m; // Czytamy liczbę wierzchołków i krawędzi DSStruct Z ( n ); // Struktura zbiorów rozłącznych Queue Q ( m ); // Kolejka priorytetowa oparta na kopcu MSTree T ( n ); // Minimalne drzewo rozpinające for( i = 0; i < n; i++ ) Z.MakeSet ( i ); // Dla każdego wierzchołka tworzymy osobny zbiór for( i = 0; i < m; i++ ) { cin >> e.v1 >> e.v2 >> e.weight; // Odczytujemy kolejne krawędzie grafu Q.push ( e ); // i umieszczamy je w kolejce priorytetowej } for( i = 1; i < n; i++ ) // Pętla wykonuje się n - 1 razy !!! { do { e = Q.front( ); // Pobieramy z kolejki krawędź Q.pop( ); // Krawędź usuwamy z kolejki } while( Z.FindSet ( e.v1 ) == Z.FindSet ( e.v2 ) ); T.addEdge ( e ); // Dodajemy krawędź do drzewa Z.UnionSets ( e ); // Zbiory z wierzchołkami łączymy ze sobą } // Wyświetlamy wyniki T.print( ); return 0; } |
Basic' Minimalne drzewo rozpinające ' Algorytm Kruskala ' Data: 6.04.2014 ' (C)2014 mgr Jerzy Wałaszek '-------------------------------- ' Definicja obiektu kolejki priorytetowej '---------------------------------------- Type Edge v1 As Integer ' Wierzchołki krawędzi, waga krawędzi v2 As Integer weight As Integer End Type Type Queue Private: Heap As Edge Ptr hpos As Integer Public: Declare Constructor ( ByVal n As Integer ) Declare Destructor( ) Declare Function front( ) As Edge Declare Sub push ( ByVal e As Edge ) Declare Sub pop( ) End Type ' Definicja obiektu struktury zbiorów rozłącznych '------------------------------------------------ Type DSNode up As Integer rank As Integer End Type Type DSStruct Private: Z As DSNode Ptr Public: Declare Constructor ( ByVal n As Integer ) Declare Destructor( ) Declare Sub MakeSet ( ByVal v As Integer ) Declare Function FindSet ( ByVal v As Integer ) As Integer Declare Sub UnionSets ( ByVal e As Edge ) End Type ' Definicja obiektu minimalnego drzewa rozpinającego '--------------------------------------------------- Type TNode Next As TNode Ptr v As Integer weight As Integer End Type Type MSTree Private: A As TNode Ptr Ptr ' Tablica list sąsiedztwa Alen As Integer ' Liczba komórek w tablicy weight As Integer ' Waga całego drzewa Public: Declare Constructor ( ByVal n As Integer ) Declare Destructor( ) Declare Sub addEdge ( ByVal e As Edge ) Declare Sub Tprint( ) End Type ' Definicje metod obiektu Queue '------------------------------ ' Konstruktor - tworzy n elementową tablicę heap na kopiec '--------------------------------------------------------- Constructor Queue ( ByVal n As Integer ) Heap = New Edge [ n ] ' Tworzymy tablicę hpos = 0 ' Pozycja w kopcu End Constructor ' Destruktor - usuwa kopiec z pamięci '------------------------------------ Destructor Queue( ) Delete [ ] Heap End Destructor ' Zwraca krawędź z początku kopca '-------------------------------- Function Queue.front( ) As Edge return Heap [ 0 ] End Function ' Umieszcza w kopcu nową krawędź i odtwarza strukturę kopca '---------------------------------------------------------- Sub Queue.push ( ByVal e As Edge ) Dim As Integer i, j i = hpos ' i ustawiamy na koniec kopca hpos += 1 j = ( i - 1 ) Shr 1 ' Obliczamy pozycję rodzica ' Szukamy miejsca w kopcu dla e while( i > 0 ) AndAlso ( Heap [ j ].weight > e.weight ) Heap [ i ] = Heap [ j ] i = j j = ( i - 1 ) Shr 1 Wend Heap [ i ] = e ' Krawędź e wstawiamy do kopca End Sub ' Usuwa korzeń z kopca i odtwarza jego strukturę '----------------------------------------------- Sub Queue.pop( ) Dim As Integer i, j Dim As Edge e If hpos > 0 Then hpos -= 1 e = Heap [ hpos ] i = 0 j = 1 While j < hpos if( j + 1 < hpos ) AndAlso ( Heap [ j + 1 ].weight < Heap [ j ].weight ) Then j += 1 If e.weight <= Heap [ j ].weight Then Exit While Heap [ i ] = Heap [ j ] i = j j = ( j Shl 1 ) + 1 Wend Heap [ i ] = e End If End Sub ' Definicje metod obiektu DSStruct '--------------------------------- ' Konstruktor Constructor DSStruct ( ByVal n As Integer ) Z = New DSNode [ n ] ' Tworzymy tablicę dla elementów zbiorów End Constructor ' Destruktor '----------- Destructor DSStruct( ) Delete [ ] Z ' Usuwamy tablicę ze zbiorami End Destructor ' Tworzy wpis w tablicy Z '------------------------ Sub DSStruct.MakeSet ( ByVal v As Integer ) Z [ v ].up = v Z [ v ].rank = 0 End Sub ' Zwraca indeks reprezentanta zbioru, w którym jest wierzchołek v '---------------------------------------------------------------- Function DSStruct.FindSet ( ByVal v As Integer ) As Integer If Z [ v ].up <> v Then Z [ v ].up = FindSet ( Z [ v ].up ) return Z [ v ].up End Function ' Łączy ze sobą zbiory z v i u '----------------------------- Sub DSStruct.UnionSets ( ByVal e As Edge ) Dim As Integer ru, rv ru = FindSet ( e.v1 ) ' Wyznaczamy korzeń drzewa z węzłem u rv = FindSet ( e.v2 ) ' Wyznaczamy korzeń drzewa z węzłem v if ru <> rv Then ' Korzenie muszą być różne If Z [ ru ].rank > Z [ rv ].rank Then ' Porównujemy rangi drzew Z [ rv ].up = ru ' ru większe, dołączamy rv Else Z [ ru ].up = rv ' równe lub rv większe, dołączamy ru If Z [ ru ].rank = Z [ rv ].rank Then Z [ rv ].rank += 1 End If End If End Sub ' Definicje metod obiektu MSTree '------------------------------- ' Konstruktor - tworzy tablicę pustych list sąsiedztwa '----------------------------------------------------- Constructor MSTree ( ByVal n As Integer ) Dim As Integer i A = New TNode Ptr [ n ] ' Tworzymy tablicę dynamiczną For i = 0 To n - 1 A [ i ] = 0 ' i wypełniamy ją pustymi listami Next Alen = n - 1 ' Zapamiętujemy długość tablicy weight = 0 ' Zerujemy wagę drzewa End Constructor ' Destruktor - usuwa listy oraz tablicę sąsiedztwa '------------------------------------------------- Destructor MSTree( ) Dim As Integer i Dim As TNode Ptr p, r For i = 0 to Alen p = A [ i ] While p r = p ' Zapamiętujemy wskazanie p = p->Next ' Przesuwamy się do następnego elementu listy Delete r ' Usuwamy element Wend Next Delete [ ] A ' Usuwamy tablicę list sąsiedztwa End Destructor ' Dodaje krawędź do drzewa '------------------------- Sub MSTree.addEdge ( ByVal e As Edge ) Dim As TNode Ptr p weight += e.weight ' Do wagi drzewa dodajemy wagę krawędzi p = New TNode ' Tworzymy nowy węzeł p->v = e.v2 ' Wierzchołek końcowy p->weight = e.weight ' Waga krawędzi p->next = A [ e.v1 ] ' Dodajemy p do listy wierzchołka v1 A [ e.v1 ] = p p = New TNode ' To samo dla krawędzi odwrotnej p->v = e.v1 ' Wierzchołek końcowy p->weight = e.weight ' Waga krawędzi p->next = A [ e.v2 ] ' Dodajemy p do listy wierzchołka v2 A [ e.v2 ] = p End Sub ' Wyświetla zawartość drzewa oraz jego wagę '------------------------------------------ Sub MSTree.Tprint( ) Dim As Integer i Dim As TNode Ptr p Print For i = 0 to Alen Print "Vertex";i;" - "; p = A [ i ] While p Print Using "&:& ";p->v;p->weight; p = p->Next Wend Print Next Print Print "Minimal Spanning Tree Weight =";weight Print End Sub ' ********************** ' *** PROGRAM GŁÓWNY *** ' ********************** Dim As integer n, m ' Liczba wierzchołków i krawędzi Dim As Edge e Dim As Integer i Open Cons For Input As #1 Input #1, n, m ' Czytamy liczbę wierzchołków i krawędzi Dim As DSStruct Z = n ' Struktura zbiorów rozłącznych Dim As Queue Q = m ' Kolejka priorytetowa oparta na kopcu Dim As MSTree T = n ' Minimalne drzewo rozpinające For i = 0 To n - 1 Z.MakeSet ( i ) ' Dla każdego wierzchołka tworzymy osobny zbiór Next For i = 1 To m Input #1, e.v1, e.v2, e.weight ' Odczytujemy kolejne krawędzie grafu Q.push ( e ) ' i umieszczamy je w kolejce priorytetowej Next Close #1 For i = 1 To n - 1 ' Pętla wykonuje się n - 1 razy !!! Do e = Q.front( ) ' Pobieramy z kolejki krawędź Q.pop( ) ' Krawędź usuwamy z kolejki Loop While Z.FindSet ( e.v1 ) = Z.FindSet ( e.v2 ) T.addEdge ( e ) ' Dodajemy krawędź do drzewa Z.UnionSets ( e ) ' Zbiory z wierzchołkami łączymy ze sobą Next ' Wyświetlamy wyniki T.Tprint( ) End |
Wynik: | |
8 16 0 1 5 0 3 9 0 6 3 1 2 9 1 4 8 1 5 6 1 7 7 2 3 9 2 4 4 2 6 5 2 7 3 3 6 8 4 5 2 4 6 1 5 6 6 6 7 9 Vertex 0 - 1:5 6:3 Vertex 1 - 0:5 Vertex 2 - 4:4 7:3 Vertex 3 - 6:8 Vertex 4 - 2:4 5:2 6:1 Vertex 5 - 4:2 Vertex 6 - 3:8 0:3 4:1 Vertex 7 - 2:3 Minimal Spanning Tree Weight = 26 |
![]() |
Drugi algorytm wyznaczania minimalnego drzewa rozpinającego nosi nazwę algorytmu Prima i można go opisać w sposób następujący:
Wybieramy w grafie dowolny wierzchołek startowy.
Dopóki drzewo nie pokrywa całego grafu, znajdujemy krawędź o najniższym koszcie spośród wszystkich krawędzi prowadzących od wybranych już wierzchołków do wierzchołków jeszcze niewybranych. Znalezioną krawędź dodajemy do drzewa rozpinającego.
Przyjrzyjmy się bliżej pracy tego algorytmu:
![]() |
Oto nasz graf ważony, dla którego mamy znaleźć minimalne drzewo rozpinające. |
![]() |
Wybieramy dowolny wierzchołek startowy, np. wierzchołek 0.
Wierzchołek ten posiada trzy krawędzie biegnące do wierzchołków 1, 3
i 6. Spośród nich krawędź do wierzchołka 6 ma najmniejszą wagę i ją
wybieramy dla drzewa rozpinającego. Suma wag = 3 |
![]() |
Spośród wszystkich krawędzi wychodzących z wierzchołków 0 i 6
(wierzchołki już wybrane) do wierzchołków jeszcze
niewybranych krawędź 6–4 ma najmniejszą wagę i ją wybieramy dla
drzewa rozpinającego. Suma wag = 3 + 1 = 4 |
![]() |
Teraz najmniejszą wagę ma krawędź 4–5. Dodajemy ją do drzewa
rozpinającego. Suma wag = 3 + 1 + 2 = 6 |
![]() |
Najmniejszą wagę ma krawędź 4–2. Dodajemy ją do drzewa
rozpinającego. Suma wag = 3 + 1 + 2 + 4 = 10 |
![]() |
Najmniejszą wagę ma krawędź 2–7. Dodajemy ją do drzewa
rozpinającego. Suma wag = 3 + 1 + 2 + 4 + 3 = 13 |
![]() |
Najmniejszą wagę ma krawędź 0–1. Dodajemy ją do drzewa
rozpinającego. Suma wag = 3 + 1 + 2 + 4 + 3 + 5 = 18 |
![]() |
Najmniejszą wagę ma krawędź 6–3. Dodajemy ją do drzewa
rozpinającego. Suma wag = 3 + 1 + 2 + 4 + 3 + 5 + 8 = 26 |
![]() |
Wszystkie wierzchołki znalazły się w drzewie rozpinającym. Zadanie wykonane. |
Podobnie jak w przypadku algorytmu Kruskala tutaj również musimy zastosować odpowiednie struktury danych, aby efektywnie zaimplementować ten algorytm.
Algorytm wymaga wyszukiwania krawędzi o najniższym koszcie. Do tego celu można wykorzystać kolejkę priorytetową, w której elementy są udostępniane wg najniższych wag. W momencie dodania wierzchołka do drzewa w kolejce umieszczamy wszystkie krawędzie prowadzące od tego wierzchołka do wierzchołków, które jeszcze nie znajdują się w drzewie rozpinającym. Następnie z kolejki pobieramy krawędzie dotąd, aż otrzymamy krawędź prowadzącą do jeszcze niewybranego wierzchołka. Krawędź tą dodajemy do drzewa rozpinającego.
Algorytm musi sprawdzać, czy krawędź pobrana z kolejki priorytetowej łączy się z niewybranym jeszcze wierzchołkiem. Do tego celu można wykorzystać prostą tablicę logiczną odwiedzin visited. Tablica ta odwzorowuje wierzchołki grafu. Początkowo wszystkie jej elementy ustawiamy na false, co oznacza, że odpowiadające im wierzchołki nie znajdują się w drzewie rozpinającym. Następnie w miarę dodawania krawędzi do drzewa objęte nimi wierzchołki oznaczamy w tablicy visited wartością true.
n | – | liczba wierzchołków w grafie, n ∈ C. |
graf | – | zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. Graf musi być spójny. |
Q | – | kolejka priorytetowa. Elementami są krawędzie wraz z wagami. Pierwszy element posiada najniższą wagę. Kolejka powinna pomieścić wszystkie krawędzie grafu. |
visited | – | n elementowa tablica logiczna, która odwzorowuje przynależność wierzchołków do drzewa rozpinającego. |
u, v | – | numery wierzchołków w grafie, u, v ∈ C. |
w | – | waga krawędzi, w ∈ R. |
i | – | licznik pętli, i ∈ C. |
K01: | Utwórz pustą kolejkę priorytetową Q |
|
K02: | Utwórz n elementową tablicę visited i zainicjuj jej elementy na false |
|
K03: | Utwórz pusty zbiór T | |
K04: | v ← 0 | wybieramy wierzchołek startowy 0 ( może być dowolny inny ) |
K05: | visited [ v ] ← true | oznaczamy v jako wierzchołek drzewa |
K06: | Dla i = 1, 2, ...,
n - 1: wykonuj kroki K07...K13 |
pętla tworząca drzewo |
K07: | Dla każdego
sąsiada u wierzchołka v : wykonuj krok K08 |
przeglądamy sąsiadów wierzchołka v |
K08: |
Jeśli visited [ u ] = false, to Q.push ( v–u:w ) |
w kolejce umieszczamy krawędzie do nieodwiedzonych sąsiadów |
K09: | v–u:w ← Q.front( ); Q.pop( ) | pobieramy z kolejki krawędź o najniższym koszcie w |
K10: | Jeśli
visited [ u ] = true, to idź do kroku K09 |
jeśli prowadzi do wierzchołka w drzewie, odrzucamy ją |
K11: | Dodaj v–u:w do T | inaczej dodajemy ją do drzewa rozpinającego |
K12: | visited [ u ] ← true | oznaczamy u jako wierzchołek drzewa |
K13: | v ← u | u czynimy wierzchołkiem bieżącym i kontynuujemy pętlę |
K14: | Zakończ z wynikiem T |
Uwaga:
Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program odczytuje definicję spójnego, ważonego grafu nieskierowanego i wyznacza dla niego minimalne drzewo rozpinające algorytmem Prima. |
Dane przykładowe (przekopiuj do
schowka i wklej do okna konsoli ):
|
Pascal// Minimalne drzewo rozpinające // Algorytm Prima // Data: 11.04.2014 // (C)2014 mgr Jerzy Wałaszek //-------------------------------- // Definicja obiektu kolejki priorytetowej //---------------------------------------- type Edge = record v1, v2 : integer; // Wierzchołki krawędzi weight : integer; // Waga krawędzi end; Queue = object private Heap : array of Edge; hpos : integer; public constructor init ( n : integer ); destructor destroy; function front : Edge; procedure push ( e : Edge ); procedure pop; end; // Definicja obiektu minimalnego drzewa rozpinającego //--------------------------------------------------- PTNode = ^TNode; TNode = record next : PTNode; v : integer; weight : integer; end; MSTree = object private A : array of PTNode; // Tablica list sąsiedztwa Alen : integer; // Liczba komórek w tablicy weight : integer; // Waga całego drzewa public constructor init ( n : integer ); destructor destroy; procedure addEdge ( e : Edge ); function getAList ( n : integer ) : PTNode; procedure print; end; // Definicje metod obiektu Queue //------------------------------ // Konstruktor - tworzy n elementową tablicę heap na kopiec //--------------------------------------------------------- constructor Queue.init ( n : integer ); begin SetLength ( Heap, n ); // Tworzymy tablicę hpos := 0; // Pozycja w kopcu end; // Destruktor - usuwa kopiec z pamięci //------------------------------------ destructor Queue.destroy; begin SetLength ( Heap, 0 ); end; // Zwraca krawędź z początku kopca //-------------------------------- function Queue.front : Edge; begin front := Heap [ 0 ]; end; // Umieszcza w kopcu nową krawędź i odtwarza strukturę kopca //---------------------------------------------------------- procedure Queue.push ( e : Edge ); var i, j : integer; begin i := hpos; // i ustawiamy na koniec kopca inc ( hpos ); // W kopcu będzie o 1 element wiecej j := ( i - 1 ) Shr 1; // Obliczamy pozycję rodzica // Szukamy miejsca w kopcu dla e while( i > 0 ) and ( Heap [ j ].weight > e.weight ) do begin Heap [ i ] := Heap [ j ]; i := j; j := ( i - 1 ) Shr 1; end; Heap [ i ] := e; // Krawędź e wstawiamy do kopca end; // Usuwa korzeń z kopca i odtwarza jego strukturę //----------------------------------------------- procedure Queue.pop; var i, j : integer; e : Edge; begin if hpos > 0 then begin dec ( hpos ); e := Heap [ hpos ]; i := 0; j := 1; while j < hpos do begin if( j + 1 < hpos ) and ( Heap [ j + 1 ].weight < Heap [ j ].weight ) then inc ( j ); if e.weight <= Heap [ j ].weight then break; Heap [ i ] := Heap [ j ]; i := j; j := ( j Shl 1 ) + 1; end; Heap [ i ] := e; end; end; // Definicje metod obiektu MSTree //------------------------------- // Konstruktor - tworzy tablicę pustych list sąsiedztwa //----------------------------------------------------- constructor MSTree.init ( n : integer ); var i : integer; begin SetLength ( A, n ); // Tworzymy tablicę dynamiczną for i := 0 to n - 1 do A [ i ] := nil; // i wypełniamy ją pustymi listami Alen := n - 1; // Zapamiętujemy długość tablicy weight := 0; // Zerujemy wagę drzewa end; // Destruktor - usuwa listy oraz tablicę sąsiedztwa //------------------------------------------------- destructor MSTree.destroy; var i : integer; p, r : PTNode; begin for i := 0 to Alen do begin p := A [ i ]; while p <> nil do begin r := p; // Zapamiętujemy wskazanie p := p^.next; // Przesuwamy się do następnego elementu listy dispose ( r ); // Usuwamy element end; end; SetLength ( A, 0 ); // Usuwamy tablicę list sąsiedztwa end; // Dodaje krawędź do drzewa //------------------------- procedure MSTree.addEdge ( e : Edge ); var p : PTNode; begin inc ( weight, e.weight ); // Do wagi drzewa dodajemy wagę krawędzi new ( p ); // Tworzymy nowy węzeł p^.v := e.v2; // Wierzchołek końcowy p^.weight := e.weight; // Waga krawędzi p^.next := A [ e.v1 ]; // Dodajemy p do listy wierzchołka v1 A [ e.v1 ] := p; new ( p ); // To samo dla krawędzi odwrotnej p^.v := e.v1; // Wierzchołek końcowy p^.weight := e.weight; // Waga krawędzi p^.next := A [ e.v2 ]; // Dodajemy p do listy wierzchołka v2 A [ e.v2 ] := p; end; // Zwraca wskaźnik początku listy sąsiadów wierzchołka //---------------------------------------------------- function MSTree.getAList ( n : integer ) : PTNode; begin getAList := A [ n ]; end; // Wyświetla zawartość drzewa oraz jego wagę //------------------------------------------ procedure MSTree.print; var i : integer; p : PTNode; begin writeln; for i := 0 to Alen do begin write ( 'Vertex ', i, ' - ' ); p := A [ i ]; while p <> nil do begin write ( p^.v, ':', p^.weight, ' ' ); p := p^.next; end; writeln; end; writeln; writeln ( 'Minimal Spanning Tree Weight = ', weight ); writeln; end; // ********************** // *** PROGRAM GŁÓWNY *** // ********************** var n, m : integer; // Liczba wierzchołków i krawędzi e : Edge; p : PTNode; i, v : integer; Q : Queue; // Kolejka priorytetowa oparta na kopcu G : MSTree; // Graf T : MSTree; // Minimalne drzewo rozpinające visited : array of boolean; // Tablica odwiedzin begin read ( n, m ); // Czytamy liczbę wierzchołków i krawędzi Q.init ( m ); // Inicjujemy kolejkę priorytetową T.init ( n ); // Inicjujemy minimalne drzewo rozpinające G.init ( n ); // Inicjujemy graf SetLength ( visited, n ); // Tworzymy tablicę odwiedzin for i := 0 to n - 1 do visited [ i ] := false; // Inicjujemy tablicę odwiedzin for i := 1 to m do begin read ( e.v1, e.v2, e.weight ); // Odczytujemy kolejne krawędzie grafu G.addEdge ( e ); // i umieszczamy je w G end; // Tworzymy minimalne drzewo rozpinające v := 0; // Wierzchołek startowy visited [ v ] := true; // Oznaczamy go jako odwiedzonego for i := 1 to n - 1 do // Do drzewa dodamy n - 1 krawędzi grafu begin p := G.getAList ( v ); // Pobieramy adres listy sąsiadów do p while p <> nil do // Przeglądamy listę begin if not visited [ p^.v ] then begin e.v1 := v; // Tworzymy krawędź e.v2 := p^.v; e.weight := p^.weight; Q.push ( e ); // Dodajemy ją do kolejki priorytetowej end; p := p^.next; // Następny sąsiad end; repeat e := Q.front; // Pobieramy krawędź z kolejki Q.pop; until not visited [ e.v2 ]; // Krawędź prowadzi poza drzewo? T.addEdge ( e ); // Dodajemy krawędź do drzewa rozpinającego visited [ e.v2 ] := true; // Oznaczamy drugi wierzchołek jako odwiedzony v := e.v2; end; // Wyświetlamy wyniki T.print; // Usuwamy struktury Q.destroy; T.destroy; G.destroy; SetLength ( visited, 0 ); end. |
C++// Minimalne drzewo rozpinające // Algorytm Prima // Data: 11.04.2014 // (C)2014 mgr Jerzy Wałaszek //-------------------------------- #include <iostream> using namespace std; // Definicja obiektu kolejki priorytetowej //---------------------------------------- struct Edge { int v1, v2, weight; // Wierzchołki krawędzi, waga krawędzi }; class Queue { private: Edge * Heap; int hpos; public: Queue ( int n ); ~Queue( ); Edge front( ); void push ( Edge e ); void pop( ); }; // Definicja obiektu minimalnego drzewa rozpinającego //--------------------------------------------------- struct TNode { TNode * next; int v, weight; }; class MSTree { private: TNode ** A; // Tablica list sąsiedztwa int Alen; // Liczba komórek w tablicy int weight; // Waga całego drzewa public: MSTree ( int n ); ~MSTree( ); void addEdge ( Edge e ); TNode * getAList ( int n ); void print( ); }; // Definicje metod obiektu Queue //------------------------------ // Konstruktor - tworzy n elementową tablicę heap na kopiec //--------------------------------------------------------- Queue::Queue ( int n ) { Heap = new Edge [ n ]; // Tworzymy tablicę hpos = 0; // Pozycja w kopcu } // Destruktor - usuwa kopiec z pamięci //------------------------------------ Queue::~Queue( ) { delete [ ] Heap; } // Zwraca krawędź z początku kopca //-------------------------------- Edge Queue::front( ) { return Heap [ 0 ]; } // Umieszcza w kopcu nową krawędź i odtwarza strukturę kopca //---------------------------------------------------------- void Queue::push ( Edge e ) { int i, j; i = hpos++; // i ustawiamy na koniec kopca j = ( i - 1 ) >> 1; // Obliczamy pozycję rodzica // Szukamy miejsca w kopcu dla e while( i && ( Heap [ j ].weight > e.weight ) ) { Heap [ i ] = Heap [ j ]; i = j; j = ( i - 1 ) >> 1; } Heap [ i ] = e; // Krawędź e wstawiamy do kopca } // Usuwa korzeń z kopca i odtwarza jego strukturę //----------------------------------------------- void Queue::pop( ) { int i, j; Edge e; if( hpos ) { e = Heap [ --hpos ]; i = 0; j = 1; while( j < hpos ) { if( ( j + 1 < hpos ) && ( Heap [ j + 1 ].weight < Heap [ j ].weight ) ) j++; if( e.weight <= Heap [ j ].weight ) break; Heap [ i ] = Heap [ j ]; i = j; j = ( j << 1 ) + 1; } Heap [ i ] = e; } } // Definicje metod obiektu MSTree //------------------------------- // Konstruktor - tworzy tablicę pustych list sąsiedztwa //----------------------------------------------------- MSTree::MSTree ( int n ) { int i; A = new TNode * [ n ]; // Tworzymy tablicę dynamiczną for( i = 0; i < n; i++ ) A [ i ] = NULL; // i wypełniamy ją pustymi listami Alen = n - 1; // Zapamiętujemy długość tablicy weight = 0; // Zerujemy wagę drzewa } // Destruktor - usuwa listy oraz tablicę sąsiedztwa //------------------------------------------------- MSTree::~MSTree( ) { int i; TNode *p, *r; for( i = 0; i <= Alen; i++ ) { p = A [ i ]; while( p ) { r = p; // Zapamiętujemy wskazanie p = p->next; // Przesuwamy się do następnego elementu listy delete r; // Usuwamy element } } delete [ ] A; // Usuwamy tablicę list sąsiedztwa } // Dodaje krawędź do drzewa //------------------------- void MSTree::addEdge ( Edge e ) { TNode *p; weight += e.weight; // Do wagi drzewa dodajemy wagę krawędzi p = new TNode; // Tworzymy nowy węzeł p->v = e.v2; // Wierzchołek końcowy p->weight = e.weight; // Waga krawędzi p->next = A [ e.v1 ]; // Dodajemy p do listy wierzchołka v1 A [ e.v1 ] = p; p = new TNode; // To samo dla krawędzi odwrotnej p->v = e.v1; // Wierzchołek końcowy p->weight = e.weight; // Waga krawędzi p->next = A [ e.v2 ]; // Dodajemy p do listy wierzchołka v2 A [ e.v2 ] = p; } // Zwraca wskaźnik początku listy sąsiadów wierzchołka //---------------------------------------------------- TNode * MSTree::getAList ( int n ) { return A [ n ]; } // Wyświetla zawartość drzewa oraz jego wagę //------------------------------------------ void MSTree::print( ) { int i; TNode *p; cout << endl; for( i = 0; i <= Alen; i++ ) { cout << "Vertex " << i << " - "; for( p = A [ i ]; p; p = p->next ) cout << p->v << ":" << p->weight << " "; cout << endl; } cout << endl << endl << "Minimal Spanning Tree Weight = " << weight << endl << endl; } // ********************** // *** PROGRAM GŁÓWNY *** // ********************** int main( ) { int n, m; // Liczba wierzchołków i krawędzi Edge e; TNode * p; int i, v; cin >> n >> m; // Czytamy liczbę wierzchołków i krawędzi Queue Q ( m ); // Kolejka priorytetowa oparta na kopcu MSTree T ( n ); // Minimalne drzewo rozpinające MSTree G ( n ); // Graf bool * visited = new bool [ n ]; for( i = 0; i < n; i++ ) visited [ i ] = false; // Inicjujemy tablicę odwiedzin for( i = 0; i < m; i++ ) { cin >> e.v1 >> e.v2 >> e.weight; // Odczytujemy kolejne krawędzie grafu G.addEdge ( e ); // i umieszczamy je w G } // Tworzymy minimalne drzewo rozpinające v = 0; // Wierzchołek startowy visited [ v ] = true; // Oznaczamy go jako odwiedzonego for( i = 1; i < n; i++ ) // Do drzewa dodamy n - 1 krawędzi grafu { for( p = G.getAList ( v ); p; p = p->next ) // Przeglądamy listę sąsiadów if( !visited [ p->v ] ) // Jeśli sąsiad jest nieodwiedzony, { e.v1 = v; // to tworzymy krawędź e.v2 = p->v; e.weight = p->weight; Q.push ( e ); // Dodajemy ją do kolejki priorytetowej } do { e = Q.front( ); // Pobieramy krawędź z kolejki Q.pop( ); } while( visited [ e.v2 ] ); // Krawędź prowadzi poza drzewo? T.addEdge ( e ); // Dodajemy krawędź do drzewa rozpinającego visited [ e.v2 ] = true; // Oznaczamy drugi wierzchołek jako odwiedzony v = e.v2; } // Wyświetlamy wyniki T.print( ); delete [ ] visited; return 0; } |
Basic' Minimalne drzewo rozpinające ' Algorytm Prima ' Data: 11.04.2014 ' (C)2014 mgr Jerzy Wałaszek '-------------------------------- ' Definicja obiektu kolejki priorytetowej '---------------------------------------- Type Edge v1 As Integer ' Wierzchołki krawędzi, waga krawędzi v2 As Integer weight As Integer End Type Type Queue Private: Heap As Edge Ptr hpos As Integer Public: Declare Constructor ( ByVal n As Integer ) Declare Destructor( ) Declare Function front( ) As Edge Declare Sub push ( ByVal e As Edge ) Declare Sub pop( ) End Type ' Definicja obiektu minimalnego drzewa rozpinającego '--------------------------------------------------- Type TNode Next As TNode Ptr v As Integer weight As Integer End Type Type MSTree Private: A As TNode Ptr Ptr ' Tablica list sąsiedztwa Alen As Integer ' Liczba komórek w tablicy weight As Integer ' Waga całego drzewa Public: Declare Constructor ( ByVal n As Integer ) Declare Destructor( ) Declare Sub addEdge ( ByVal e As Edge ) Declare Function getAList ( ByVal n As integer ) As TNode Ptr Declare Sub Tprint( ) End Type ' Definicje metod obiektu Queue '------------------------------ ' Konstruktor - tworzy n elementową tablicę heap na kopiec '--------------------------------------------------------- Constructor Queue ( ByVal n As Integer ) Heap = New Edge [ n ] ' Tworzymy tablicę hpos = 0 ' Pozycja w kopcu End Constructor ' Destruktor - usuwa kopiec z pamięci '------------------------------------ Destructor Queue( ) Delete [ ] Heap End Destructor ' Zwraca krawędź z początku kopca '-------------------------------- Function Queue.front( ) As Edge return Heap [ 0 ] End Function ' Umieszcza w kopcu nową krawędź i odtwarza strukturę kopca '---------------------------------------------------------- Sub Queue.push ( ByVal e As Edge ) Dim As Integer i, j i = hpos ' i ustawiamy na koniec kopca hpos += 1 j = ( i - 1 ) Shr 1 ' Obliczamy pozycję rodzica ' Szukamy miejsca w kopcu dla e while( i > 0 ) AndAlso ( Heap [ j ].weight > e.weight ) Heap [ i ] = Heap [ j ] i = j j = ( i - 1 ) Shr 1 Wend Heap [ i ] = e ' Krawędź e wstawiamy do kopca End Sub ' Usuwa korzeń z kopca i odtwarza jego strukturę '----------------------------------------------- Sub Queue.pop( ) Dim As Integer i, j Dim As Edge e If hpos > 0 Then hpos -= 1 e = Heap [ hpos ] i = 0 j = 1 While j < hpos if( j + 1 < hpos ) AndAlso ( Heap [ j + 1 ].weight < Heap [ j ].weight ) Then j += 1 If e.weight <= Heap [ j ].weight Then Exit While Heap [ i ] = Heap [ j ] i = j j = ( j Shl 1 ) + 1 Wend Heap [ i ] = e End If End Sub ' Definicje metod obiektu MSTree '------------------------------- ' Konstruktor - tworzy tablicę pustych list sąsiedztwa '----------------------------------------------------- Constructor MSTree ( ByVal n As Integer ) Dim As Integer i A = New TNode Ptr [ n ] ' Tworzymy tablicę dynamiczną For i = 0 To n - 1 A [ i ] = 0 ' i wypełniamy ją pustymi listami Next Alen = n - 1 ' Zapamiętujemy długość tablicy weight = 0 ' Zerujemy wagę drzewa End Constructor ' Destruktor - usuwa listy oraz tablicę sąsiedztwa '------------------------------------------------- Destructor MSTree( ) Dim As Integer i Dim As TNode Ptr p, r For i = 0 to Alen p = A [ i ] While p r = p ' Zapamiętujemy wskazanie p = p->Next ' Przesuwamy się do następnego elementu listy Delete r ' Usuwamy element Wend Next Delete [ ] A ' Usuwamy tablicę list sąsiedztwa End Destructor ' Dodaje krawędź do drzewa '------------------------- Sub MSTree.addEdge ( ByVal e As Edge ) Dim As TNode Ptr p weight += e.weight ' Do wagi drzewa dodajemy wagę krawędzi p = New TNode ' Tworzymy nowy węzeł p->v = e.v2 ' Wierzchołek końcowy p->weight = e.weight ' Waga krawędzi p->next = A [ e.v1 ] ' Dodajemy p do listy wierzchołka v1 A [ e.v1 ] = p p = New TNode ' To samo dla krawędzi odwrotnej p->v = e.v1 ' Wierzchołek końcowy p->weight = e.weight ' Waga krawędzi p->next = A [ e.v2 ] ' Dodajemy p do listy wierzchołka v2 A [ e.v2 ] = p End Sub ' Zwraca wskaźnik początku listy sąsiadów wierzchołka '---------------------------------------------------- Function MSTree.getAList ( ByVal n As integer ) As TNode Ptr Return A [ n ] End Function ' Wyświetla zawartość drzewa oraz jego wagę '------------------------------------------ Sub MSTree.Tprint( ) Dim As Integer i Dim As TNode Ptr p Print For i = 0 to Alen Print "Vertex";i;" - "; p = A [ i ] While p Print Using "&:& ";p->v;p->weight; p = p->Next Wend Print Next Print Print "Minimal Spanning Tree Weight =";weight Print End Sub ' ********************** ' *** PROGRAM GŁÓWNY *** ' ********************** Dim As integer n, m ' Liczba wierzchołków i krawędzi Dim As Edge e Dim As TNode Ptr p Dim As Integer i, v Open Cons For Input As #1 Input #1, n, m ' Czytamy liczbę wierzchołków i krawędzi Dim As Queue Q = m ' Kolejka priorytetowa oparta na kopcu Dim As MSTree T = n ' Minimalne drzewo rozpinające Dim As MSTree G = n ' Graf Dim As Byte visited ( 0 To N - 1 ) For i = 0 To n - 1 visited ( i ) = 0 ' Inicjujemy tablicę odwiedzin Next For i = 1 To m Input #1, e.v1, e.v2, e.weight ' Odczytujemy kolejne krawędzie grafu G.addEdge ( e ) ' i umieszczamy je w G Next Close #1 ' Tworzymy minimalne drzewo rozpinające v = 0 ' Wierzchołek startowy visited ( v ) = 1 ' Oznaczamy go jako odwiedzonego For i = 2 To n ' Do drzewa dodamy n - 1 krawędzi grafu p = G.getAList ( v ) ' Przeglądamy listę sąsiadów While p If visited ( p->v ) = 0 Then ' Jeśli sąsiad jest nieodwiedzony, e.v1 = v ' to tworzymy krawędź e.v2 = p->v e.weight = p->weight Q.push ( e ) ' Dodajemy ją do kolejki priorytetowej End If p = p->Next ' Następny sąsiad Wend Do e = Q.front( ) ' Pobieramy krawędź z kolejki Q.pop( ) Loop While visited ( e.v2 ) = 1 ' Krawędź prowadzi poza drzewo? T.addEdge ( e ) ' Dodajemy krawędź do drzewa rozpinającego visited ( e.v2 ) = 1 ' Oznaczamy drugi wierzchołek jako odwiedzony v = e.v2 Next ' Wyświetlamy wyniki T.Tprint( ) End |
Wynik: | |
8 16 0 1 5 0 3 9 0 6 3 1 2 9 1 4 8 1 5 6 1 7 7 2 3 9 2 4 4 2 6 5 2 7 3 3 6 8 4 5 2 4 6 1 5 6 6 6 7 9 Vertex 0 - 1:5 6:3 Vertex 1 - 0:5 Vertex 2 - 7:3 4:4 Vertex 3 - 6:8 Vertex 4 - 2:4 5:2 6:1 Vertex 5 - 4:2 Vertex 6 - 3:8 4:1 0:3 Vertex 7 - 2:3 Minimal Spanning Tree Weight = 26 |
![]() |
![]() |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2023 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.