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

Przechodzenie grafów w głąb – DFS

SPIS TREŚCI
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. iC.

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, jC.

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  1  5  2  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 [ pv  ] = false,
    to DFS ( pv  )
odwiedzamy nieodwiedzonych sąsiadów
K06:     p  ← ( pnext  ) 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 [ pv  ] = true,
        to idź do kroku K12
szukamy nieodwiedzonego sąsiada
K10         S.push ( pv  ) sąsiada umieszczamy na stosie
K11         visited [ pv  ] ← true oznaczamy go jako odwiedzonego ( już drugi raz nie znajdzie się na stosie )
K12:         p  ← ( pnext  ) 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
©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.