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

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Przechodzenie grafów w głąb – DFS

SPIS TREŚCI W KONSERWACJI
Podrozdziały

Problem

Dokonać przejścia grafu w głąb.

Algorytm DFS

Przejście grafu (ang. graph traversal) polega na przechodzeniu przez wierzchołki, do których prowadzą ścieżki. Algorytm przejścia daje nam pewność, że żaden taki wierzchołek nie zostanie pominięty, Algorytm przejścia/przeszukiwania w głąb (ang. Depth First Search - DFS) omówiony został w rozdziale o przechodzeniu drzew binarnych. W przypadku grafu istnieje pewna trudność, która nie pojawiała się przy drzewach – w grafach krawędzie mogą tworzyć cykle lub pętle, czyli prowadzić do tego samego wierzchołka. Powoduje to konieczność modyfikacji podstawowego algorytmu w celu wyeliminowania zapętlenia się. Rozwiązaniem jest wprowadzenie dla każdego wierzchołka dodatkowego składnika, który będzie informował algorytm, czy wierzchołek ten został już odwiedzony. Dzięki temu algorytm nie będzie w kółko krążył po wierzchołkach tworzących cykl. Umówmy się, że parametr ten nazwiemy visited i będzie on miał wartość logiczną false, gdy wierzchołek jeszcze nie był odwiedzony, a true, gdy algorytm odwiedził dany wierzchołek. Do przechowywania parametrów visited można wykorzystać osobną tablicę o tylu elementach, ile mamy wierzchołków w grafie. Przed rozpoczęciem przejścia tablica visited powinna być wyzerowana (tzn. wszystkie jej elementy należy ustawić na wartość logiczną false)..

Zasada działania DFS jest następująca:

Zaznaczamy bieżący wierzchołek jako odwiedzony. Przechodzimy do kolejnych sąsiadów wierzchołka bieżącego i wykonujemy dla nich tą samą operację (tzn. zaznaczamy je jako odwiedzone i przechodzimy do ich sąsiadów). Przechodzenie kończymy, gdy zostaną w ten sposób odwiedzone wszystkie dostępne wierzchołki.

Prześledźmy algorytm DFS dla poniższego grafu:

obrazek Przejście rozpoczynamy od wierzchołka v0.
obrazek Wierzchołek v0 oznaczamy jako odwiedzony (kolor zielony) i przechodzimy do jego sąsiada v1.
obrazek Wierzchołek v1 oznaczamy jako odwiedzony. Ponieważ nie ma on sąsiadów, to ta gałąź przejścia jest ślepa i już dalej nie biegnie.
obrazek Przechodzimy do kolejnego sąsiada wierzchołka v0, czyli do v5.
obrazek Wierzchołek v5 oznaczamy jako odwiedzony. Wierzchołek ten posiada dwóch sąsiadów: v1 i v2. Do v1 nie będziemy przechodzić, ponieważ jest on oznaczony jako już odwiedzony.
obrazek Przechodzimy do v2.
obrazek Wierzchołek v2 oznaczamy jako odwiedzony. Posiada on dwóch sąsiadów: v1 (już odwiedzony) oraz v3.
obrazek Przechodzimy do v3.
obrazek Zaznaczamy v3 jako odwiedzony. Wierzchołek v3 posiada tylko jednego sąsiada: v4.
obrazek Przechodzimy do v4.
obrazek Zaznaczamy v4 jako odwiedzony. Wierzchołek v4 posiada dwóch sąsiadów, v1 i v5, lecz oba te wierzchołki są już odwiedzone. Przejście kończymy, ponieważ w grafie nie ma już dalszych wierzchołków, do których moglibyśmy przejść.

Kolejno odwiedzone wierzchołki: v0 v1 v5 v2 v3 v4


Na początek:  podrozdziału   strony 

Rekurencyjny algorytm DFS

Algorytm DFS występuje w dwóch postaciach: rekurencyjnej i stosowej. Implementacja algorytmu zależy od wybranej reprezentacji grafu.

Algorytm rekurencyjny DFS – wersja poglądowa: DFS (v)

Wejście:

v  :  numer wierzchołka startowego, v ∈ C.
visited  :  tablica logiczna n elementowa z informacją o odwiedzonych wierzchołkach.
graf  :  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

Przetworzenie wszystkich wierzchołków w grafie.
Zmienne pomocnicze:
u  :  wierzchołek roboczy, w ∈ C.

Lista kroków:

K01: visited [v] ← true odwiedź wierzchołek
K02: Przetwórz wierzchołek v przetwarzanie wstępne
K03: Dla każdego sąsiada u wierzchołka v,
wykonuj: jeśli visited [u ] = false, to DFS (u)
odwiedź algorytmem DFS każdego nieodwiedzonego sąsiada
K04: Przetwórz wierzchołek v przetwarzanie końcowe
K03: Zakończ  

