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,vs)

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.
vs : 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: vs[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 vs[u] = true, ; szukamy nieodwiedzonych
       to następny obieg pętli K02 ; 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,vs) ; 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 u 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
  // Tablica list sąsiedztwa grafu
  graf : TList;
  // Tablica list sąsiedztwa
  // drzewa rozpinającego
  T : TList;
  // Tablica odwiedzin
  vs : array of boolean;

// 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
  // Oznaczamy wierzchołek
  // jako odwiedzony
  vs[v] := true;
  // Przeglądamy sąsiadów
  p := graf[v];
  while p <> nil do
  begin
    // u-numer sąsiada
    u := p^.v;
    // Interesują nas tylko
    // nieodwiedzeni sąsiedzi
    if not vs[u] then
    begin
      // Dodajemy u do listy T[v]
      new(r);
      r^.v := u;
      r^.next := T[v];
      T[v] := r;
      // Rekurencyjnie
      // tworzymy drzewo
      DFSTree(u);
    end;
    // Następny sąsiad
    p := p^.next;
  end;
end;

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

var
  i, n, m, v1, v2 : integer;
  p, r : PSLel;
begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablicę
  // list sąsiedztwa grafu
  SetLength(graf, n);
  // Tworzymy tablicę list
  // sąsiedztwa drzewa
  // rozpinającego
  SetLength(T, n);
  // Tworzymy tablicę odwiedzin
  SetLength(vs, n);
  // Tablice wypełniamy 
  // pustymi listami
  for i := 0 to n-1 do
  begin
    graf[i] := nil;
    T[i] := nil;
    vs[i] := false;
  end;
  // Odczytujemy kolejne
  // definicje krawędzi
  for i := 1 to m do
  begin
    // Wierzchołek startowy
    // i końcowy krawędzi
    read(v1, v2);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako v2
    p^.v := v2;
    // Dodajemy go na początek
    // listy A[v1]
    p^.next := graf[v1];
    graf[v1] := p;
    // Teraz krawędź
    // w odwrotną stronę
    new(p);
    p^.v := v1;
    p^.next := graf[v2];
    graf[v2] := p;
  end;
  // Tworzymy drzewo
  // rozpinające w głąb
  //-------------------
  // Czytamy wierzchołek startowy
  read(v1);
  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(vs, 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
//-----------------
// Tablica list sąsiedztwa grafu
SLel ** graf;
// Tablica list sąsiedztwa
// drzewa rozpinającego
SLel ** T;
// Tablica odwiedzin
bool * vs;

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

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

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

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

  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę
  // list sąsiedztwa grafu
  graf = new SLel * [n];
  // Tworzymy tablicę list
  // sąsiedztwa drzewa
  // rozpinającego
  T = new SLel * [n];
  // Tworzymy tablicę odwiedzin
  vs = new bool [n];
  // Tablice wypełniamy
  // pustymi listami
  for(i = 0; i < n; i++)
  {
    graf[i] = T[i] = nullptr;
    vs[i] = false;
  }
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołek startowy
    // i końcowy krawędzi
    cin >> v1 >> v2;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako v2
    p->v = v2;
    // Dodajemy go na początek
    // listy graf[v1]
    p->next = graf[v1];
    graf[v1] = p;
    // Teraz krawędź
    // w odwrotną stronę
    p = new SLel;
    p->v = v1;
    p->next = graf[v2];
    graf[v2] = p;
  }
  // Tworzymy drzewo
  // rozpinające w głąb
  //-------------------
  // Czytamy wierzchołek startowy
  cin >> v1;
  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 [] vs;
  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
'-----------------

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

' 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

  ' Oznaczamy wierzchołek
  ' jako odwiedzony
  vs[v] = 1
  p = graf[v]
  ' Przeglądamy sąsiadów
  while p
    ' u-numer sąsiada
    u = p->v
    ' Interesują nas tylko
    ' nieodwiedzeni sąsiedzi
    If vs[u] = 0 Then
      ' Dodajemy u do listy T[v]
      r = new SLel
      r->v = u
      r->next = T[v]
      T[v] = r
      ' Rekurencyjnie tworzymy
      ' drzewo
      DFSTree(u)
    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
' Czytamy liczbę
' wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę
' list sąsiedztwa grafu
graf = New SLel Ptr [n]
' Tworzymy tablicę
' list sąsiedztwa
' drzewa rozpinającego
T = New SLel Ptr [n]
' Tworzymy tablicę odwiedzin
vs = New Byte [n]
' Tablice wypełniamy
' pustymi listami
For i = 0 To n-1
  graf[i] = 0
  T[i] = 0
  vs[i] = 0
Next
' Odczytujemy kolejne
' definicje krawędzi
For i = 1 To m
  ' Wierzchołek startowy
  ' i końcowy krawędzi
  Input #1, v1, v2
  ' Tworzymy nowy element
  p = New SLel
  ' Numerujemy go jako v2
  p->v = v2
  ' Dodajemy go na początek
  ' listy graf[v1]
  p->next = graf[v1]
  graf[v1] = p
  ' Teraz krawędź w odwrotną stronę
  p = new SLel
  p->v = v1
  p->next = graf[v2]
  graf[v2] = p
Next
' Tworzymy drzewo
' rozpinające w głąb
' Czytamy wierzchołek startowy
Input #1, v1
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 [] vs
Print
End

Python (dodatek)

# Drzewo rozpinające w głąb
# Data: 7.01.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# Klasa listy jednokierunkowej
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0


# Rekurencyjna procedura
# tworzenia drzewa rozpinającego
# w głąb
# v - numer wierzchołka
#     startowego
def dfs_tree(v):
    global vs, graf, t
    # Oznaczamy wierzchołek
    # jako odwiedzony
    vs[v] = 1
    p = graf[v]
    # Przeglądamy sąsiadów
    while p:
        # u - numer sąsiada
        u = p.v
        # Interesują nas tylko
        # nieodwiedzeni sąsiedzi
        if not vs[u]:
            # Dodajemy u do
            # listy t[v]
            r = SLel()
            r.v = u
            r.next = t[v]
            t[v] = r
            # Rekurencyjnie
            # tworzymy drzewo
            dfs_tree(u)
        p = p.next


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Czytamy liczbę
# wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę
# list sąsiedztwa grafu
graf = [None] * n
# Tworzymy tablicę
# list sąsiedztwa
# drzewa rozpinającego
t = [None] * n
# Tworzymy tablicę odwiedzin
vs = [False] * n
# Odczytujemy kolejne
# definicje krawędzi
for i in range(m):
    # Wierzchołek startowy
    # i końcowy krawędzi
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako v2
    p.v = v2
    # Dodajemy go na początek
    # listy graf[v1]
    p.next = graf[v1]
    graf[v1] = p
    # Teraz krawędź
    # w odwrotną stronę
    p = SLel()
    p.v = v1
    p.next = graf[v2]
    graf[v2] = p
# Tworzymy drzewo
# rozpinające w głąb
# Czytamy wierzchołek startowy
v1 = int(input())
dfs_tree(v1)
# Wyświetlamy tablicę list
# sąsiedztwa drzewa
# rozpinającego
print()
for i in range(n):
    print("%2d :" % i, end="")
    p = t[i]
    while p:
        print("%3d" % p.v,
              end="")
        p = p.next
    print()
# Usuwamy dynamiczne
# struktury danych
for i in range(n):
    while graf[i]:
        graf[i] = graf[i].next
    while t[i]:
        t[i] = t[i].next
del graf,t,vs
print()

Wynik:

do podrozdziału do 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ć, iż 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 drzewa rozpinającego; v ∈ C.
graf : zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.
vs : 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: vs[v] ← true ; oznaczamy wierzchołek v jako odwiedzony
K04: Dopóki Q.empty() = false: ; uruchamiamy BFS
     wykonuj kroki K05…K10
K05:   v ← Q.front(); Q.pop() ; pobieramy z kolejki krawędź v–w
       w ← Q.front(); Q.pop()
K06:   Jeśli v > -1, ; krawędź v – w dodajemy do drzewa T
       to dodaj w do listy T[v]
K07:   Dla każdego sąsiada z wierzchołka w:
       wykonuj kroki K18…K10
K08:     Jeśli vs[z] = true, ; szukamy nieodwiedzonego sąsiada
         to następny obieg pętli K07
K09:     vs[z] ← true ; sąsiada oznaczamy jako odwiedzonego
K10:     Q.push(w) ; i krawędź w-z umieszczamy w kolejce
         Q.push(z)
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
  // Liczba wierzchołków n
  // i krawędzi m
  n, m : integer;
  // Tablica list sąsiedztwa grafu
  A : TList;
  // Tablica list sąsiedztwa
  // drzewa rozpinającego
  T : TList;
  vs : 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
  if head <> nil then
  begin
    Q_pop := head^.v;
    p := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose(p)
  end
  else Q_pop := -2
end;

// Tworzy drzewo rozpinające
procedure BFSTree(v : integer);
var
  // Kolejka
  head, tail : PSLel;
  // Wskaźnik węzłów na liście
  p : PSLel;
  w, z : integer;

begin
  // Tworzymy pustą kolejkę
  head := nil;
  tail := nil;
  // W kolejce umieszczamy
  // krawędź -1-v
  Q_push(head, tail, -1);
  Q_push(head, tail, v);
  // Oznaczamy v jako odwiedzony
  vs[v] := true;
  // Uruchamiamy BFS
  while head <> nil do
  begin
    // Pobieramy parę v-w z kolejki
    v := Q_pop(head, tail);
    w := Q_pop(head, tail);
    // w dodajemy do listy T[v]
    if v > -1 then push(T[v], w);
    // Sąsiadów w umieszczamy
    // w kolejce
    p := A[w];
    while p <> nil do
    begin
      z := p^.v;
      if not vs[z] then
      begin
        vs[z] := true;
        // Do kolejki para w-sąsiad
        Q_push(head, tail, w);
        Q_push(head, tail, z);
      end;
      p := p^.next;
    end;
  end;
end;

var
  i, v1, v2 : integer;
  p : PSLel;
begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablicę list
  // sąsiedztwa grafu
  SetLength(A, n);
  // Tworzymy tablicę list
  // sąsiedztwa drzewa
  SetLength(T, n);
  // Tworzymy tablicę odwiedzin
  SetLength(vs, n);
  // Tablice inicjujemy
  for i := 0 to n-1 do
  begin
    A[i] := nil;
    T[i] := nil;
    vs[i] := false;
  end;
  // Odczytujemy kolejne
  // definicje krawędzi
  for i := 1 to m do
  begin
    // Wierzchołek startowy
    // i końcowy krawędzi
    read(v1, v2);
    // Krawędź v1-v2
    push(A[v1], v2);
    // Krawędź v2-v1
    push(A[v2], v1);
  end;
  // Tworzymy drzewo
  // rozpinające wszerz
  //-------------------
  // Czytamy wierzchołek startowy
  read(v1);
  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(vs, 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
//-----------------

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

// 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;
  if(L)
  {
    x = L->v;
    SLel * p = L;
    L = L->next;
    delete p;
  }
  else x = -2;
  return x;
}

// Zapisuje do kolejki
void Q_push(SLel * & head,
            SLel * & tail,
            int x)
{
  SLel * p = new SLel;
  p->next = nullptr;
  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)
{
  int x;
  SLel * p = head;
  if(p)
  {
    x = head->v;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  }
  else x = -2;
  return x;
}

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

  // Tworzymy pustą kolejkę
  head = tail = nullptr;
  // W kolejce umieszczamy
  // krawędź -1-v
  Q_push(head, tail, -1);
  Q_push(head, tail, v);
  // Oznaczamy v jako odwiedzony
  vs[v] = true;
  // Uruchamiamy BFS
  while(head)
  {
    // Pobieramy parę v-w z kolejki
    v = Q_pop(head, tail);
    w = Q_pop(head, tail);
    if(v > -1)
      // w dodajemy do listy T[v]
      push(T[v], w);
    // Sąsiadów wierzchołka w
    // umieszczamy w kolejce
    for(p = A[w]; p; p = p->next)
    {
      z = p->v;
      if(!vs[z])
      {
        vs[z] = true;
        // Do kolejki para w-sąsiad
        Q_push(head, tail, w);
        Q_push(head, tail, z);
      }
    }
  }
}

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

  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę list
  // sąsiedztwa grafu
  A = new SLel * [n];
  // Tworzymy tablicę list
  // sąsiedztwa drzewa
  // rozpinającego
  T = new SLel * [n];
  // Tworzymy tablicę odwiedzin
  vs = new bool [n];
  // Tablice inicjujemy
  for(i = 0; i < n; i++)
  {
    A[i] = T[i] = nullptr;
    vs[i] = false;
  }
  // Odczytujemy kolejne
  // definicje krawędzi

  for(i = 0; i < m; i++)
  {
    // Wierzchołek startowy
    // i końcowy krawędzi
    cin >> v1 >> v2;
    // Krawędź v1-v2
    push(A[v1], v2);
    // Krawędź v2-v1
    push(A[v2], v1);
  }
  // Tworzymy drzewo
  // rozpinające wszerz
  //-------------------
  // Czytamy wierzchołek startowy
  cin >> v1;
  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 [] vs;
  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
'-----------------
' Liczba wierzchołków n i krawędzi m
Dim Shared As Integer n, m
' Tablica list sąsiedztwa grafu
Dim Shared As SLel Ptr Ptr A
' Tablica list sąsiedztwa drzewa
' rozpinającego
Dim Shared As SLel Ptr Ptr T
' Tablica odwiedzin
Dim Shared As Byte Ptr vs

' 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
  Dim As SLel Ptr p = L
  If L <> 0 Then
    x = L->v
    L = L->Next
    Delete p
  Else
    x = -2
  End If
  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
  If head <> 0 Then
    x = head->v
    head = head->Next
    If head = 0 Then tail = 0
    delete p
  Else
    x = -2
  End If
  Return x
End Function

' Tworzy drzewo rozpinające
Sub BFSTree(ByVal v As Integer)
  ' Kolejka
  Dim As SLel Ptr head, tail
  ' Wskaźnik węzłów na liscie
  Dim As SLel Ptr p
  Dim As Integer w, z
  ' Tworzymy pustą kolejkę
  head = 0
  tail = 0
  ' W kolejce umieszczamy krawędź -1-v
  Q_push(head, tail, -1)
  Q_push(head, tail, v)
  ' Oznaczamy v jako odwiedzony
  vs[v] = 1
  ' Uruchamiamy BFS
  While head <> 0
    ' Pobieramy parę v-w z kolejki
    v = Q_pop(head, tail)
    w = Q_pop(head, tail)
    ' w dodajemy do listy T[v]
    If v > -1 Then push(T[v], w)
    p = A[w]
    ' Sąsiadów wierzchołka w
    ' umieszczamy w kolejce
    While p <> 0
      z = p->v
      if vs[z] = 0 Then
        vs[z] = 1
        ' Do kolejki para w-sąsiad
        Q_push(head, tail, w)
        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
' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę list sąsiedztwa grafu
A = new SLel Ptr [n]
' Tworzymy tablicę list sąsiedztwa
' drzewa rozpinającego
T = new SLel Ptr [n]
' Tworzymy tablicę odwiedzin
vs = New Byte [n]
' Tablice inicjujemy
For i = 0 To n-1
  A[i] = 0
  T[i] = 0
  vs[i] = 0
Next
' Odczytujemy kolejne definicje krawędzi
For i = 1 To m
  ' Wierzchołek startowy i końcowy krawędzi
  Input #1, v1, v2
  ' Krawędź v1-v2
  push(A[v1], v2)
  ' Krawędź v2-v1
  push(A[v2], v1)
Next
' Tworzymy drzewo rozpinające wszerz
'-----------------------------------
' Czytamy wierzchołek startowy
Input #1, v1
BFSTree (v1)
Close #1
' Wyświetlamy tablicę list sąsiedztwa
' drzewa rozpinającego
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] <> 0
    pop(A[i])
  Wend
  While T[i] <> 0
    pop(T[i])
  Wend
Next
Delete [] A
Delete [] T
Delete [] vs
Print
End

Python (dodatek)

# Drzewo rozpinające wszerz
# Data: 8.01.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# Klasa listy jednokierunkowej
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0

# Klasa kolejki
class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    # Zapisuje do kolejki
    def push(self, x):
        p = SLel()
        p.next = None
        p.v = x
        if not self.tail:
            self.head = p
        else:
            self.tail.next = p
        self.tail = p


    # Odczytuje z kolejki,
    # usuwając element
    def pop(self):
        if self.head:
            x = self.head.v
            self.head = self.head.next
            if not self.head:
                self.tail = None
        else:
            x = -2
        return x


# Zapisuje na początek listy
def push(lst, x):
    p = SLel()
    p.v = x
    p.next = lst
    lst = p
    return lst


# Odczytuje z listy,
def pop(lst):
    if lst:
        lst = lst.next
    return lst


# Tworzy drzewo rozpinające
def bfs_tree(v):
    global vs, t, a
    # Tworzymy pustą kolejkę
    q = Queue()
    # W kolejce umieszczamy
    # krawędź -1-v
    q.push(-1)
    q.push(v)
    # Oznaczamy v jako odwiedzony
    vs[v] = True
    # Uruchamiamy BFS
    while q.head:
        # Pobieramy parę v-w
        # z kolejki
        v = q.pop()
        w = q.pop()
        # w dodajemy do listy T[v]
        if v > -1:
            t[v] = push(t[v], w)
        p = a[w]
        # Sąsiadów wierzchołka w
        # umieszczamy w kolejce
        while p:
            z = p.v
            if not vs[z]:
                vs[z] = True
                # Do kolejki
                # para w-sąsiad
                q.push(w)
                q.push(z)
            p = p.next


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Czytamy liczbę wierzchołków
# i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę list
# sąsiedztwa grafu
a = [None] * n
# Tworzymy tablicę list sąsiedztwa
# drzewa rozpinającego
t = [None] * n
# Tworzymy tablicę odwiedzin
vs = [False] * n
# Odczytujemy kolejne
# definicje krawędzi
for i in range(m):
    # Wierzchołek startowy
    # i końcowy krawędzi
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    # Krawędź v1-v2
    a[v1] = push(a[v1], v2)
    # Krawędź v2-v1
    a[v2] = push(a[v2], v1)
# Tworzymy drzewo rozpinające wszerz
#-----------------------------------
# Czytamy wierzchołek startowy
v1 = int(input())
bfs_tree(v1)
# Wyświetlamy tablicę list sąsiedztwa
# drzewa rozpinającego
print()
for i in range(n):
    print("%2d :" % i, end="")
    p = t[i]
    while p:
        print("%3d" % p.v, end="")
        p = p.next
    print()
# Usuwamy tablice dynamiczne
for i in range(n):
    while a[i]:  a[i] = pop(a[i])
    while t[i]:  t[i] = pop(t[i])
del a, t, vs
print()

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
obrazek

Drzewo rozpinające wszerz
obrazek

do podrozdziału do 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,vs)

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