Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
ProblemDokonać przejścia grafu w głąb. |
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:
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 |
Algorytm DFS występuje w dwóch postaciach: rekurencyjnej i stosowej. Implementacja algorytmu zależy od wybranej reprezentacji grafu.
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. |
u | : | wierzchołek roboczy, w ∈ C. |
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 |
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. |
i | : | indeks. i ∈ C. |
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) (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 |
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):
|
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. |
// 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 |
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. |
i, j | : | indeksy. i, j ∈ C. |
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.
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):
|
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. |
// Rekurencyjne DFS - macierz incydencji // Data: 22.07.2013 // (C)2013 mgr Jerzy Wałaszek //-------------------------------------- #include <iostream> #include <iomanip> using namespace std; // Zmienne globalne int n, m; // Liczba wierzchołków signed char ** A; // Macierz incydencji bool * visited; // Tablica odwiedzin // Rekurencyjna procedura przejścia w głąb //---------------------------------------- void DFS (int v) { int i, j; visited [v] = true; // Zaznaczamy węzeł jako odwiedzony cout << setw (3) << v; // Przetwarzamy węzeł (wypisujemy jego numer) // Rekurencyjnie odwiedzamy nieodwiedzonych sąsiadów for(i = 0; i < m; i++) if(A [v][i] == 1) for(j = 0; j < n; j++) if(A [j][i] == -1) { if(!visited [j]) DFS (j); break; } } // ********************** // *** PROGRAM GŁÓWNY *** // ********************** int main() { int i, j, v1, v2; cin >> n >> m; // Czytamy liczbę wierzchołków i krawędzi A = new signed char * [n]; // Tworzymy tablicę wskaźników visited = new bool [n]; // Tworzymy tablicę odwiedzin for(i = 0; i < n; i++) A [i] = new signed char [m]; // Tworzymy wiersze // Macierz wypełniamy zerami for(i = 0; i < n; i++) { visited [i] = false; // Zerujemy tablicę odwiedzin for(j = 0; j < m; j++) A [i][j] = 0; } // Odczytujemy kolejne definicje krawędzi for(i = 0; i < m; i++) { cin >> v1 >> v2; // Wierzchołek startowy i końcowy krawędzi A [v1][i] = 1; // Wierzchołek startowy A [v2][i] = -1; // Wierzchołek końcowy } cout << endl; // Przechodzimy graf w głąb DFS (0); // Usuwamy macierz for(i = 0; i < n; i++) delete A [i]; delete [] A; delete [] visited; cout << endl; return 0;} |
Basic' Rekurencyjne DFS - macierz incydencji ' Data: 22.07.2013 ' (C)2013 mgr Jerzy Wałaszek '-------------------------------------- ' Zmienne globalne Dim Shared As Integer n, m ' Liczba wierzchołków Dim Shared As Byte Ptr Ptr A ' Macierz incydencji Dim Shared As Byte Ptr visited ' Tablica odwiedzin ' Rekurencyjna procedura przejścia w głąb '---------------------------------------- Sub DFS (ByVal v As Integer) Dim As Integer i, j visited [v] = 1 ' Zaznaczamy węzeł jako odwiedzony Print Using "###";v; ' Przetwarzamy węzeł (wypisujemy jego numer) ' Rekurencyjnie odwiedzamy nieodwiedzonych sąsiadów For i = 0 To m - 1 If A [v][i] = 1 Then For j = 0 To n - 1 If A [j][i] = -1 Then If visited [j] = 0 Then DFS (j) Exit For End If Next End If Next End Sub ' ********************** ' *** PROGRAM GŁÓWNY *** ' ********************** Dim As Integer i, j, v1, v2 Open Cons For Input As #1 Input #1, n, m ' Czytamy liczbę wierzchołków i krawędzi A = New Byte Ptr [n] ' Tworzymy tablicę wskaźników visited = New Byte [n] ' Tworzymy tablicę odwiedzin For i = 0 To n - 1 A [i] = New Byte [m] ' Tworzymy wiersze Next ' Macierz wypełniamy zerami For i = 0 To n - 1 visited [i] = 0 ' Zerujemy tablicę odwiedzin For j = 0 To m - 1 A [i][j] = 0 Next Next ' Odczytujemy kolejne definicje krawędzi For i = 0 To m - 1 Input #1, v1, v2 ' Wierzchołek startowy i końcowy krawędzi A [v1][i] = 1 ' Wierzchołek startowy A [v2][i] =-1 ' Wierzchołek końcowy Next Close #1 Print ' Przechodzimy graf w głąb DFS (0) ' Usuwamy macierz For i = 0 To n - 1 Delete A [i] Next Delete [] A Delete [] visited Print End |
Wynik: |
6 9 0 5 0 1 5 2 5 1 4 1 4 5 3 4 2 1 2 3 0 5 2 1 3 4 |
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. |
p | : | wskaźnik elementu listy sąsiedztwa. |
K01: | visited [v] ← true | odwiedź wierzchołek |
K02: | Przetwórz wierzchołek v | przetwarzanie wstępne |
K03: | p ← A [v] | rozpoczynamy od początku listy |
K04 | Dopóki p ≠ nil: wykonuj kroki K05…K06 |
|
K05: | Jeśli
visited [p→v] = false, to DFS (p→v) |
odwiedzamy nieodwiedzonych sąsiadów |
K06: | p ← (p→next) | idziemy do kolejnego sąsiada |
K07: | Przetwórz wierzchołek v | przetwarzanie końcowe |
K08: | Zakończ |
Reprezentacja grafu tablicą list sąsiedztwa jest korzystna dla algorytmu DFS, ponieważ pętla wyszukująca sąsiadów nie wykonuje pustych przebiegów – każdy element listy sąsiedztwa jest sąsiadem.
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):
|
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. |
// 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 |
Algorytm stosowy DFS wykorzystuje stos do przechowywania numerów wierzchołków do odwiedzenia.
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. |
S | : | pusty stos liczb całkowitych. |
u | : | wierzchołek roboczy, u ∈ C. |
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.
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. |
S | : | pusty stos liczb całkowitych. |
p | : | wskaźnik elementu listy sąsiedztwa. |
K01: | S.push (v) | umieszczamy na stosie numer wierzchołka startowego |
K02: | visited [v] ← true | oznaczamy wierzchołek jako odwiedzony |
K03: | Dopóki S.empty() = false, wykonuj kroki K04…K12 |
|
K04: | v ←S.top() | pobieramy ze stosu numer wierzchołka |
K05: | S.pop() | numer usuwamy ze stosu |
K06: | Przetwórz wierzchołek v | zrób coś z odwiedzonym wierzchołkiem |
K07: | p ← A [v] | przeglądamy listę sąsiedztwa wierzchołka v |
K08: | Dopóki p
≠
nil, wykonuj kroki K09…K12 |
|
K09: |
Jeśli visited [p→v] = true, to idź do kroku K12 |
szukamy nieodwiedzonego sąsiada |
K10 | S.push ( p→v) | sąsiada umieszczamy na stosie |
K11 | visited [p→v] ← true | oznaczamy go jako odwiedzonego (już drugi raz nie znajdzie się na stosie) |
K12: | p ← (p→next) | przechodzimy do następnego wierzchołka na liście |
K13: | Zakończ |
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):
|
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. |
// 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 |
Zmodyfikuj podane programy, tak aby tworzyły reprezentację grafu nieskierowanego.
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.