Algorytmy i Struktury Danych - Drzewa rozpinające

Do utworzenia drzewa rozpinającego w głąb (ang. Depth-First Spanning Tree) wykorzystujemy algorytm DFS. W trakcie przechodzenia przez graf zapamiętujemy w osobnej strukturze przebyte krawędzie. Po zakończeniu przejścia struktura ta będzie zawierała drzewo rozpinające w głąb.

Algorytm tworzenia drzewa rozpinającego w głąb

Procedura rekurencyjna DFSTree (v, graf, T, visited)

Wejście:

n	–	liczba wierzchołków w grafie (algorytm z tej danej nie korzysta), n ∈ C.
v	–	wierzchołek startowy, który będzie korzeniem, v ∈ C.
graf	:	zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
T	:	pusta n elementowa tablica list sąsiedztwa dla drzewa.
visited	:	n elementowa tablica logiczna wypełniona wartościami false.

Wyjście:

–

tablica list sąsiedztwa zawierająca drzewo rozpinające w głąb.

Elementy pomocnicze:

–

wierzchołek, u ∈ C.

Lista kroków:

K01:	visited [v] ← true	oznaczamy wierzchołek v jako odwiedzony
K02:	Dla każdego sąsiada u wierzchołka v : wykonuj kroki K03…K05
K03:	Jeśli visited [u] = true, to następny obieg pętli K02	szukamy nieodwiedzonych jeszcze sąsiadów
K04:	Dodaj wierzchołek u do listy T [v]	dodajemy krawędź v-u do drzewa rozpinającego
K05:	DFSTree (u, graf, T, visited)	rekurencyjnie tworzymy drzewo rozpinające
K06	Zakończ

Uwaga: jeśli drzewo rozpinające ma być grafem nieskierowanym, to w kroku K04 należy również dodać wierzchołek v do listy T [u ], aby powstała krawędź biegnąca z powrotem od wierzchołka w do v.

Przykładowe programy

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 wczytuje definicję grafu nieskierowanego oraz numer wierzchołka startowego. Następnie tworzy jedno z drzew rozpinających w głąb i wyświetla wyniki w oknie konsoli.

Przykładowe dane (ostatnia czerwona liczba określa wierzchołek startowy, który będzie korzeniem drzewa rozpinającego):

17 24
0 1 0 2 0 3
1 2 1 9 1 14
2 6
3 4 3 6
4 12 4 13
5 6 5 9
6 7 6 8 6 12
7 13
10 11 10 14 10 15
11 16
12 16
13 16
14 15
6

Pascal

// Drzewo rozpinające w głąb
// Data: 22.09.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program DFS_tree;

// Typ listy jednokierunkowej

type
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

  TList = array of PSLel;

// Zmienne globalne

var
  graf    : TList;            // Tablica list sąsiedztwa grafu
  T       : TList;            // Tablica list sąsiedztwa drzewa rozpinającego
  visited : array of boolean; // Tablica odwiedzin

// Rekurencyjna procedura tworzenia drzewa rozpinającego w głąb
// v-numer wierzchołka startowego
// reszta zmiennych globalna
//-------------------------------------------------------------
procedure DFSTree (v : integer);
var
  p, r : PSLel;
  u   : integer;
begin
  visited [v] := true;     // Oznaczamy wierzchołek jako odwiedzony
  p := graf [v];           // Przeglądamy sąsiadów
  while p <> nil do
  begin
    u := p^.v;               // u-numer sąsiada
    if not visited [u] then // Interesują nas tylko nieodwiedzeni sąsiedzi
    begin
      new (r);             // Dodajemy u do listy T [v]
      r^.v := u;
      r^.next := T [v];
      T [v] := r;
      DFSTree (u);         // Rekurencyjnie tworzymy drzewo
    end;
    p := p^.next;            // Następny sąsiad
  end;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  i, n, m, v1, v2 : integer;
  p, r         : PSLel;