Algorytm rekurencyjny DFS dla macierzy sąsiedztwa: DFS (v)

Wejście:

n  :  liczba wierzchołków, n ∈ C.
v  :  numer wierzchołka startowego, v ∈ C.
visited  :  n-elementowa tablica logiczna z informacją o odwiedzonych wierzchołkach.
A  :  macierz sąsiedztwa o rozmiarze n × n.

Wyjście:

Przetworzenie wszystkich wierzchołków w grafie.
Zmienne pomocnicze:
i  :  indeks. i ∈ C.

Lista kroków:

K01: visited [v] ← true odwiedź wierzchołek
K02: Przetwórz wierzchołek v przetwarzanie wstępne
K03: Dla i = 0, 1, ..., n-1, wykonuj:
Jeśli (A [v][i] = 1) obrazek (visited [i] = false),
to DFS (i)
odwiedź algorytmem DFS każdego nieodwiedzonego sąsiada
K04: Przetwórz wierzchołek v przetwarzanie końcowe
K05: Zakończ  

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 odczytuje definicję grafu skierowanego, tworzy dla niego macierz sąsiedztwa, a następnie przechodzi ten graf rekurencyjnym algorytmem DFS rozpoczynając od wierzchołka o numerze 0. Na wyjście są wyprowadzane numery kolejno odwiedzanych wierzchołków. Macierz sąsiedztwa i tablica odwiedzin są zadane globalnie, aby uprościć wywołania rekurencyjne.
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):
obrazek 6 9
0 5
0 1
5 2
5 1
4 1
4 5
3 4
2 1
2 3
Pascal
// Rekurencyjne DFS - macierz sąsiedztwa
// Data: 22.07.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------

program rdfs_adj;

// Typy dla dynamicznej macierzy
type
  nptr = array of byte;  // Wiersz
  mptr = array of nptr;  // Cała macierz

// Zmienne globalne
var
  n : integer;           // Liczba wierzchołków
  A : mptr;              // Macierz sąsiedztwa
  visited : array of boolean; // Tablica odwiedzin

// Rekurencyjna procedura przejścia w głąb
//----------------------------------------
procedure DFS (v : integer);
var
  i : integer;
begin
  visited [v] := true; // Zaznaczamy węzeł jako odwiedzony
  write (v:3);            // Przetwarzamy węzeł (wypisujemy jego numer)

// Rekurencyjnie odwiedzamy nieodwiedzonych sąsiadów

  for i := 0 to n - 1 do
    if(A [v][i] = 1) and (visited [i] = false) then DFS (i);
end;

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

var
  m, i, j, v1, v2 : integer;

begin
  read (n, m);              // Czytamy liczbę wierzchołków i krawędzi

  SetLength (A, n);         // Tworzymy tablicę wskaźników
  SetLength (visited, n);   // Tworzymy tablicę odwiedzin

  for i := 0 to n - 1 do
    SetLength (A [i], n); // Tworzymy wiersze

  // Macierz wypełniamy zerami

  for i := 0 to n - 1 do
  begin
    visited [i] := false; // Zerujemy tablicę odwiedzin
    for j := 0 to n - 1 do A [i][j] := 0;
  end;

  // Odczytujemy kolejne definicje krawędzi

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

  writeln;

  // Przechodzimy graf w głąb

  DFS (0);

  // Usuwamy macierz

  for i := 0 to n - 1 do SetLength (A [i], 0);
  SetLength (A, 0);
  SetLength (visited, 0);

  writeln;
end.
C++
// Rekurencyjne DFS - macierz sąsiedztwa
// Data: 22.07.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Zmienne globalne

int n;                   // Liczba wierzchołków
char ** A;               // Macierz sąsiedztwa
bool * visited;          // Tablica odwiedzin

// Rekurencyjna procedura przejścia w głąb
//----------------------------------------
void DFS (int v)
{
  int i;

  visited [v] = true;  // Zaznaczamy węzeł jako odwiedzony
  cout << setw (3) << v;  // Przetwarzamy węzeł (wypisujemy jego numer)

// Rekurencyjnie odwiedzamy nieodwiedzonych sąsiadów

  for(i = 0; i < n; i++)
    if((A [v][i] == 1) && !visited [i]) DFS (i);
}

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

