Algorytmy i Struktury Danych - Przechodzenie grafów w głąb

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.
vs : 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.

Elementy pomocnicze:

u : wierzchołek roboczy, u ∈ C.

Lista kroków:

K01: vs[v] ← true ; oznacz wierzchołek jako odwiedzony
K02: Przetwórz wierzchołek v ; przetwarzanie wstępne
K03: Dla każdego sąsiada u wierzchołka v, ; odwiedź algorytmem DFS każdego
     wykonuj: jeśli vs[u] = false, to dfs(u) ; 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.
vs : 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.

Elementy pomocnicze:

i : indeks. i ∈ C.

Lista kroków:

K01: vs[v] ← true ; odwiedź wierzchołek
K02: Przetwórz wierzchołek v ; przetwarzanie wstępne
K03: Dla i = 0, 1, …, n-1, wykonuj: ; odwiedź algorytmem DFS każdego
     Jeśli (A[v][i] = 1)  (vs[i] = false), ; nieodwiedzonego sąsiada
     to dfs(i)
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):

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
  // Wiersz
  nptr = array of byte;
  // Cała macierz
  mptr = array of nptr;

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

// Rekurencyjna procedura
// przejścia w głąb
//-----------------------
procedure dfs(v : integer);
var
  i : integer;
begin
  // Oznaczamy węzeł jako odwiedzony
  vs[v] := true;
  // Przetwarzamy węzeł
  // (wypisujemy jego numer)
  write(v:3);
  // Rekurencyjnie odwiedzamy
  // nieodwiedzonych sąsiadów
  for i := 0 to n-1 do
    if (A[v][i] = 1) and
       (vs [i] = false) then dfs(i);
end;

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

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

begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablicę wskaźników
  SetLength(A, n);
  // Tworzymy tablicę odwiedzin
  SetLength(vs, n);
  for i := 0 to n-1 do
    // Tworzymy wiersze
    SetLength(A[i], n);
  // Macierz wypełniamy zerami
  for i := 0 to n-1 do
  begin
    // Zerujemy tablicę odwiedzin
    vs[i] := false;
    for j := 0 to n-1 do
      A[i][j] := 0;
  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 obecna
    A[v1][v2] := 1;
  end;
  writeln;
  // Przechodzimy graf w głąb
  // od wierzchołka nr 0
  dfs(0);
  // Usuwamy macierz
  for i := 0 to n-1 do
    SetLength(A[i], 0);
  SetLength(A, 0);
  SetLength(vs, 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 * vs; // Tablica odwiedzin

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

  // Oznaczamy węzeł jako odwiedzony
  vs [v] = true;
   // Przetwarzamy węzeł
   // (wypisujemy jego numer)
   cout << setw(3) << v;
  // Rekurencyjnie odwiedzamy
  // nieodwiedzonych sąsiadów
  for(i = 0; i < n; i++)
    if((A[v][i] == 1) &&
       !vs [i]) dfs(i);
}

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

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

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

  // Tworzymy tablicę wskaźników
  A = new char * [n];
  // Tworzymy tablicę odwiedzin
  vs = new bool [n];
  for(i = 0; i < n; i++)
    // Tworzymy wiersze
    A[i] = new char [n];
  // Macierz wypełniamy zerami
  for(i = 0; i < n; i++)
  {
    // Zerujemy tablicę odwiedzin
    vs[i] = false;
    for(j = 0; j < n; j++)
      A[i][j] = 0;
  }
  // 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 obecna
    A[v1][v2] = 1;
  }
  cout << endl;
  // Przechodzimy graf w głąb
  dfs(0);
  // Usuwamy macierz
  for(i = 0; i < n; i++)
    delete [] A[i];
  delete [] A;
  delete [] vs;
  cout << endl;
  return 0;
}

Basic

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

' Zmienne globalne

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

' Rekurencyjna procedura przejścia w głąb
'----------------------------------------
Sub dfs(ByVal v As Integer)
  Dim As Integer i
  ' Oznaczamy węzeł jako odwiedzony
  vs[v] = 1
  ' Przetwarzamy węzeł
  ' (wypisujemy jego numer)
  Print Using "###";v;
  ' Rekurencyjnie odwiedzamy
  ' nieodwiedzonych sąsiadów
  For i = 0 To n-1
    If (A[v][i] = 1) AndAlso _
       (vs[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
' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę wskaźników
A = New Byte Ptr [n]
' Tworzymy tablicę odwiedzin
vs = New Byte [n]
For i = 0 To n-1
  ' Tworzymy wiersze
  A[i] = New Byte [n]
Next
' Macierz wypełniamy zerami
For i = 0 To n-1
  ' Zerujemy tablicę odwiedzin
  vs[i] = 0
  For j = 0 To n-1
    A[i][j] = 0
  Next
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 obecna
  A[v1][v2] = 1
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 [] vs
Print
End

Python (dodatek)

# Rekurencyjne DFS-macierz sąsiedztwa
# Data: 27.11.2024
# (C)2024 mgr Jerzy Wałaszek
#--------------------------------------

# Rekurencyjna procedura przejścia w głąb
#----------------------------------------
def dfs(a,vt,v):
    # Oznaczamy węzeł jako odwiedzony
    vt[v] = 1
    # Przetwarzamy węzeł
    # (wypisujemy jego numer)
    print("%3d" % v, end="")
    # Rekurencyjnie odwiedzamy
    # nieodwiedzonych sąsiadów
    for i in range(n):
        if a[v][i] and not vt[i]:
            dfs(a,vt,i)

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

# Czytamy liczbę wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę wskaźników
a = []
# Tworzymy tablicę odwiedzin
vs = [0] * n
for i in range(n):
    a.append([0] * 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 obecna
    a[v1][v2] = 1
print()
# Przechodzimy graf w głąb
dfs(a,vs,0)
# Usuwamy macierz
for i in range(n):
    a[i] = None
del a,vs
print()

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.
vs : 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.

Elementy pomocnicze:

i, j : indeksy. i, j ∈ C.

Lista kroków:

K01: vs[v] ← true ; odwiedź wierzchołek
K02: Przetwórz wierzchołek v ; przetwarzanie wstępne
K03: Dla i = 0, 1, …, m-1: ; przeszukujemy kolejne krawędzie
     wykonuj kroki K04…K08
K04:   Jeśli A[v][i] ≠ 1, ; szukamy krawędzi, dla której v jest wierzchołkiem startowym
       to następny obieg pętli K03
K05:   Dla j = 0, 1, …, n-1:
       wykonuj kroki K06…K08
K06:     Jeśli A[j][i] ≠ -1, ; szukamy wierzchołka końcowego
         to następny obieg pętli K05
K07:     Jeśli vs[j] = false, ; rekurencyjnie odwiedzamy znalezionego sąsiada
         to dfs(j)
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):

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
  // Liczba wierzchołków i krawędzi
  n, m : integer;
  // Macierz incydencji
  A : mptr;
  // Tablica odwiedzin
  vs : array of boolean;

// Rekurencyjna procedura przejścia w głąb
//----------------------------------------
procedure dfs(v : integer);
var
  i, j : integer;

begin
  // Oznaczamy węzeł jako odwiedzony
  vs[v] := true;
  // Przetwarzamy węzeł
  // (wypisujemy jego numer)
  write(v:3);
  // 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 vs[j] = false then dfs(j);
          break;
        end;
end;

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

var
  i, j, v1, v2 : integer;

begin
  // Czytamy liczbę wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablicę wskaźników
  SetLength(A, n);
  // Tworzymy tablicę odwiedzin
  SetLength(vs, n);
  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
    // Zerujemy tablicę odwiedzin
    vs[i] := false;
    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
    // Wierzchołek startowy i końcowy krawędzi
    read(v1, v2);
    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(vs, 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 * vs;  // Tablica odwiedzin

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

  // Zaznaczamy węzeł jako odwiedzony
  vs[v] = true;
  // Przetwarzamy węzeł (wypisujemy jego numer)
  cout << setw(3) << v;
  // 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(!vs[j]) dfs(j);
          break;
        }
}

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

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

  // Czytamy liczbę wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę wskaźników
  A = new signed char * [n];
  // Tworzymy tablicę odwiedzin
  vs = new bool [n];
  for(i = 0; i < n; i++)
    // Tworzymy wiersze
    A[i] = new signed char [m];
  // Macierz wypełniamy zerami
  for(i = 0; i < n; i++)
  {
    // Zerujemy tablicę odwiedzin
    vs[i] = false;
    for(j = 0; j < m; j++) A[i][j] = 0;
  }
  // Odczytujemy kolejne definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołek startowy i końcowy krawędzi
    cin >> v1 >> v2;
    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 [] vs;
  cout << endl;
  return 0;
}

