algorytm.org

Przeszukiwanie grafu wszerz (BFS) i w głąb (DFS)



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Przeszukiwanie grafu wszerz (BFS) i w głąb (DFS)
Ocena użytkowników:***** / 145
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 09 sierpnia 2005 21:40

Procedury przeglądania grafu w głąb (DFS) i wszerz (BFS) są bardzo często wykorzystywane w innych, bardziej złożonych algorytmach (np. badania spójności).
W strategii DFS wybrany wierzchołek należy umieścić na stosie, zaznaczyć jako odwiedzony a następnie przejść do jego następnika. Następnik również umieszczamy na stosie, zaznaczamy jako odwiedzony przechodzimy do jego następnika. Jak widać procedurę można wywoływać rekurencyjnie. Jeśli dojdziemy do takiego wierzchołka, że nie ma on krawędzi incydentych z nieodwiedzonymi wierzchołkami, należy usunąć go ze stosu i pobrać ze stosu kolejny wierzchołek do przeszukania. W praktyce stosuje się zasadę, że jeśli przeszukiwany wierzchołek jest połączony krawędziami z wieloma wierzchołkami, wybiera się do przeszukania wierzchołek o najmniejszej liczbie porządkowej. Dlatego szukając kolejny nieodwiedzony następnik należy rozpoczynać od końca macierzy. Przeszukiwanie DFS wykorzystuje się do badania spójności grafu. Jeśli procedura wywołana dla pierwszego wierzchołka "dotrze" do wszystkich wierzchołków grafu to graf jest spójny.
Aby przeszukać graf wszerz (BFS) należy zamiast stosu wykorzystać kolejkę do przechowywania wierzchołków a kolejnych nieodwiedzonych następników szukać od początku macierzy.
Oto przykładowy graf:
graf
Przykład:

:

Przeszukiwanie w głąb (DFS):
Zaczynamy od wierzchołka 1, odwiedzamy go i wrzucamy na stos wszystkie jego następniki, w kolejności od tego z największym indeksem:
Odwiedzone: 1; Stos: 3, 2;
Bierzemy wierzchołek ze stosu, odwiedzamy go i znów wrzucamy wszystkie jego nieodwiedzone jeszcze następniki na stos:
Odwiedzone: 1, 2; Stos: 3, 5, 4;
Bierzemy wierzchołek ze stosu, odwiedzamy go, jedynym następnikiem 4 jest 1, ale ten wierzchołek już odwiedzaliśmy więc nie wrzucamy nic na stos:
Odwiedzone: 1, 2, 4; Stos: 3, 5;
Bierzemy wierzchołek ze stosu, odwiedzamy go, jedynym następnikiem 5 jest 4, ale ten wierzchołek już odwiedzaliśmy więc nie wrzucamy nic na stos:
Odwiedzone: 1, 2, 4, 5; Stos: 3;
Bierzemy wierzchołek ze stosu, odwiedzamy go, jedynym następnikiem 3 jest 6, ten wierzchołek jeszcze nie jest odwiedzony więc wrzucamy go na stos:
Odwiedzone: 1, 2, 4, 5, 3; Stos: 6;
Bierzemy wierzchołek ze stosu, odwiedzamy go, wierzchołek 6 nie ma następników, więc nie ma czego wrzucić na stos:
Odwiedzone: 1, 2, 4, 5, 3, 6; Stos: ;
Stos jest pusty zatem zakończyliśmy przeszukiwanie grafu w głąb.

