W DFS , badane węzły są przechowywane w strukturze danych stosu. Krawędzie, które kierują nas do niezbadanych węzłów, nazywane są „ krawędzie odkrywcze ‘ podczas gdy krawędzie prowadzące do już odwiedzonych węzłów nazywane są ‘ krawędzie bloków '. DFS jest przydatne w scenariuszach, gdy programista chce znaleźć połączone komponenty lub cykle na wykresie.
Postępuj zgodnie ze wskazówkami z tego artykułu, aby wdrożyć DFS w C++.
Implementacja DFS w C++
W następnej sekcji omówimy, jak to zrobić DFS jest zaimplementowany w języku C++. Można wykonać podane kroki, aby wdrożyć DFS .
- Wstaw węzeł główny drzewa lub wykresu do stosu.
- Dodaj najwyższy element stosu do listy odwiedzonych.
- Odkryj wszystkie sąsiednie węzły do odwiedzanego węzła i dodaj te węzły, które jeszcze nie odwiedziły stosu.
- Powtarzaj kroki 2 i 3, aż stos będzie pusty.
Pseudokod DFS
The DFS pseudokod pokazano poniżej. w ciepło() funkcję, wykonujemy nasze DFS funkcję w każdym węźle. Ponieważ wykres może mieć dwie rozłączone części, możemy uruchomić DFS algorytm w każdym węźle, aby upewnić się, że pokryliśmy każdy wierzchołek.
DFS ( g za )
A. odwiedził = PRAWDA
Do każde b ∈ g. przym [ A ]
Jeśli B. odwiedził == FAŁSZ
DFS ( g, b )
ciepło ( )
{
Dla każdego a ∈ g
A. odwiedził = FAŁSZ
Dla każdego a ∈ g
DFS ( g, a )
}
Tutaj g, aib reprezentują odpowiednio wykres, pierwszy odwiedzony węzeł i węzeł w stosie.
Implementacja DFS w C++
Program C++ dla DFS implementacja jest podana poniżej:
#include
#include
#include
za pomocą przestrzeń nazw standardowe ;
szablon < Wpisz imię T >
klasa Wyszukiwanie w głąb
{
prywatny :
mapa < t, lista < T > > lista przym ;
publiczny :
Wyszukiwanie w głąb ( ) { }
próżnia Dodaj_krawędź ( t a, t b, bool Ty = PRAWDA )
{
lista przym [ A ] . push_back ( B ) ;
Jeśli ( Ty )
{
lista przym [ B ] . push_back ( A ) ;
}
}
próżnia Wydrukować ( )
{
Do ( automatyczny I : lista przym ) {
cout << I. Pierwszy << '->' ;
Do ( wejście : I. drugi ) {
cout << wejście << ',' ;
}
cout << koniec ;
}
}
próżnia dfs_pomocnik ( węzeł t, mapa < T, bool > & odwiedził ) {
odwiedził [ węzeł ] = PRAWDA ;
cout << węzeł << ' ' << koniec ;
Do ( sąsiad : lista przym [ węzeł ] ) {
Jeśli ( ! odwiedził [ sąsiad ] ) {
dfs_pomocnik ( sąsiad, odwiedził ) ;
}
}
}
próżnia DFS ( t src )
{
mapa < T, bool > odwiedził ;
dfs_pomocnik ( src, odwiedziłem ) ;
}
} ;
int główny ( ) {
Wyszukiwanie w głąb < int > G ;
G. Dodaj_krawędź ( 0 , 5 ) ;
G. Dodaj_krawędź ( 0 , 7 ) ;
G. Dodaj_krawędź ( 4 , 7 ) ;
G. Dodaj_krawędź ( 7 , 8 ) ;
G. Dodaj_krawędź ( 2 , 1 ) ;
G. Dodaj_krawędź ( 0 , 6 ) ;
G. Dodaj_krawędź ( 2 , 4 ) ;
G. Dodaj_krawędź ( 3 , 2 ) ;
G. Dodaj_krawędź ( 3 , 6 ) ;
G. Dodaj_krawędź ( 7 , 5 ) ;
G. Dodaj_krawędź ( 5 , 8 ) ;
G. Wydrukować ( ) ;
G. DFS ( 6 ) ;
cout << koniec ;
}
W tym kodzie zaimplementowaliśmy DFS algorytm zgodny z pseudokodem podanym powyżej. Mamy 12 par węzłów. Zdefiniowaliśmy klasę „ G ”, który reprezentuje graf mający wierzchołki aib, które reprezentują odwiedzone i nieodwiedzone węzły.
Wyjście
Wniosek
DFS to popularny algorytm wyszukiwania przydatny w kilku scenariuszach, takich jak znajdowanie cykli na grafie i uzyskiwanie informacji o połączonych komponentach lub wszystkich wierzchołkach grafu. Opisaliśmy również działanie tzw DFS metoda z przykładem. DFS wykorzystuje stosy do wykonania techniki i może być również używany na drzewach.