Minimalne drzewo rozpinające


Tematy pokrewne   Podrozdziały
Grafy
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Transpozycja grafu
Kwadrat grafu
Graf krawędziowy
Stopień grafu
Znajdowanie ścieżki w grafie
Znajdowanie drogi w labiryncie
Spójność grafu
Znajdowanie spójnych składowych w grafie
Znajdowanie silnie spójnych składowych w grafie
Drzewa rozpinające grafu
Znajdowanie mostów w grafie
Znajdowanie punktów artykulacji w grafie
Grafy dwudzielne
Kojarzenie małżeństw
Cykliczność grafu
Znajdowanie cykli w grafie
Istnienie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Hamiltona
Sortowanie topologiczne grafu skierowanego
Najkrótsza ścieżka w grafie ważonym – algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym – algorytm Bellmana-Forda
Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Problem chińskiego listonosza
Problem komiwojażera
Minimalne drzewo rozpinające
Kolorowanie grafu
Znajdowanie klik w grafie

Zbiory rozłączne – implementacja w tablicy
Zbiory rozłączne – implementacja listowa
Zbiory rozłączne – implementacja za pomocą drzew
Kolejki priorytetowe

  Algorytm Kruskala
Algorytm Prima

Problem

Dla danego spójnego i nieskierowanego grafu ważonego 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.

 

Algorytm Kruskala

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.

 

T
 
L

4–6:1
4–5:2
2–7:3
0–6:3
2–4:4
0–1:5
2–6:5
1–5:6
5–6:6
1–7:7
1–4:8
3–6:8
0–3:9
1–2:9
2–3:9
6–7:9

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
T
4–6:1
L

4–6:1
4–5:2
2–7:3
0–6:3
2–4:4
0–1:5
2–6:5
1–5:6
5–6:6
1–7:7
1–4:8
3–6:8
0–3:9
1–2:9
2–3:9
6–7:9

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

T

4–6:1
4–5:2

L

4–5:2
2–7:3
0–6:3
2–4:4
0–1:5
2–6:5
1–5:6
5–6:6
1–7:7
1–4:8
3–6:8
0–3:9
1–2:9
2–3:9
6–7:9

Pobieramy z L kolejną krawędź 4–5:2 i dodajemy ją do zbioru T.

Suma wag = 1 + 2 = 3

T

4–6:1
4–5:2
2–7:3

L

2–7:3
0–6:3
2–4:4
0–1:5
2–6:5
1–5:6
5–6:6
1–7:7
1–4:8
3–6:8
0–3:9
1–2:9
2–3:9
6–7:9

Pobieramy z L krawędź 2–7:3 i dołączamy do T.
Suma wag = 1 + 2 + 3 = 6
T

4–6:1
4–5:2
2–7:3
0–6:3

L

0–6:3
2–4:4
0–1:5
2–6:5
1–5:6
5–6:6
1–7:7
1–4:8
3–6:8
0–3:9
1–2:9
2–3:9
6–7:9

Pobieramy z L krawędź 0–6:3 i dołączamy do T.

Suma wag = 1 + 2 + 3 + 3 = 9

T

4–6:1
4–5:2
2–7:3
0–6:3
2–4:4

L

2–4:4
0–1:5
2–6:5
1–5:6
5–6:6
1–7:7
1–4:8
3–6:8
0–3:9
1–2:9
2–3:9
6–7:9

Pobieramy z L krawędź 2–4:4 i dołączamy do T.

Suma wag = 1 + 2 + 3 + 3 + 4 = 13

T

4–6:1
4–5:2
2–7:3
0–6:3
2–4:4
0–1:5

L

0–1:5
2–6:5
1–5:6
5–6:6
1–7:7
1–4:8
3–6:8
0–3:9
1–2:9
2–3:9
6–7:9

Pobieramy z L krawędź 0–1:5 i dołączamy do T.