int main()
{
  int m, i, j, v1, v2;

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

  A = new char * [n];       // Tworzymy tablicę wskaźników
  visited = new bool [n];   // Tworzymy tablicę odwiedzin

  for(i = 0; i < n; i++)
    A [i] = new char [n]; // Tworzymy wiersze

  // Macierz wypełniamy zerami

  for(i = 0; i < n; i++)
  {
    visited [i] = false;  // Zerujemy tablicę odwiedzin
    for(j = 0; j < n; j++) A [i][j] = 0;
  }

  // Odczytujemy kolejne definicje krawędzi

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

  cout << endl;

  // Przechodzimy graf w głąb

  DFS (0);

  // Usuwamy macierz

  for(i = 0; i < n; i++) delete A [i];
  delete [] A;
  delete [] visited;

  cout << endl;

  return 0;}
Basic
' Rekurencyjne DFS - macierz sąsiedztwa
' Data: 22.07.2013
' (C)2013 mgr Jerzy Wałaszek
'--------------------------------------

' Zmienne globalne

Dim Shared As Integer n         ' Liczba wierzchołków
Dim Shared As Byte Ptr Ptr A    ' Macierz sąsiedztwa
Dim Shared As Byte Ptr visited  ' Tablica odwiedzin

' Rekurencyjna procedura przejścia w głąb
'----------------------------------------
Sub DFS (ByVal v As Integer)
  
  Dim As Integer i

  visited [v] = 1    ' Zaznaczamy węzeł jako odwiedzony
  Print Using "###";v; ' Przetwarzamy węzeł (wypisujemy jego numer)

' Rekurencyjnie odwiedzamy nieodwiedzonych sąsiadów

  For i = 0 To n - 1
    if(A [v][i] = 1) AndAlso (visited [i] = 0) Then DFS (i)
  Next
End Sub

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

Dim As Integer m, i, j, v1, v2

Open Cons For Input As #1

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

A = New Byte Ptr [n]     ' Tworzymy tablicę wskaźników
visited = New Byte [n]   ' Tworzymy tablicę odwiedzin

For i = 0 To n - 1
  A [i] = New Byte [n] ' Tworzymy wiersze
Next

' Macierz wypełniamy zerami

For i = 0 To n - 1
  visited [i] = 0     ' Zerujemy tablicę odwiedzin
  For j = 0 To n - 1
    A [i][j] = 0
  Next
Next

' Odczytujemy kolejne definicje krawędzi

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

Close #1

Print

' Przechodzimy graf w głąb

DFS (0)

' Usuwamy macierz

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

Print

End
Wynik:
6 9
0 5
0 1
5 2
5 1
4 1
4 5
3 4
2 1
2 3

0 1 5 2 3 4

Algorytm rekurencyjny DFS dla macierzy incydencji: DFS (v)

Wejście:

n  :  liczba wierzchołków, n ∈ C.
m  :  liczba krawędzi, m ∈ C.
v  :  numer wierzchołka startowego, v ∈ C.
visited  :  n-elementowa tablica logiczna z informacją o odwiedzonych wierzchołkach.
A  :  macierz incydencji o rozmiarze n × m.

Wyjście:

Przetworzenie wszystkich wierzchołków w grafie.
Zmienne pomocnicze:
i, j  :  indeksy. i, j ∈ C.

Lista kroków:

K01: visited [v] ← true odwiedź wierzchołek
K02: Przetwórz wierzchołek v przetwarzanie wstępne
K03: Dla i = 0, 1, ..., m - 1:
wykonuj kroki K04...K08
przeszukujemy kolejne krawędzie
K04: Jeśli A [v][i] ≠ 1,
to następny obieg pętli K03
szukamy krawędzi, dla której v jest wierzchołkiem startowym
K05: Dla j = 0, 1, ..., n - 1:
wykonuj kroki K06...K08
 
K06: Jeśli A [j][i] ≠ -1,
to następny obieg pętli K05
szukamy wierzchołka końcowego
K07: Jeśli visited [j] = false,
to DFS (j)
rekurencyjnie odwiedzamy znalezionego sąsiada
K08: Następny obieg pętli K03 kontynuujemy szukanie dalszych sąsiadów
K09: Przetwórz wierzchołek v przetwarzanie końcowe
K10: Zakończ  

Zwróć uwagę, że reprezentacja grafu macierzą incydencji nie jest wygodna dla algorytmu DFS.


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 odczytuje definicję grafu skierowanego, tworzy dla niego macierz incydencji, a następnie przechodzi ten graf rekurencyjnym algorytmem DFS rozpoczynając od wierzchołka o numerze 0. Na wyjście są wyprowadzane numery kolejno odwiedzanych wierzchołków. Macierz incydencji i tablica odwiedzin są zadane globalnie, aby uprościć wywołania rekurencyjne.
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):
obrazek 6 9
0 5
0 1
5 2
5 1
4 1
4 5
3 4
2 1
2 3
Pascal
// Rekurencyjne DFS - macierz incydencji
// Data: 22.07.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------

program rdfs_inc;

// Typy dla dynamicznej macierzy
type
  nptr = array of shortint; // Wiersz
  mptr = array of nptr;     // Cała macierz

// Zmienne globalne
var
  n, m : integer;             // Liczba wierzchołków i krawędzi
  A : mptr;                   // Macierz incydencji
  visited : array of boolean; // Tablica odwiedzin

// Rekurencyjna procedura przejścia w głąb
//----------------------------------------
procedure DFS (v : integer);
var
  i, j : integer;
begin
  visited [v] := true; // Zaznaczamy węzeł jako odwiedzony
  write (v:3);            // Przetwarzamy węzeł (wypisujemy jego numer)

// Rekurencyjnie odwiedzamy nieodwiedzonych sąsiadów

  for i := 0 to m - 1 do
    if A [v][i] = 1 then
      for j := 0 to n - 1 do
        if A [j][i] = -1 then
        begin
          if visited [j] = false then DFS (j);
          break;
        end;
end;

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

var
  i, j, v1, v2 : integer;

begin
  read (n, m);             // Czytamy liczbę wierzchołków i krawędzi

  SetLength (A, n);        // Tworzymy tablicę wskaźników
  SetLength (visited, n);  // Tworzymy tablicę odwiedzin

  for i := 0 to n - 1 do
    SetLength (A [i], m);   // Tworzymy wiersze

  // Macierz wypełniamy zerami

  for i := 0 to n - 1 do
  begin
    visited [i] := false; // Zerujemy tablicę odwiedzin
    for j := 0 to m - 1 do A [i][j] := 0;
  end;

  // Odczytujemy kolejne definicje krawędzi

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

  writeln;

  // Przechodzimy graf w głąb

  DFS (0);

  // Usuwamy macierz

  for i := 0 to n - 1 do SetLength (A [i], 0);
  SetLength (A, 0);
  SetLength (visited, 0);

  writeln;
 
end.
C++
// Rekurencyjne DFS - macierz incydencji
// Data: 22.07.2013
// (C)2013 mgr Jerzy Wałaszek
//--------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Zmienne globalne

int n, m;         // Liczba wierzchołków
signed char ** A; // Macierz incydencji
bool * visited;   // Tablica odwiedzin

// Rekurencyjna procedura przejścia w głąb
//----------------------------------------
void DFS (int v)
{
  int i, j;

  visited [v] = true;  // Zaznaczamy węzeł jako odwiedzony
  cout << setw (3) << v;  // Przetwarzamy węzeł (wypisujemy jego numer)

// Rekurencyjnie odwiedzamy nieodwiedzonych sąsiadów

  for(i = 0; i < m; i++)
    if(A [v][i] == 1)
      for(j = 0; j < n; j++)
        if(A [j][i] == -1)
        {
          if(!visited [j]) DFS (j);
          break;
        }
}

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

int main()
{
  int i, j, v1, v2;

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

  A = new signed char * [n]; // Tworzymy tablicę wskaźników
  visited = new bool [n];    // Tworzymy tablicę odwiedzin

  for(i = 0; i < n; i++)
    A [i] = new signed char [m]; // Tworzymy wiersze

  // Macierz wypełniamy zerami

  for(i = 0; i < n; i++)
  {
    visited [i] = false;        // Zerujemy tablicę odwiedzin
    for(j = 0; j < m; j++) A [i][j] = 0;
  }

  // Odczytujemy kolejne definicje krawędzi

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

  cout << endl;

  // Przechodzimy graf w głąb

  DFS (0);

  // Usuwamy macierz

  for(i = 0; i < n; i++) delete A [i];
  delete [] A;
  delete [] visited;

  cout << endl;

  return 0;}
Basic
' Rekurencyjne DFS - macierz incydencji
' Data: 22.07.2013
' (C)2013 mgr Jerzy Wałaszek
'--------------------------------------

' Zmienne globalne

Dim Shared As Integer n, m     ' Liczba wierzchołków
Dim Shared As Byte Ptr Ptr A   ' Macierz incydencji
Dim Shared As Byte Ptr visited ' Tablica odwiedzin

' Rekurencyjna procedura przejścia w głąb
'----------------------------------------
Sub DFS (ByVal v As Integer)
  
  Dim As Integer i, j

  visited [v] = 1     ' Zaznaczamy węzeł jako odwiedzony
  Print Using "###";v;  ' Przetwarzamy węzeł (wypisujemy jego numer)