Basic

' Rekurencyjne DFS-macierz incydencji
' Data: 22.07.2013
' (C)2013 mgr Jerzy Wałaszek
'--------------------------------------

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

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

  ' Zaznaczamy węzeł jako odwiedzony
  vs[v] = 1
  ' Przetwarzamy węzeł
  ' (wypisujemy jego numer)
  Print Using "###";v;
  ' 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 vs[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
' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę wskaźników
A = New Byte Ptr [n]
' Tworzymy tablicę odwiedzin
vs = New Byte [n]
For i = 0 To n-1
  A[i] = New Byte [m] ' Tworzymy wiersze
Next
' Macierz wypełniamy zerami
For i = 0 To n-1
  ' Zerujemy tablicę odwiedzin
  vs[i] = 0
  For j = 0 To m-1
    A[i][j] = 0
  Next
Next
' Odczytujemy kolejne definicje krawędzi
For i = 0 To m-1
  ' Wierzchołek startowy i końcowy krawędzi
  Input #1, v1, v2
  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 [] vs
Print
End

Python (dodatek)

# Rekurencyjne DFS-macierz incydencji
# Data: 27.11.2024
# (C)2024 mgr Jerzy Wałaszek
#--------------------------------------

# Rekurencyjna procedura przejścia w głąb
#----------------------------------------
def dfs(a,vt,v):
    # Oznaczamy węzeł jako odwiedzony
    vt[v] = True
    # Przetwarzamy węzeł
    # (wypisujemy jego numer)
    print("%3d" % v, end="")
    # Rekurencyjnie odwiedzamy
    # nieodwiedzonych sąsiadów
    for i in range(m):
        if a[v][i] == 1:
            for j in range(n):
                if a[j][i] == -1:
                    if not vt[j]: dfs(a,vt,j)
                    break

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

# Czytamy liczbę wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę wskaźników
a = []
# Tworzymy tablicę odwiedzin
vs = [False] * n
for i in range(n):
    a.append([0] * m)
# 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])
    a[v1][i] =  1 # Wierzchołek startowy
    a[v2][i] = -1 # Wierzchołek końcowy
print()
# Przechodzimy graf w głąb
dfs(a,vs,0)
# Usuwamy macierz
for i in range(n):
    a[i] = None
del a, vs
print()

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.
vs : 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.

Elementy pomocnicze:

p : wskaźnik elementu listy sąsiedztwa.

Lista kroków:

K01: vs[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 vs[p→v] = false, ; odwiedzamy nieodwiedzonych sąsiadów
       to dfs(p→v)
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 przetwarzanego wierzchołka grafu.

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

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
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;
  TList = array of PSLel;

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

// Rekurencyjna procedura przejścia w głąb
//----------------------------------------
procedure dfs(v : integer);
var
  p : PSLel;

begin
  // Zaznaczamy węzeł jako odwiedzony
  vs[v] := true;
  // Przetwarzamy węzeł
  // (wypisujemy jego numer)
  write(v:3);
  // Rekurencyjnie odwiedzamy
  // nieodwiedzonych sąsiadów
  p := A[v];
  while p <> nil do
  begin
    if vs[p^.v] = false then
      dfs(p^.v);
    p := p^.next;
  end;
end;

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

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

begin
  // Czytamy liczbę wierzchołków
  // i krawędzi
  read(n, m);
  // Tworzymy tablicę
  // list sąsiedztwa
  SetLength(A, n);
  // Tworzymy tablicę odwiedzin
  SetLength(vs, n);
  // Tablice wypełniamy
  // pustymi listami
  for i := 0 to n-1 do
  begin
    A[i] := nil;
    vs[i] := false;
  end;
  // Odczytujemy kolejne
  // definicje krawędzi
  for i := 0 to m-1 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 := 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(vs, 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 SLel
{
  SLel * next;
  int v;
};

// Zmienne globalne

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

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

  // Zaznaczamy węzeł jako odwiedzony
  vs[v] = true;
  // Przetwarzamy węzeł
  // (wypisujemy jego numer)
  cout << setw(3) << v;
  // Rekurencyjnie odwiedzamy
  // nieodwiedzonych sąsiadów
  for(p = A[v]; p; p = p->next)
    if(!vs[p->v]) dfs(p->v);
}

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

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

  // Czytamy liczbę wierzchołków
  // i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę list sąsiedztwa
  A = new SLel * [n];
  // Tworzymy tablicę odwiedzin
  vs = new bool [n];
  // Tablicę wypełniamy pustymi listami
  for(i = 0; i < n; i++)
  {
    A[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 A[v1]
    p->next = 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 [] vs;
  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 SLel
  next As SLel Ptr
  v As Integer
End Type

' Zmienne globalne

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

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

  ' Oznaczamy węzeł jako odwiedzony
  vs[v] = 1
  ' Przetwarzamy węzeł
  ' (wypisujemy jego numer)
  Print Using "###";v;
  ' Rekurencyjnie odwiedzamy
  ' nieodwiedzonych sąsiadów
  p = A[v]
  While p
    If vs[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 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
A = new SLel Ptr [n]
' Tworzymy tablicę odwiedzin
vs = New Byte [n]
' Tablicę wypełniamy pustymi listami
For i = 0 To n-1
  A[i] = 0
  vs[i] = 0
Next
' Odczytujemy kolejne definicje krawędzi
For i = 0 To m -1
  ' 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 A[v1]
  p->next = 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 <> 0
    r = p
    p = p->Next
    Delete r
  Wend
Next
Delete [] A
Delete [] vs
Print
End

Python (dodatek)

# Rekurencyjne DFS-listy sąsiedztwa
# Data: 28.11.2024
# (C)2024 mgr Jerzy Wałaszek
#----------------------------------

# Klasa dla dynamicznej tablicy list sąsiedztwa
class SLel:
    def __init(self):
        self.next =None
        self.v = 0


# Rekurencyjna procedura przejścia w głąb
#----------------------------------------
def dfs(a,vt,x):
    # Oznaczamy węzeł jako odwiedzony
    vt[x] = True
    # Przetwarzamy węzeł
    # (wypisujemy jego numer)
    print("%3d" % x, end="")
    # Rekurencyjnie odwiedzamy
    # nieodwiedzonych sąsiadów
    p = a[x]
    while p:
        if not vt[p.v]: dfs(a,vt,p.v)
        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
a = [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 a[v1]
    p.next = a[v1]
    a[v1] = p
print()
# Przechodzimy graf w głąb
dfs(a,vs,0)
# Usuwamy tablicę list sąsiedztwa
for i in range(n):
    while a[i]:
        a[i] = a[i].next
del a, vs
print()

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

do podrozdziału do strony

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.
vs : 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.

Elementy 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: vs[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, ; na stos przesyłamy numery
       wykonuj kroki K08…K10 ; nieodwiedzonych jeszcze wierzchołków
K08:     Jeśli vs[u] = true, ; pomijamy odwiedzonych sąsiadów
         to następny obieg pętli K07
K09:     S.push(u) ; sąsiada umieszczamy na stosie
K10:     vs[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.
vs : wyzerowana tablica logiczna o n elementach.

Wyjście:

Przetworzenie wszystkich wierzchołków w grafie.

Elementy 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: vs[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 vs[p→v] = true, ; szukamy nieodwiedzonego sąsiada
         to idź do kroku K12
K10      S.push(p→v) ; sąsiada umieszczamy na stosie
K11      vs[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 o tej samej strukturze.

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

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
  PSLel = ^SLel;
  SLel =  record
    next  : PSLel;
    v     : integer;
  end;

  TList = array of PSLel;

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

// Stosowa procedura przejścia w głąb
//-----------------------------------
procedure dfs(v : integer);
var
  S, p, r : PSLel;

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

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

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

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

  // Tworzymy tablicę list sąsiedztwa
  SetLength(A, n);
  // Tworzymy tablicę odwiedzin
  SetLength(vs, n);
  // Tablice wypełniamy pustymi listami
  for i := 0 to n-1 do
  begin
    A[i] := nil;
    vs[i] := false;
  end;
  // Odczytujemy kolejne definicje krawędzi
  for i := 0 to m-1 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 := 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(vs, 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 SLel
{
  SLel * next;
  int v;
};

// Zmienne globalne
SLel ** A; // Macierz sąsiedztwa
bool * vs; // Tablica odwiedzin

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

  // Na stosie umieszczamy wierzchołek startowy
  p = new SLel;
  p->v = v;
  p->next = NULL;
  S = p;
  // Oznaczamy wierzchołek jako odwiedzony
  vs[v] = true;
  while(S)
  {
    // Odczytujemy wierzchołek ze stosu
    v = S->v;
    // Wierzchołek usuwamy ze stosu
    r = S;
    S = S->next;
    delete r;
    // Przetwarzamy wierzchołek
    cout << setw(3) << v;
    // Przeglądamy jego listę sąsiedztwa
    for(p = A[v]; p; p = p->next)
    {
      if(!vs[p->v])
      {
        // Jeśli wierzchołek nie był odwiedzony,
        r = new SLel;
        // to umieszczamy go na stosie
        r->v = p->v;
        r->next = S;
        S = r;
        // i oznaczamy jako odwiedzony
        vs[p->v] = true;
      }
    }
  }
}

// **********************
// *** 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
  A = new SLel * [n];
  // Tworzymy tablicę odwiedzin
  vs = new bool [n];
  // Tablicę wypełniamy pustymi listami
  for(i = 0; i < n; i++)
  {
    A[i] = NULL;
    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 A[v1]
    p->next = 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 [] vs;
  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 SLel
  next As SLel Ptr
  v As Integer
End Type

' Zmienne globalne

' Tablica list sąsiedztwa
Dim Shared As SLel Ptr Ptr A
' Tablica odwiedzin
Dim Shared As Byte Ptr vs

' Stosowa procedura przejścia w głąb
'-----------------------------------
Sub dfs(ByVal v As Integer)
  Dim As SLel Ptr S, p, r

  ' Na stosie umieszczamy
  ' wierzchołek startowy
  p = new SLel
  p->v = v
  p->next = 0
  S = p
  ' Oznaczamy wierzchołek jako odwiedzony
  vs[v] = 1
  While S
    ' Odczytujemy wierzchołek ze stosu
    v = S->v
    ' Wierzchołek usuwamy ze stosu
    r = S
    S = S->Next
    Delete r
    ' Przetwarzamy wierzchołek
    Print Using "###";v;
    ' Przeglądamy jego listę sąsiedztwa
    p = A[v]
    While p <> 0
      If vs[p->v] = 0 Then
        ' Jeśli wierzchołek
        ' nie był odwiedzony,
        r = new SLel
        ' to umieszczamy go na stosie
        r->v = p->v
        r->next = S
        S = r
        ' Oznaczamy wierzchołek
        ' jako odwiedzony
        vs[p->v] = 1
      End If
      p = p->Next
    Wend
  Wend
End Sub

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

Dim As Integer n, m, i, 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
A = new SLel Ptr [n]
' Tworzymy tablicę odwiedzin
vs = New Byte [n]
' Tablicę wypełniamy pustymi listami
For i = 0 To n-1
  A[i] = 0
  vs[i] = 0
Next
' Odczytujemy kolejne definicje krawędzi
For i = 0 To m-1
  ' 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 A[v1]
  p->next = 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 [] vs
Print
End

Python (dodatek)

# Stosowe DFS-listy sąsiedztwa
# Data: 2.12.2024
# (C)2024 mgr Jerzy Wałaszek
#-------------------------------

# Klasa elementów list
class SLel:
    def __init__(self,v):
        self.next = None
        self.v = v


# Stosowa procedura przejścia w głąb
#-----------------------------------
def dfs(a,vt,s,v):
    # Na stosie umieszczamy
    # wierzchołek startowy
    p = SLel(v)
    s = p
    # Oznaczamy wierzchołek jako odwiedzony
    vt[v] = True
    while s:
        # Odczytujemy wierzchołek ze stosu
        v = s.v
        # Wierzchołek usuwamy ze stosu
        r = s
        s = s.next
        del r
        # Przetwarzamy wierzchołek
        print("%3d" % v, end="")
        # Przeglądamy jego listę sąsiedztwa
        p = a[v]
        while p:
            if not vt[p.v]:
                # Jeśli wierzchołek
                # nie był odwiedzony,
                r = SLel(p.v)
                # to umieszczamy go na stosie
                r.next = s
                s = r
                # Oznaczamy wierzchołek
                # jako odwiedzony
                vt[p.v] = True
            p = p.next

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

# Stos
s = []
# Czytamy liczbę wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę list sąsiedztwa
a = [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(v2)
    # Dodajemy go na początek listy A[v1]
    p.next = a[v1]
    a[v1] = p
# Przechodzimy graf w głąb
dfs(a,vs,s,0)
# Usuwamy tablicę list sąsiedztwa
for i in range(n):
  while a[i]:
    a[i] = a[i].next
del a, vs
print()

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 przechodziły w głąb przez graf nieskierowany.

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.

	Przejście rozpoczynamy od wierzchołka v₀.
	Wierzchołek v₀ oznaczamy jako odwiedzony (kolor zielony) i przechodzimy do jego sąsiada v₁.
	Wierzchołek v₁ oznaczamy jako odwiedzony. Ponieważ nie ma on sąsiadów, to ta gałąź przejścia jest ślepa i już dalej nie biegnie.
	Przechodzimy do kolejnego sąsiada wierzchołka v₀, czyli do v₅.
	Wierzchołek v₅ oznaczamy jako odwiedzony. Wierzchołek ten posiada dwóch sąsiadów: v₁ i v₂. Do v₁ nie będziemy przechodzić, ponieważ jest on oznaczony jako już odwiedzony.
	Przechodzimy do v₂.
	Wierzchołek v₂ oznaczamy jako odwiedzony. Posiada on dwóch sąsiadów: v₁ (już odwiedzony) oraz v₃.
	Przechodzimy do v₃.
	Zaznaczamy v₃ jako odwiedzony. Wierzchołek v₃ posiada tylko jednego sąsiada: v₄.
	Przechodzimy do v₄.
	Zaznaczamy v₄ jako odwiedzony. Wierzchołek v₄ posiada dwóch sąsiadów, v₁ i v₅, 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: v₀ v₁ v₅ v₂ v₃ v₄

Przechodzenie grafów w głąb – DFS

Problem

Algorytm DFS

Rekurencyjny algorytm DFS

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Algorytm rekurencyjny DFS dla macierzy incydencji: dfs(v)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Stosowy algorytm DFS

Algorytm stosowy DFS – wersja poglądowa

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm stosowy DFS dla list sąsiedztwa

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Zadanie