begin
  read (n, m);             // Czytamy liczbę wierzchołków i krawędzi
  SetLength (graf, n);     // Tworzymy tablicę list sąsiedztwa grafu
  SetLength (T, n);        // Tworzymy tablicę list sąsiedztwa drzewa rozpinającego
  SetLength (visited, n);  // Tworzymy tablicę odwiedzin

  // Tablice wypełniamy pustymi listami

  for i := 0 to n-1 do
  begin
    graf [i]    := nil;
    T [i]       := nil;
    visited [i] := false;
  end;

  // Odczytujemy kolejne definicje krawędzi

  for i := 1 to m do
  begin
    read (v1, v2);         // Wierzchołek startowy i końcowy krawędzi
    new (p);               // Tworzymy nowy element
    p^.v     := v2;          // Numerujemy go jako v2
    p^.next  := graf [v1]; // Dodajemy go na początek listy A [v1]
    graf [v1] := p;
    new (p);               // Teraz krawędź w odwrotną stronę
    p^.v     := v1;
    p^.next  := graf [v2];
    graf [v2] := p;
  end;

  // Tworzymy drzewo rozpinające w głąb

  read (v1);               // Czytamy wierzchołek startowy

  DFSTree (v1);

  // Wyświetlamy tablicę list sąsiedztwa drzewa rozpinającego

  writeln;

  for i := 0 to n-1 do
  begin
    write (i:2, ' : ');
    p := T [i];
    while p <> nil do
    begin
      write (p^.v, ' ');
      p := p^.next;
    end;
    writeln;
  end;

  // Usuwamy dynamiczne struktury danych

  for i := 0 to n-1 do
  begin
    p := graf [i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose (r);
    end;

    p := T [i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose (r);
    end;
  end;

  SetLength (graf, 0);
  SetLength (T, 0);
  SetLength (visited, 0);

  writeln;
end.

C++

// Drzewo rozpinające w głąb
// Data: 22.09.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typ listy jednokierunkowej

struct SLel
{
  SLel * next;
  int v;
};

// Zmienne globalne

SLel ** graf; // Tablica list sąsiedztwa grafu
SLel ** T;    // Tablica list sąsiedztwa drzewa rozpinającego
bool * visited;  // Tablica odwiedzin

// Rekurencyjna funkcja tworzenia drzewa rozpinającego w głąb
// v-numer wierzchołka startowego
// reszta zmiennych globalna
//-------------------------------------------------------------
void DFSTree (int v)
{
  SLel *p, *r;
  int u;

  visited [v] = true;      // Oznaczamy wierzchołek jako odwiedzony
  for(p = graf [v]; p; p = p->next) // Przeglądamy sąsiadów
  {
    u = p->v;                // u-numer sąsiada
    if(!visited [u])     // Interesują nas tylko nieodwiedzeni sąsiedzi
    {
      r = new SLel;       // Dodajemy u do listy T [v]
      r->v = u;
      r->next = T [v];
      T [v] = r;
      DFSTree (u);         // Rekurencyjnie tworzymy drzewo
    }
  }
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int n, m, i, v1, v2;
  SLel *p, *r;

  cin >> n >> m;              // Czytamy liczbę wierzchołków i krawędzi
  graf = new SLel * [n]; // Tworzymy tablicę list sąsiedztwa grafu
  T    = new SLel * [n]; // Tworzymy tablicę list sąsiedztwa drzewa rozpinającego
  visited = new bool [n];   // Tworzymy tablicę odwiedzin

  // Tablice wypełniamy pustymi listami

  for(i = 0; i < n; i++)
  {
    graf [i] = T [i] = NULL;
    visited [i] = false;
  }

  // Odczytujemy kolejne definicje krawędzi

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;         // Wierzchołek startowy i końcowy krawędzi
    p = new SLel;         // Tworzymy nowy element
    p->v     = v2;           // Numerujemy go jako v2
    p->next  = graf [v1];  // Dodajemy go na początek listy A [v1]
    graf [v1] = p;
    p = new SLel;         // Teraz krawędź w odwrotną stronę
    p->v     = v1;
    p->next  = graf [v2];
    graf [v2] = p;
  }

  // Tworzymy drzewo rozpinające w głąb

  cin >> v1;                 // Czytamy wierzchołek startowy

  DFSTree (v1);

  // Wyświetlamy tablicę list sąsiedztwa drzewa rozpinającego

  cout << endl;

  for(i = 0; i < n; i++)
  {
    cout << setw (2) << i << ":";
    for(p = T [i]; p; p = p->next) cout << setw (3) << p->v;
    cout << endl;
  }

  // Usuwamy dynamiczne struktury danych

  for(i = 0; i < n; i++)
  {
    p = graf [i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }

    p = T [i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }

  delete [] graf;
  delete [] T;
  delete [] visited;

  cout << endl;

  return 0;}

Basic

' Drzewo rozpinające w głąb
' Data: 22.09.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

' Typ listy jednokierunkowej

Type SLel
  next As SLel Ptr
  v As Integer
End Type

' Zmienne globalne

Dim Shared As SLel Ptr Ptr graf, T ' Tablice list sąsiedztwa grafu i drzewa
Dim Shared As Byte Ptr visited        ' Tablica odwiedzin

' Rekurencyjna procedura tworzenia drzewa rozpinającego w głąb
' v-numer wierzchołka startowego
' reszta zmiennych globalna
'-------------------------------------------------------------
Sub DFSTree (byval v As Integer)
  Dim As SLel Ptr p, r
  Dim As Integer u

  visited [v] = 1          ' Oznaczamy wierzchołek jako odwiedzony
  p = graf [v]
  while p                    ' Przeglądamy sąsiadów
    u = p->v                 ' u-numer sąsiada
    If visited [u] = 0 Then ' Interesują nas tylko nieodwiedzeni sąsiedzi
      r = new SLel        ' Dodajemy u do listy T [v]
      r->v = u
      r->next = T [v]
      T [v] = r
      DFSTree (u)          ' Rekurencyjnie tworzymy drzewo
    End If
    p = p->Next
  Wend
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer i, n, m, v1, v2
Dim As SLel Ptr p, r

Open Cons For Input As #1

Input #1, n, m                 ' Czytamy liczbę wierzchołków i krawędzi

graf = New SLel Ptr [n]   ' Tworzymy tablicę list sąsiedztwa grafu
T    = New SLel Ptr [n]   ' Tworzymy tablicę list sąsiedztwa drzewa rozpinającego
visited = New Byte [n]       ' Tworzymy tablicę odwiedzin

' Tablice wypełniamy pustymi listami

For i = 0 To n-1
  graf [i] = 0
  T [i]    = 0
  visited [i] = 0
Next

' Odczytujemy kolejne definicje krawędzi

For i = 1 To m
  Input #1, v1, v2           ' Wierzchołek startowy i końcowy krawędzi
  p = New SLel            ' Tworzymy nowy element
  p->v     = v2              ' Numerujemy go jako v2
  p->next  = graf [v1]     ' Dodajemy go na początek listy A [v1]
  graf [v1] = p
  p = new SLel            ' Teraz krawędź w odwrotną stronę
  p->v     = v1
  p->next  = graf [v2]
  graf [v2] = p
Next

' Tworzymy drzewo rozpinające w głąb

Input #1, v1                 ' Czytamy wierzchołek startowy

Close #1

DFSTree (v1)

' Wyświetlamy tablicę list sąsiedztwa drzewa rozpinającego

Print

For i = 0 To n-1
  Print Using "## :";i;
  p = T [i]
  While p
    Print Using "###";p->v;
    p = p->Next
  Wend
  Print
Next

' Usuwamy dynamiczne struktury danych

For i = 0 To n-1
  p = graf [i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend

  p = T [i]
  While p
    r = p
    p = p->Next
    Delete r
  Wend
Next

Delete [] graf
Delete [] T
Delete [] visited

Print

End

Wynik:
17 24 0 1 0 2 0 3 1 2 1 9 1 14 2 6 3 4 3 6 4 12 4 13 5 6 5 9 6 7 6 8 6 12 7 13 10 11 10 14 10 15 11 16 12 16 13 16 14 15 6 0 : 2 1 : 9 14 2 : 1 3 : 0 4 : 3 5 : 6 : 8 12 7 : 8 : 9 : 5 10 : 11 11 : 12 : 16 13 : 4 7 14 : 15 15 : 10 16 : 13

Na początek: podrozdziału strony

Algorytm tworzenia drzewa rozpinającego wszerz (ang. Breadth First Spanning Tree) jest w zasadzie identyczny jak dla drzewa rozpinającego w głąb – jedyną różnicą jest zastąpienie stosu kolejką (musimy przy tym pamiętać, że kolejka nie odwraca kolejności zapisanych danych, jak robi to stos).

Algorytm tworzenia drzewa rozpinającego wszerz

Wejście:

n	–	liczba wierzchołków w grafie, n ∈ C.
v	–	wierzchołek startowy, który będzie korzeniem, v ∈ C.
graf	:	zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
visited	:	wyzerowana n elementowa tablica logiczna.
T	:	n elementowa tablica pustych list sąsiedztwa.

Wyjście:

–

tablica list sąsiedztwa zawierająca drzewo rozpinające wszerz.

Elementy pomocnicze:

Q	–	kolejka wierzchołków.
w, z	–	wierzchołki, w, z ∈ C.

Lista kroków:

K01:	Utwórz pustą kolejkę Q	inicjujemy dane
K02:	Q.push (-1); Q.push (v)	w kolejce umieszczamy krawędź -1 v
K03:	visited [v] ← true	oznaczamy wierzchołek v jako odwiedzony
K04:	Dopóki Q.empty() = false: wykonuj kroki K05…K10	uruchamiamy BFS
K05:	v ← Q.front(); Q.pop() w ← Q.front(); Q.pop()	pobieramy z kolejki krawędź v – w
K06:	Jeśli v > -1, to dodaj w do listy T [v ]	krawędź v – w dodajemy do drzewa T
K07:	Dla każdego sąsiada z wierzchołka w : wykonuj kroki K18…K10
K08:	Jeśli visited [z] = true, to następny obieg pętli K07	szukamy nieodwiedzonego sąsiada
K09:	visited [z] ← true	sąsiada oznaczamy jako odwiedzonego
K10:	Q.push (w) Q.push (z)	i krawędź w-z umieszczamy w kolejce
K11:	Zakończ

Uwaga: jeśli drzewo rozpinające ma być grafem nieskierowanym, to po kroku K06 należy również dodać wierzchołek v do listy T [w], aby powstała krawędź biegnąca z powrotem od wierzchołka w do v.

Przykładowe programy

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 wczytuje definicję grafu nieskierowanego oraz numer wierzchołka startowego. Następnie tworzy jedno z drzew rozpinających wszerz i wyświetla wyniki w oknie konsoli.

Przykładowe dane (ostatnia czerwona liczba określa wierzchołek startowy, który będzie korzeniem drzewa rozpinającego):

17 24
0 1 0 2 0 3
1 2 1 9 1 14
2 6
3 4 3 6
4 12 4 13
5 6 5 9
6 7 6 8 6 12
7 13
10 11 10 14 10 15
11 16
12 16
13 16
14 15
6

Pascal

// Drzewo rozpinające wszerz
// Data: 22.09.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program BFS_tree;

// Typ listy jednokierunkowej

type
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

  TList = array of PSLel;

// Zmienne globalne

var
  n, m : integer;        // Liczba wierzchołków n i krawędzi m
  A : TList;             // Tablica list sąsiedztwa grafu
  T : TList;             // Tablica list sąsiedztwa drzewa rozpinającego
  visited : array of Boolean;

// Zapisuje na początek listy

procedure push (var L : PSLel; x : integer);
var
  p : PSLel;
begin
  new (p);
  p^.v := x;
  p^.next := L;
  L := p;
end;

// Odczytuje z listy usuwając odczytany element

function pop (var L : PSLel) : integer;
var
  p : PSLel;
begin
  pop := L^.v;
  p := L;
  L := L^.next;
  dispose (p);
end;

// Zapisuje do kolejki

procedure Q_push (var head, tail : PSLel; x : integer);
var
  p : PSLel;
begin
  new (p);
  p^.next := nil;
  p^.v    := x;
  if tail = nil then head := p
  else tail^.next := p;
  tail := p;
end;

// Odczytuje z kolejki, usuwając element

function Q_pop (var head, tail : PSLel) : integer;
var
  p : PSLel;
begin
  Q_pop := head^.v;
  p := head;
  head := head^.next;
  if head = nil then tail := nil;
  dispose (p);
end;

// Tworzy drzewo rozpinające

procedure BFSTree (v : integer);
var
  head, tail : PSLel;   // Kolejka
  p : PSLel;            // Wskaźnik węzłów na liscie
  w, z : integer;

begin
  head := nil;             // Tworzymy pustą kolejkę
  tail := nil;

  Q_push (head, tail, -1); // W kolejce umieszczamy krawędź -1 v
  Q_push (head, tail, v);

  visited [v] := true;   // Oznaczamy v jako odwiedzony

  while head <> nil do     // Uruchamiamy BFS
  begin
    v := Q_pop (head, tail); // Pobieramy parę v-w z kolejki
    w := Q_pop (head, tail);

    if v > -1 then push (T [v], w); // w dodajemy do listy T [v]

    p := A [w];          // Sąsiadów w umieszczamy w kolejce
    while p <> nil do
    begin
      z := p^.v;
      if not visited [z] then
      begin
        visited [z] := true;
        Q_push (head, tail, w); // Do kolejki para w-sąsiad
        Q_push (head, tail, z);
      end;
      p := p^.next;
    end;
  end;
end;

var
  i, v1, v2 : integer;
  p : PSLel;
begin
  read (n, m);            // Czytamy liczbę wierzchołków i krawędzi

  SetLength (A, n);       // Tworzymy tablicę list sąsiedztwa grafu
  SetLength (T, n);       // Tworzymy tablicę list sąsiedztwa drzewa
  SetLength (visited, n); // Tworzymy tablicę odwiedzin

  // Tablice inicjujemy

  for i := 0 to n-1 do
  begin
    A [i] := nil;
    T [i] := nil;
    visited [i] := false;
  end;

  // Odczytujemy kolejne definicje krawędzi

  for i := 1 to m do
  begin
    read (v1, v2);       // Wierzchołek startowy i końcowy krawędzi
    push (A [v1], v2); // Krawędź v1-v2
    push (A [v2], v1); // Krawędź v2-v1
  end;

  // Tworzymy drzewo rozpinające wszerz

  read (v1);             // Czytamy wierzchołek startowy

  BFSTree (v1);

  // Wyświetlamy tablicę list sąsiedztwa drzewa rozpinającego

  writeln;

  for i := 0 to n-1 do
  begin
    write (i:2, ' :');
    p := T [i];
    while p <> nil do
    begin
      write (p^.v:3);
      p := p^.next;
    end;
    writeln;
  end;

  // Usuwamy tablice dynamiczne

  for i := 0 to n-1 do
  begin
    while A [i] <> nil do v1 := pop (A [i]);
    while T [i] <> nil do v1 := pop (T [i]);
  end;

  SetLength (A, 0);
  SetLength (T, 0);
  SetLength (visited, 0);

  writeln;
end.

C++

// Drzewo rozpinające wszerz
// Data: 22.09.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typ listy jednokierunkowej

struct SLel
{
  SLel * next;
  int v;
};

// Zmienne globalne

int n, m;        // Liczba wierzchołków n i krawędzi m
SLel ** A;    // Tablica list sąsiedztwa grafu
SLel ** T;    // Tablica list sąsiedztwa drzewa rozpinającego
bool * visited;  // Tablica odwiedzin

// Zapisuje na początek listy

void push (SLel * & L, int x)
{
  SLel * p = new SLel;

  p->v = x;
  p->next = L;
  L = p;
}

// Odczytuje z listy usuwając odczytany element

int pop (SLel * & L)
{
  int x = L->v;
  SLel * p = L;
  L = L->next;
  delete p;
  return x;
}

// Zapisuje do kolejki

void Q_push (SLel * & head, SLel * & tail, int x)
{
  SLel * p = new SLel;
  p->next = NULL;
  p->v    = x;
  if(!tail) head = p; else tail->next = p;
  tail = p;
}

// Odczytuje z kolejki, usuwając element

int Q_pop (SLel * & head, SLel * & tail)
{
  SLel * p = head;
  int x = head->v;
  head = head->next;
  if(!head) tail = NULL;
  delete p;
  return x;
}

// Tworzy drzewo rozpinające

void BFSTree (int v)
{
  SLel * head, * tail;     // Kolejka
  SLel * p;                // Wskaźnik węzłów na liscie
  int w, z;

  head = tail = NULL;         // Tworzymy pustą kolejkę

  Q_push (head, tail, -1);  // W kolejce umieszczamy krawędź -1 v
  Q_push (head, tail, v);

  visited [v] = true;       // Oznaczamy v jako odwiedzony

  while(head)               // Uruchamiamy BFS
  {
    v = Q_pop (head, tail); // Pobieramy parę v-w z kolejki
    w = Q_pop (head, tail);

    if(v > -1) push (T [v], w); // w dodajemy do listy T [v]

    for(p = A [w]; p; p = p->next) // Sąsiadów wierzchołka w umieszczamy w kolejce
    {
      z = p->v;
      if(!visited [z])
      {
        visited [z] = true;
        Q_push (head, tail, w); // Do kolejki para w-sąsiad
        Q_push (head, tail, z);
      }
    }
  }
}

int main()
{
  int i, v1, v2;
  SLel * p;

  cin >> n >> m;            // Czytamy liczbę wierzchołków i krawędzi

  A = new SLel * [n];  // Tworzymy tablicę list sąsiedztwa grafu
  T = new SLel * [n];  // Tworzymy tablicę list sąsiedztwa drzewa rozpinającego
  visited = new bool [n]; // Tworzymy tablicę odwiedzin

  // Tablice inicjujemy

  for(i = 0; i < n; i++)
  {
    A [i] = T [i] = NULL;
    visited [i] = false;
  }

  // Odczytujemy kolejne definicje krawędzi

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;       // Wierzchołek startowy i końcowy krawędzi
    push (A [v1], v2); // Krawędź v1-v2
    push (A [v2], v1); // Krawędź v2-v1
  }

  // Tworzymy drzewo rozpinające wszerz

  cin >> v1;            // Czytamy wierzchołek startowy

  BFSTree (v1);

  // Wyświetlamy tablicę list sąsiedztwa drzewa rozpinającego

  cout << endl;

  for(i = 0; i < n; i++)
  {
    cout << setw (2) << i << ":";
    for(p = T [i]; p; p = p->next) cout << setw (3) << p->v;
    cout << endl;
  }

  // Usuwamy tablice dynamiczne

  for(i = 0; i < n; i++)
  {
    while(A [i]) pop (A [i]);
    while(T [i]) pop (T [i]);
  }

  delete [] A;
  delete [] T;
  delete [] visited;

  cout << endl;

  return 0;}

Basic

' Drzewo rozpinające wszerz
' Data: 22.09.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

' Typ listy jednokierunkowej

Type SLel
  next As SLel Ptr
  v As Integer
End Type

' Zmienne globalne

Dim Shared As Integer n, m         ' Liczba wierzchołków n i krawędzi m
Dim Shared As SLel Ptr Ptr A    ' Tablica list sąsiedztwa grafu
Dim Shared As SLel Ptr Ptr T    ' Tablica list sąsiedztwa drzewa rozpinającego
Dim Shared As Byte Ptr visited     ' Tablica odwiedzin

' Zapisuje na początek listy

Sub push (ByRef L As SLel Ptr, ByVal x As Integer)

  Dim As SLel Ptr p = New SLel

  p->v = x
  p->next = L
  L = p
 
End Sub

' Odczytuje z listy usuwając odczytany element

Function pop (ByRef L As SLel Ptr) As Integer

  Dim As Integer x = L->v
  Dim As SLel Ptr p = L
  L = L->Next
  Delete p
  Return x
 
End Function

' Zapisuje do kolejki

Sub Q_push (ByRef head As SLel Ptr, ByRef tail As SLel Ptr, ByVal x As Integer)

  Dim As SLel Ptr p = new SLel
  p->next = 0
  p->v    = x
  If tail = 0 Then
  	 head = p
  Else
  	tail->next = p
  EndIf
  tail = p
End Sub

' Odczytuje z kolejki, usuwając element

Function Q_pop (ByRef head As SLel Ptr, ByRef tail As SLel Ptr) As Integer

  Dim As SLel Ptr p = head
  Dim As Integer x = head->v
  head = head->Next
  If head = 0 Then tail = 0
  delete p
  return x
 
End Function

' Tworzy drzewo rozpinające

Sub BFSTree (ByVal v As Integer)

  Dim As SLel Ptr head, tail ' Kolejka
  Dim As SLel Ptr p       ' Wskaźnik węzłów na liscie
  Dim As Integer w, z

  head = 0                   ' Tworzymy pustą kolejkę
  tail = 0

  Q_push (head, tail, -1)  ' W kolejce umieszczamy krawędź -1 v
  Q_push (head, tail, v)

  visited [v] = 1          ' Oznaczamy v jako odwiedzony

  While head                 ' Uruchamiamy BFS
    v = Q_pop (head, tail) ' Pobieramy parę v-w z kolejki
    w = Q_pop (head, tail)

    If v > -1 Then push (T [v], w) ' w dodajemy do listy T [v]

    p = A [w]
    While p               ' Sąsiadów wierzchołka w umieszczamy w kolejce
      z = p->v
      if visited [z] = 0 Then
        visited [z] = 1
        Q_push (head, tail, w) ' Do kolejki para w-sąsiad
        Q_push (head, tail, z)
      End If
      p = p->Next
    Wend
  Wend
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer i, v1, v2
Dim as SLel Ptr p

Open Cons For Input As #1

Input #1, n, m            ' Czytamy liczbę wierzchołków i krawędzi

A = new SLel Ptr [n] ' Tworzymy tablicę list sąsiedztwa grafu
T = new SLel Ptr [n] ' Tworzymy tablicę list sąsiedztwa drzewa rozpinającego
visited = New Byte [n]  ' Tworzymy tablicę odwiedzin

' Tablice inicjujemy

For i = 0 To n-1
  A [i] = 0
  T [i] = 0
  visited [i] = 0
Next

' Odczytujemy kolejne definicje krawędzi

For i = 1 To m
  Input #1, v1, v2       ' Wierzchołek startowy i końcowy krawędzi
  push (A [v1], v2)  ' Krawędź v1-v2
  push (A [v2], v1)  ' Krawędź v2-v1
Next

' Tworzymy drzewo rozpinające wszerz

Input #1, v1            ' Czytamy wierzchołek startowy

BFSTree (v1)

' Wyświetlamy tablicę list sąsiedztwa drzewa rozpinającego

Close #1

Print

For i = 0 To n-1
  Print Using "## :";i;

  p = T [i]
  while p <> 0
  	 Print Using "###";p->v;
  	 p = p->Next
  Wend
 
  Print
Next

' Usuwamy tablice dynamiczne

For i = 0 To n-1
  While A [i] : pop (A [i]): Wend
  While T [i] : pop (T [i]): Wend
Next

Delete [] A
Delete [] T
Delete [] visited

Print

End

Wynik:
xxx17 24 0 1 0 2 0 3 1 2 1 9 1 14 2 6 3 4 3 6 4 12 4 13 5 6 5 9 6 7 6 8 6 12 7 13 10 11 10 14 10 15 11 16 12 16 13 16 14 15 6 0 : 1 : 14 2 : 1 3 : 0 4 : 5 : 9 6 : 2 3 5 7 8 12 7 : 13 8 : 9 : 10 : 11 : 10 12 : 4 16 13 : 14 : 15 15 : 16 : 11

Na koniec dla porównania przedstawiamy oba drzewa rozpinające:

Drzewo rozpinające w głąb		Drzewo rozpinające wszerz

Na początek: podrozdziału strony

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.

Drzewa rozpinające grafu

Problem

Drzewo rozpinające w głąb

Algorytm tworzenia drzewa rozpinającego w głąb

Procedura rekurencyjna DFSTree (v, graf, T, visited)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Drzewo rozpinające wszerz

Algorytm tworzenia drzewa rozpinającego wszerz

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy