Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2021 mgr Jerzy Wałaszek
I LO w Tarnowie

Drzewa rozpinające grafu

SPIS TREŚCI
Podrozdziały

Problem

Dla danego grafu należy 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:

obrazek
Graf podstawowy
     obrazek
Drzewo rozpinające nr 1
     obrazek
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.
Zmienne 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 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 ):
obrazek        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
  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.
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 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;
}
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
obrazek
Na początek:  podrozdziału   strony 

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.
Zmienne 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 ):
obrazek        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
  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.
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 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;
}
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:
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
obrazek

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

Drzewo rozpinające w głąb      Drzewo rozpinające wszerz
obrazek   obrazek
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2021 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.