Suma wag = 1 + 2 + 3 + 3 + 4 + 5 = 18

 

T

4–6:1
4–5:2
2–7:3
0–6:3
2–4:4
0–1:5

L

2–6:5
1–5:6
5–6:6
1–7:7
1–4:8

3–6:8
0–3:9
1–2:9
2–3:9
6–7:9

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.
T

4–6:1
4–5:2
2–7:3
0–6:3
2–4:4
0–1:5
3–6:8

L

3–6:8
0–3:9
1–2:9
2–3:9
6–7:9

Pobieramy z L krawędź 3–6:8 i dołączamy do T.

Suma wag = 1 + 2 + 3 + 3 + 4 + 5 + 8 = 26

T

4–6:1
4–5:2
2–7:3
0–6:3
2–4:4
0–1:5
3–6:8

L

0–3:9
1–2:9
2–3:9
6–7:9

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.

 

Drzewo rozpinające T może być tworzone w macierzy sąsiedztwa, w tablicy list sąsiedztwa lub po prostu w tablicy poprzedników (element i-ty zawiera numer rodzica węzła i-tego na drzewie rozpinającym). Do drzewa dodajemy krawędzie. Zwróć uwagę, że drzewo rozpinające powstanie w T po dodaniu n-1 krawędzi.

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.

 

Algorytm Kruskala znajdowania minimalnego drzewa rozpinającego w spójnym, ważonym grafie nieskierowanym

Wejście
n  –  liczba wierzchołków w grafie, n symbol C
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. Graf musi być spójny.
Wyjście:
Zbiór T. Elementami są krawędzie wraz z wagami. Zbiór zawiera minimalne drzewo rozpinające grafu.
Elementy pomocnicze:
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 symbol C
w  –  waga krawędzi, w symbol 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
Lista kroków:
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 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 K08...K11 ; główną pętlę wykonujemy n-1 razy
K08:     v–u:wQ.front();  Q.pop() ; pobieramy krawędź z początku kolejki
K09:     Jeśli FindSet(Z[v]) = FindSet(Z[u]), to idź do 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  

 

Program

Ważne:

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.

Przykładowe dane dla programu:

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

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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

 

Algorytm Prima

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.

 

Drzewo rozpinające T może być tworzone w macierzy sąsiedztwa, w tablicy list sąsiedztwa lub po prostu w tablicy poprzedników (element i-ty zawiera numer rodzica węzła i-tego na drzewie rozpinającym, korzeń jako rodzica ma węzeł -1). Drzewo powstanie w T po dodaniu n - 1 krawędzi.

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 wisited wartością true.

 

Algorytm Prima znajdowania minimalnego drzewa rozpinającego w spójnym, ważonym grafie nieskierowanym

Wejście
n  –  liczba wierzchołków w grafie, n symbol C
graf  –  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje. Graf musi być spójny.
Wyjście:
Zbiór T. Elementami są krawędzie wraz z wagami. Zbiór zawiera minimalne drzewo rozpinające grafu.
Elementy pomocnicze:
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 symbol C
w  –  waga krawędzi, w symbol R
i  – licznik pętli, i symbol C
Lista kroków:
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 K07...K13 ; pętla tworząca drzewo
K07:     Dla każdego sąsiada u wierzchołka v wykonuj K08 ; przeglądamy sąsiadów wierzchołka v
K08:         Jeśli visited[u] = false, to Q.push(vu:w) ; w kolejce umieszczamy krawędzie do nieodwiedzonych sąsiadów
K09:     vu:wQ.front();  Q.pop() ; pobieramy z kolejki krawędź o najniższym koszcie w
K10:     Jeśli visited[u] = true, to idź do 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:     vu ; u czynimy wierzchołkiem bieżącym i kontynuujemy pętlę
K14: Zakończ z wynikiem T  

 

Program

Ważne:

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.

Przykładowe dane dla programu:

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

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.