' Rekurencyjnie odwiedzamy nieodwiedzonych sąsiadów

  For i = 0 To m - 1
    If A [v][i] = 1 Then
      For j = 0 To n - 1
        If A [j][i] = -1 Then
          If visited [j] = 0 Then DFS (j)
          Exit For
        End If
      Next
    End If
  Next
End Sub

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

Dim As Integer i, j, v1, v2

Open Cons For Input As #1

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

A = New Byte Ptr [n]     ' Tworzymy tablicę wskaźników
visited = New Byte [n]   ' Tworzymy tablicę odwiedzin

For i = 0 To n - 1
  A [i] = New Byte [m] ' Tworzymy wiersze
Next

' Macierz wypełniamy zerami

For i = 0 To n - 1
  visited [i] = 0        ' Zerujemy tablicę odwiedzin
  For j = 0 To m - 1
  	 A [i][j] = 0
  Next
Next

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m - 1
  Input #1, v1, v2  ' Wierzchołek startowy i końcowy krawędzi
  A [v1][i] = 1 ' Wierzchołek startowy
  A [v2][i] =-1 ' Wierzchołek końcowy
Next

Close #1

Print

' Przechodzimy graf w głąb

DFS (0)

' Usuwamy macierz

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

Print

End
Wynik:
6 9
0 5
0 1
5 2
5 1
4 1
4 5
3 4
2 1
2 3

 0 5 2 1 3 4

Algorytm rekurencyjny DFS dla list sąsiedztwa: DFS (v)

Wejście:

n  :  liczba wierzchołków, n ∈ C.
v  :  numer wierzchołka startowego, v ∈ C.
visited  :  n elementowa tablica logiczna z informacją o odwiedzonych wierzchołkach.
A  :  n elementowa tablica list sąsiedztwa.

Wyjście:

Przetworzenie wszystkich wierzchołków w grafie.
Zmienne pomocnicze:
p  :  wskaźnik elementu listy sąsiedztwa.

Lista kroków:

K01: visited [v] ← true odwiedź wierzchołek
K02: Przetwórz wierzchołek v przetwarzanie wstępne
K03: p ← A [v] rozpoczynamy od początku listy
K04 Dopóki p ≠ nil:
wykonuj kroki K05...K06
 
K05: Jeśli visited [p→v] = false,
to DFS (p→v)
odwiedzamy nieodwiedzonych sąsiadów
K06: p ← (p→next) idziemy do kolejnego sąsiada
K07: Przetwórz wierzchołek v przetwarzanie końcowe
K08: Zakończ  

Reprezentacja grafu tablicą list sąsiedztwa jest korzystna dla algorytmu DFS, ponieważ pętla wyszukująca sąsiadów nie wykonuje pustych przebiegów –  każdy element listy sąsiedztwa jest sąsiadem.


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 odczytuje definicję grafu skierowanego, tworzy dla niego tablicę list sąsiedztwa, a następnie przechodzi ten graf rekurencyjnym algorytmem DFS rozpoczynając od wierzchołka o numerze 0. Na wyjście są wyprowadzane numery kolejno odwiedzanych wierzchołków. Tablica list sąsiedztwa i tablica odwiedzin są zadane globalnie, aby uprościć wywołania rekurencyjne. Listy sąsiedztwa są tworzone na bazie listy jednokierunkowej.
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):
obrazek 6 9
0 5
0 1
5 2
5 1
4 1
4 5
3 4
2 1
2 3
Pascal
// Rekurencyjne DFS - listy sąsiedztwa
// Data: 22.07.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------------

program rdfs_adjl;

// Typy dla dynamicznej tablicy list sąsiedztwa
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

  TList = array of PslistEl;


// Zmienne globalne
var
  n : integer;           // Liczba wierzchołków i krawędzi
  A : TList;             // Tablica list sąsiedztwa
  visited : array of boolean; // Tablica odwiedzin

// Rekurencyjna procedura przejścia w głąb
//----------------------------------------
procedure DFS (v : integer);
var
  p : PslistEl;
begin
  visited [v] := true;   // Zaznaczamy węzeł jako odwiedzony
  write (v:3);           // Przetwarzamy węzeł (wypisujemy jego numer)

// Rekurencyjnie odwiedzamy nieodwiedzonych sąsiadów

  p := A [v];

  while p <> nil do
  begin
    if visited [p^.v] = false then DFS (p^.v);
    p := p^.next;
  end;
end;

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

var
  m, i, v1, v2 : integer;
  p, r : PslistEl;

begin
  read (n, m);             // Czytamy liczbę wierzchołków i krawędzi

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

  // Tablice wypełniamy pustymi listami

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

  // Odczytujemy kolejne definicje krawędzi

  for i := 0 to m - 1 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 := A [v1];   // Dodajemy go na początek listy A [v1] 
    A [v1] := p;
  end;

  writeln;

  // Przechodzimy graf w głąb

  DFS (0);

  // Usuwamy tablicę list sąsiedztwa

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

  SetLength (A, 0);

  SetLength (visited, 0);

  writeln;
 
end.
C++
// Rekurencyjne DFS - listy sąsiedztwa
// Data: 22.07.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa

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

// Zmienne globalne

int n;                   // Liczba wierzchołków
slistEl ** A;            // Macierz sąsiedztwa
bool * visited;          // Tablica odwiedzin

// Rekurencyjna procedura przejścia w głąb
//----------------------------------------
void DFS (int v)
{
  slistEl * p;

  visited [v] = true;     // Zaznaczamy węzeł jako odwiedzony
  cout << setw (3) << v;  // Przetwarzamy węzeł (wypisujemy jego numer)

// Rekurencyjnie odwiedzamy nieodwiedzonych sąsiadów

  for(p = A [v]; p; p = p->next)
    if(!visited [p->v]) DFS (p->v);
}

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

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

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

  A = new slistEl * [n];       // Tworzymy tablicę list sąsiedztwa
  visited = new bool [n];       // Tworzymy tablicę odwiedzin

  // Tablicę wypełniamy pustymi listami

  for(i = 0; i < n; i++)
  {
    A [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 = A [v1];    // Dodajemy go na początek listy A [v1] 
    A [v1] = p;
  }

  cout << endl;

  // Przechodzimy graf w głąb

  DFS (0);

  // Usuwamy tablicę list sąsiedztwa

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

  cout << endl;

  return 0;}
Basic
' Rekurencyjne DFS - listy sąsiedztwa
' Data: 22.07.2013
' (C)2013 mgr Jerzy Wałaszek
'--------------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

' Zmienne globalne

Dim Shared As Integer n                   ' Liczba wierzchołków
Dim Shared As slistEl Ptr Ptr A           ' Tablica list sąsiedztwa
Dim Shared As Byte Ptr visited            ' Tablica odwiedzin

' Rekurencyjna procedura przejścia w głąb
'----------------------------------------
Sub DFS (ByVal v As Integer)
  
  Dim As slistEl Ptr p

  visited [v] = 1        ' Zaznaczamy węzeł jako odwiedzony
  Print Using "###";v;  ' Przetwarzamy węzeł (wypisujemy jego numer)

' Rekurencyjnie odwiedzamy nieodwiedzonych sąsiadów

  p = A [v] 
  
  While p
  	 If visited [p->v] = 0 Then DFS (p->v)
  	 p = p->Next
  Wend
  
End Sub

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

Dim As Integer m, i, 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

A = new slistEl Ptr [n] ' Tworzymy tablicę list sąsiedztwa
visited = New Byte [n]  ' Tworzymy tablicę odwiedzin

' Tablicę wypełniamy pustymi listami

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

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m -1
  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 = A [v1]   ' Dodajemy go na początek listy A [v1] 
  A [v1] = p
Next

Close #1

Print

' Przechodzimy graf w głąb

DFS (0)

' Usuwamy tablicę list sąsiedztwa

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

Delete [] A
Delete [] visited

Print

End
Wynik:
6 9
0 5
0 1
5 2
5 1
4 1
4 5
3 4
2 1
2 3

0 1 5 2 3 4

Na początek:  podrozdziału   strony 

Stosowy algorytm DFS

Algorytm stosowy DFS wykorzystuje stos do przechowywania numerów wierzchołków do odwiedzenia.

Algorytm stosowy DFS – wersja poglądowa

Wejście:

v  :  numer wierzchołka startowego, v  ∈ C.
visited  :  wyzerowana tablica logiczna o n elementach.
graf  :  zadany w dowolnie wybrany sposób, algorytm tego nie precyzuje.

Wyjście:

Przetworzenie wszystkich wierzchołków w grafie.
Zmienne pomocnicze:
S  :  pusty stos liczb całkowitych.
u  :  wierzchołek roboczy, u  ∈ C.

Lista kroków:

K01: S.push (v) umieszczamy na stosie numer wierzchołka startowego
K02: visited [v] ← true wierzchołek oznaczamy jako odwiedzony
K03: Dopóki S.empty() = false,
wykonuj
kroki K04...K10
 
K04: v ← S.top() pobieramy ze stosu numer wierzchołka
K05: S.pop() numer usuwamy ze stosu
K06: Przetwórz wierzchołek v  
K07: Dla każdego sąsiada u wierzchołka v,
wykonuj kroki K08...K10
na stos przesyłamy numery nieodwiedzonych jeszcze wierzchołków
K08: Jeśli visited [u] = true,
to następny obieg pętli K07
pomijamy odwiedzonych sąsiadów
K09: S.push (u); sąsiada umieszczamy na stosie
K10: visited [u] ← true oznaczamy go jako odwiedzony
K11: Zakończ  

Poniżej przedstawiamy ten algorytm dla list sąsiedztwa. Postaraj się stworzyć podobne wersje dla macierzy sąsiedztwa i incydencji.

Algorytm stosowy DFS dla list sąsiedztwa

Wejście:

n  :  liczba wierzchołków w grafie, n  ∈ C.
v  :  numer wierzchołka startowego, v  ∈ C.
A  :  n elementowa tablica list sąsiedztwa.
visited  :  wyzerowana tablica logiczna o n elementach.

Wyjście:

Przetworzenie wszystkich wierzchołków w grafie.
Zmienne pomocnicze:
S  :  pusty stos liczb całkowitych.
p  :  wskaźnik elementu listy sąsiedztwa.

Lista kroków:

K01: S.push (v) umieszczamy na stosie numer wierzchołka startowego
K02: visited [v] ← true oznaczamy wierzchołek jako odwiedzony
K03: Dopóki S.empty() = false,
wykonuj
kroki K04...K12
 
K04: v ←S.top() pobieramy ze stosu numer wierzchołka
K05: S.pop() numer usuwamy ze stosu
K06: Przetwórz wierzchołek v zrób coś z odwiedzonym wierzchołkiem
K07: p ← A [v] przeglądamy listę sąsiedztwa wierzchołka v
K08: Dopóki p ≠ nil,
wykonuj kroki K09...K12
 
K09: Jeśli visited [p→v] = true,
to idź do kroku K12
szukamy nieodwiedzonego sąsiada
K10 S.push ( p→v) sąsiada umieszczamy na stosie
K11 visited [p→v] ← true oznaczamy go jako odwiedzonego (już drugi raz nie znajdzie się na stosie)
K12: p ← (p→next) przechodzimy do następnego wierzchołka na liście
K13: Zakończ  

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 odczytuje definicję grafu skierowanego, tworzy dla niego tablicę list sąsiedztwa, a następnie przechodzi ten graf stosowym algorytmem DFS rozpoczynając od wierzchołka o numerze 0. Na wyjście są wyprowadzane numery kolejno odwiedzanych wierzchołków. Tablica list sąsiedztwa i tablica odwiedzin są zadane globalnie, aby uprościć wywołania rekurencyjne. Stos oraz listy sąsiedztwa są tworzone na bazie listy jednokierunkowej.
Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):
obrazek 6 9
0 5
0 1
5 2
5 1
4 1
4 5
3 4
2 1
2 3
Pascal
// Stosowe DFS - listy sąsiedztwa
// Data: 22.07.2013
// (C)2013 mgr Jerzy Wałaszek
//-------------------------------

program sdfs_adjl;

// Typy dla dynamicznej tablicy list sąsiedztwa oraz stosu
type
  PslistEl = ^slistEl;
  slistEl =  record
    next  : PslistEl;
    v     : integer;
  end;

  TList = array of PslistEl;


// Zmienne globalne
var
  A : TList; // Tablica list sąsiedztwa
  visited : array of boolean; // Tablica odwiedzin

// Stosowa procedura przejścia w głąb
//----------------------------------------
procedure DFS (v : integer);
var
  S, p, r : PslistEl;
begin
  new (p);                 // Na stosie umieszczamy wierzchołek startowy
  p^.v := v;
  p^.next := nil;
  S := p;

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

  while S <> nil do
  begin
    v := S^.v;            // Odczytujemy wierzchołek ze stosu
    S := S^.next;         // Wierzchołek usuwamy ze stosu

    write (v:3);         // Przetwarzamy wierzchołek

    p := A [v];          // Przeglądamy jego listę sąsiedztwa
    while p <> nil do
    begin
      if visited [p^.v] = false then
      begin
        new (r);         // Jeśli wierzchołek nie był odwiedzony, 
        r^.v := p^.v;   // to umieszczamy go na stosie
        r^.next := S;
        S := r;
        visited [p^.v] := true; // i oznaczamy jako odwiedzony
      end;
      p := p^.next;     // Następny sąsiad z listy
    end;
  end;
end;

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

var
  n, m, i, v1, v2 : integer;
  p, r : PslistEl;

begin
  read (n, m);             // Czytamy liczbę wierzchołków i krawędzi

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

  // Tablice wypełniamy pustymi listami

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

  // Odczytujemy kolejne definicje krawędzi

  for i := 0 to m - 1 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 := A [v1];   // Dodajemy go na początek listy A [v1] 
    A [v1] := p;
  end;

  writeln;

  // Przechodzimy graf w głąb

  DFS (0);

  // Usuwamy tablicę list sąsiedztwa

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

  SetLength (A, 0);

  SetLength (visited, 0);

  writeln;

