Drzewa rozpinające grafu


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
  Drzewo rozpinające w głąb
Drzewo rozpinające wszerz

Problem

Dla danego grafu znaleźć jedno z drzew rozpinających.



Drzewo rozpinające (ang. spanning tree) jest drzewem, które zawiera wszystkie wierzchołki grafu. Dany graf może posiadać wiele różnych drzew rozpinających:

 


Graf podstawowy
    
Drzewo rozpinające nr 1
    
Drzewo rozpinające nr 2

 

Drzewo rozpinające powstaje przez usunięcie z grafu krawędzi, które tworzą cykl. Drzewo rozpinające możemy utworzyć przy pomocy przejścia DFS (drzewo rozpinające w głąb) lub BFS (drzewo rozpinające wszerz). Zasada tworzenia takiego drzewa jest bardzo prosta: w trakcie przechodzenia przez graf zapamiętywane są tylko przebyte krawędzie. Ponieważ ani DFS, ani BFS nie przechodzą do wierzchołków wcześniej odwiedzonych, metoda ta nie będzie zapamiętywała krawędzi tworzących pętle, czyli to, co zostanie, będzie drzewem rozpinającym. Drzewo rozpinające możemy tworzyć w podobnej strukturze jak sam graf, np. w tablicy list sąsiedztwa.

 

Drzewo rozpinające w głąb

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:
T  –  tablica list sąsiedztwa zawierająca drzewo rozpinające w głąb
Elementy pomocnicze:
u  –  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 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.

 

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

 

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

program DFS_tree;

// Typ listy jednokierunkowej

type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

  TList = array of PslistEl;

// 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 : PslistEl;
  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         : PslistEl;
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.
Code::Blocks
// 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 slistEl
{
  slistEl * next;
  int v;
};

// Zmienne globalne

slistEl ** graf; // Tablica list sąsiedztwa grafu
slistEl ** 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)
{
  slistEl *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 slistEl;       // 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;
  slistEl *p, *r;

  cin >> n >> m;             // Czytamy liczbę wierzchołków i krawędzi
  graf = new slistEl * [n];  // Tworzymy tablicę list sąsiedztwa grafu
  T    = new slistEl * [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 slistEl;         // 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 slistEl;         // 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;
}
Free Basic
' Drzewo rozpinające w głąb
' Data: 22.09.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

' Typ listy jednokierunkowej

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

' Zmienne globalne

Dim Shared As slistEl 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 slistEl 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 slistEl        ' 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 slistEl Ptr p,r

Open Cons For Input As #1

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

graf = New slistEl Ptr [n]   ' Tworzymy tablicę list sąsiedztwa grafu
T    = New slistEl 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 slistEl            ' 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 slistEl            ' 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

 

Drzewo rozpinające wszerz

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:
T  –  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 K05...K10 ; uruchamiamy BFS
K05:     vQ.front();  Q.pop()
    wQ.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 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.

 

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

 

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

program BFS_tree;

// Typ listy jednokierunkowej

type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

  TList = array of PslistEl;

// 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 : PslistEl; x : integer);
var
  p : PslistEl;
begin
  new(p);
  p^.v := x;
  p^.next := L;
  L := p;
end;

// Odczytuje z listy usuwając odczytany element

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

// Zapisuje do kolejki

procedure Q_push(var head, tail : PslistEl; x : integer);
var
  p : PslistEl;
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 : PslistEl) : integer;
var
  p : PslistEl;
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 : PslistEl;    // Kolejka
  p : PslistEl;            // 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 : PslistEl;
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.
Code::Blocks
// 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 slistEl
{
  slistEl * next;
  int v;
};

// Zmienne globalne

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

// Zapisuje na początek listy

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

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

// Odczytuje z listy usuwając odczytany element

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

// Zapisuje do kolejki

void Q_push(slistEl * & head,slistEl * & tail, int x)
{
  slistEl * p = new slistEl;
  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(slistEl * & head,slistEl * & tail)
{
  slistEl * 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)
{
  slistEl * head,* tail;   // Kolejka
  slistEl * 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;
  slistEl * p;

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

  A = new slistEl * [n];  // Tworzymy tablicę list sąsiedztwa grafu
  T = new slistEl * [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;
}
Free Basic
' Drzewo rozpinające wszerz
' Data: 22.09.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

' Typ listy jednokierunkowej

Type slistEl
  next As slistEl 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 slistEl Ptr Ptr A    ' Tablica list sąsiedztwa grafu
Dim Shared As slistEl 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 slistEl Ptr, ByVal x As Integer)

  Dim As slistEl Ptr p = New slistEl

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

' Odczytuje z listy usuwając odczytany element

Function pop(ByRef L As slistEl Ptr) As Integer

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

' Zapisuje do kolejki

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

  Dim As slistEl Ptr p = new slistEl
  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 slistEl Ptr, ByRef tail As slistEl Ptr) As Integer

  Dim As slistEl 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 slistEl Ptr head,tail ' Kolejka
  Dim As slistEl 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 slistEl Ptr p

Open Cons For Input As #1

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

A = new slistEl Ptr [n] ' Tworzymy tablicę list sąsiedztwa grafu
T = new slistEl 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
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 :
 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
 

 



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.