Przechodzenie grafów w głąb – DFS


Tematy pokrewne   Podrozdziały
Grafy
Podstawowe pojęcia dotyczące grafów
Reprezentacja grafów w komputerze
Przechodzenie grafów w głąb – DFS
Przechodzenie grafów wszerz – BFS
Transpozycja grafu
Kwadrat grafu
Graf krawędziowy
Stopień grafu
Znajdowanie ścieżki w grafie
Znajdowanie drogi w labiryncie
Spójność grafu
Znajdowanie spójnych składowych w grafie
Znajdowanie silnie spójnych składowych w grafie
Drzewa rozpinające grafu
Znajdowanie mostów w grafie
Znajdowanie punktów artykulacji w grafie
Grafy dwudzielne
Kojarzenie małżeństw
Cykliczność grafu
Znajdowanie cykli w grafie
Istnienie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Eulera
Znajdowanie cyklu lub ścieżki Hamiltona
Sortowanie topologiczne grafu skierowanego
Najkrótsza ścieżka w grafie ważonym – algorytm Dijkstry
Najkrótsza ścieżka w grafie ważonym – algorytm Bellmana-Forda
Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków w grafie ważonym
Problem chińskiego listonosza
Problem komiwojażera
Minimalne drzewo rozpinające
Kolorowanie grafu
Znajdowanie klik w grafie
 

Algorytm DFS
Rekurencyjny algorytm DFS
Stosowy algorytm DFS

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:

 

  Przejście rozpoczynamy od wierzchołka v0.
  Wierzchołek v0 oznaczamy jako odwiedzony (kolor zielony) i przechodzimy do jego sąsiada v1
  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.
  Przechodzimy do kolejnego sąsiada wierzchołka v0, czyli do v5.
  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.
  Przechodzimy do v2.
  Wierzchołek v2 oznaczamy jako odwiedzony. Posiada on dwóch sąsiadów: v1 (już odwiedzony) oraz v3.
  Przechodzimy do v3.
  Zaznaczamy v3 jako odwiedzony. Wierzchołek v3 posiada tylko jednego sąsiada: v4
  Przechodzimy do v4.
  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

 

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.
Elementy 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 wykonaj:
    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 x n
Wyjście:
Przetworzenie wszystkich wierzchołków w grafie.
Elementy 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: wykonaj:
    Jeśli (A[v][i] = 1) (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  

 

Program

Ważne:

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.

 

Przykładowe dane

       6 9
0 5
0 1
5 2
5 1
4 1
4 5
3 4
2 1
2 3

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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 x m
Wyjście:
Przetworzenie wszystkich wierzchołków w grafie.
Elementy 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 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 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.

 

Program

Ważne:

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.

 

Przykładowe dane
       6 9
0 5
0 1
5 2
5 1
4 1
4 5
3 4
2 1
2 3

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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.
Elementy 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: pA[v] ; rozpoczynamy od początku listy
K04 Dopóki pnil: wykonuj 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.

 

Program

Ważne:

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.

 

Przykładowe dane
       6 9
0 5
0 1
5 2
5 1
4 1
4 5
3 4
2 1
2 3

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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

 

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.
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: visited[v] ← true ; wierzchołek oznaczamy jako odwiedzony
K03: Dopóki S.empty() = false, wykonuj 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 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.
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: visited[v] ← true ; oznaczamy wierzchołek jako odwiedzony
K03: Dopóki S.empty() = false, wykonuj K04...K12  
K04:     vS.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:     pA[v] ; przeglądamy listę sąsiedztwa wierzchołka v
K08:     Dopóki pnil, wykonuj K09...K12  
K09:         Jeśli visited[pv] = true, to idź do 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  

Program

Ważne:

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.

 

Przykładowe dane
       6 9
0 1
0 5
5 2
5 1
4 1
4 5
3 4
2 1
2 3

 

Lazarus
// 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.
Code::Blocks
// 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;
}
Free 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.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.