end.
C++
// Stosowe DFS - listy sąsiedztwa
// Data: 22.07.2013
// (C)2013 mgr Jerzy Wałaszek
//-------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy dla dynamicznej tablicy list sąsiedztwa oraz stosu

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

// Zmienne globalne

slistEl ** A;            // Macierz sąsiedztwa
bool * visited;          // Tablica odwiedzin

// Stosowa procedura przejścia w głąb
//----------------------------------------
void DFS (int v)
{
  slistEl *S, *p, *r;

  p = new slistEl;        // Na stosie umieszczamy wierzchołek startowy
  p->v = v;
  p->next = NULL;
  S = p;

  visited [v] = true;   // Oznaczamy wierzchołek jako odwiedzony

  while(S)
  {
    v = S->v;             // Odczytujemy wierzchołek ze stosu
    S = S->next;          // Wierzchołek usuwamy ze stosu

    cout << setw (3) << v; // Przetwarzamy wierzchołek

    // Przeglądamy jego listę sąsiedztwa


    for(p = A [v]; p; p = p->next)
    {
      if(!visited [p->v])
      {
        r = new slistEl;  // Jeśli wierzchołek nie był odwiedzony, 
        r->v = p->v;      // to umieszczamy go na stosie
        r->next = S;
        S = r;
        visited [p->v] = true; // i oznaczamy jako odwiedzony
      }
    }
  }
}

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

  A = new slistEl * [n];  // Tworzymy tablicę list sąsiedztwa
  visited = new bool [n]; // Tworzymy tablicę odwiedzin

  // Tablicę wypełniamy pustymi listami

  for(i = 0; i < n; i++)
  {
    A [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 = A [v1]; // Dodajemy go na początek listy A [v1] 
    A [v1] = p;
  }

  cout << endl;

  // Przechodzimy graf w głąb

  DFS (0);

  // Usuwamy tablicę list sąsiedztwa

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

  cout << endl;

  return 0;}
Basic
' Stosowe DFS - listy sąsiedztwa
' Data: 22.07.2013
' (C)2013 mgr Jerzy Wałaszek
'-------------------------------

' Typy dla dynamicznej tablicy list sąsiedztwa oraz stosu

Type slistEl
  next As slistEl Ptr
  v As Integer
End Type

' Zmienne globalne

Dim Shared As slistEl Ptr Ptr A  ' Tablica list sąsiedztwa
Dim Shared As Byte Ptr visited   ' Tablica odwiedzin

' Stosowa procedura przejścia w głąb
'-----------------------------------
Sub DFS (ByVal v As Integer)

  Dim As slistEl Ptr S, p, r

  p = new slistEl        ' Na stosie umieszczamy wierzchołek startowy
  p->v = v
  p->next = 0
  S = p

  visited [v] = 1      ' Oznaczamy wierzchołek jako odwiedzony

  While S
    v = S->v             ' Odczytujemy wierzchołek ze stosu
    S = S->Next          ' Wierzchołek usuwamy ze stosu

    Print Using "###";v; ' Przetwarzamy wierzchołek

    ' Przeglądamy jego listę sąsiedztwa

    p = A [v] 
    While p
      If visited [p->v] = 0 Then
        r = new slistEl  ' Jeśli wierzchołek nie był odwiedzony, 
        r->v = p->v      ' to umieszczamy go na stosie
        r->next = S
        S = r
        visited [p->v] = 1 ' Oznaczamy wierzchołek jako odwiedzony
      End If
      p = p->Next
    Wend
  Wend
End Sub

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

Dim As Integer n, m, i, 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

A = new slistEl Ptr [n] ' Tworzymy tablicę list sąsiedztwa
visited = New Byte [n]  ' Tworzymy tablicę odwiedzin

' Tablicę wypełniamy pustymi listami

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

' Odczytujemy kolejne definicje krawędzi

For i = 0 To m - 1
  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 = A [v1]   ' Dodajemy go na początek listy A [v1] 
  A [v1] = p
Next

Close #1

Print

' Przechodzimy graf w głąb

DFS (0)

' Usuwamy tablicę list sąsiedztwa

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

Delete [] A
Delete [] visited

Print

End
Wynik:
6 9
0 1
0 5
5 2
5 1
4 1
4 5
3 4
2 1
2 3

0 1 5 2 3 4

Zadanie

Zmodyfikuj podane programy, tak aby tworzyły reprezentację grafu nieskierowanego.


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
©2024 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.