Przeszukiwanie w szerz (BFS):
Zaczynamy od wierzchołka 1, odwiedzamy go i wrzucamy do kolejki wszystkie jego następniki, w kolejności od tego z najmniejszym indeksem:
Odwiedzone: 1; Kolejka: 2, 3;
Bierzemy wierzchołek z kolejki, odwiedzamy go i znów wrzucamy wszystkie jego nieodwiedzone jeszcze następniki do kolejki:
Odwiedzone: 1, 2; Kolejka: 3, 4, 5;
Bierzemy wierzchołek z kolejki, odwiedzamy go, jedynym następnikiem 3 jest 6 więc wrzucamy go do kolejki:
Odwiedzone: 1, 2, 3; Kolejka: 4, 5, 6;
Bierzemy wierzchołek z kolejki, odwiedzamy go, jedynym następnikiem 4 jest 1, ale ten wierzchołek już odwiedzaliśmy więc nie wrzucamy go do kolejki:
Odwiedzone: 1, 2, 3, 4; Kolejka: 5, 6;
Bierzemy wierzchołek z kolejki, odwiedzamy go, jedynym następnikiem 5 jest 4, ale ten wierzchołek już odwiedzaliśmy więc nie wrzucamy go do kolejki:
Odwiedzone: 1, 2, 3, 4, 5; Kolejka: 6;
Bierzemy wierzchołek z kolejki, odwiedzamy go, wierzchołek 6 nie ma następników, więc nie ma czego wrzucić do kolejki:
Odwiedzone: 1, 2, 3, 4, 5, 6; Kolejka: ;
Kolejka jest pusta zatem zakończyliśmy przeszukiwanie grafu w szerz.


Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Mateusz ZaborowskiC#DFS
.cs
.cs
***** / 8
Michał KnasieckiC/C++
.cpp
.cpp
***** / 35
Dawid DrozdC/C++C++
.cpp
.cpp
***** / 14
mephistoJavaDFS, BFS oraz ścieżki w grafach nieskierowanych i skierowanych
.java
.java
***** / 7
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 09 sierpnia 2012 15:16
Komentarze
photo
-4 # Paweł 2010-01-17 23:16
wielkie dzięki
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-17 # Adam 2010-01-26 02:04
Wreszcie konkret, ale przydałby się jakiś przykład kodu.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-12 # culio 2010-05-08 02:31
Jakby ktoś mógł taki kod do pythona 3.x
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-21 # Adiki 2011-06-06 22:51
DFS Drozda jest niepoprawny. Jak kładziesz na stos to nie kolorujesz jako odwiedzony, kolorujesz jak ściągasz ze stosu i ściągnięty jest biały i możesz kilka razy ten sam element na stos położyć. Inaczej masz jakieś pseudo wszerz przeszukiwanie.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+3 # Adam2 2012-06-04 18:42
Nie prawda, w DFS już przy sprawdzaniu sąsiadów/następników danego wierzchołka oznaczamy go jako odwiedzony właśnie dlatego, że nie można tego samego wierzchołka na stos odłożyć kilka razy. Pomyliło Ci się chyba z algorytmem poszukiwania cyklu Eulera, który jest modyfikacją algorytmu DFS, gdzie jako odwiedzone oznaczamy krawędzie/łuki, a nie wierzchołki. Tam faktycznie wierzchołek może być na stos odłożony więcej niż raz. Nie sprawdzałem jednak poprawności DFS Drozda, więc nie gwarantuje że jest on poprawny, ale Twoja uwaga jest błędna.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-14 # matti2515 2013-02-03 04:11
Na stos możesz kilka razy ten sam element położyć adiki ma rację inaczej ten sposób implementacji nie miał by sensu bo miałbyś fałszywe wyniki.
A wierzchołki koloruje się jak się ściąga je ze stosu. Po to jest w końcu tablica odwiedzonych wierzchołków żeby powtarzać danych wyjściowych po kilka razy.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-16 # ksz 2013-02-16 17:02
dokładnie! na stos można włożyć tą samą po raz kolejny, a tą wcześniejszą usunąć, w przeciwnym razie alg. jest błedny.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # luk 2013-09-13 11:59
jak chcecie kilka razy wkladac na stos to samo? Wtedy kilka razy trzeba bedzie z niego zdjac i kilka razy wyjdzie ta sama liczba...
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz