v DFS jsou prozkoumávané uzly uloženy v datové struktuře zásobníku. Hrany, které nás nasměrují do neprozkoumaných uzlů, se nazývají „ objevné hrany „zatímco hrany, které vedou již navštívené uzly, se nazývají“ hrany bloku '. DFS je užitečná ve scénářích, kdy chce programátor najít v grafu spojené součásti nebo cykly.
Při implementaci postupujte podle pokynů v tomto článku DFS v C++.
Implementace DFS v C++
V následující části si projdeme, jak na to DFS je implementován v C++. Při implementaci lze postupovat podle uvedených kroků DFS .
- Vložte kořenový uzel stromu nebo grafu do zásobníku.
- Přidejte nejvyšší položku zásobníku do svého seznamu navštívených stránek.
- Objevte všechny sousední uzly k navštívenému uzlu a přidejte ty uzly, které ještě nenavštívily zásobník.
- Opakujte kroky 2 a 3, dokud nebude zásobník prázdný.
Pseudokód DFS
The DFS pseudokód je uveden níže. V teplo() funkci, provádíme naši DFS funkce na každém uzlu. Protože graf může mít dvě odpojené části, můžeme spustit DFS algoritmus na každém uzlu, abychom zajistili, že jsme pokryli každý vrchol.
DFS ( g a )
A. navštívil = skutečný
pro každé b ∈ g. Adj [ A ]
-li b. navštívil == Nepravdivé
DFS ( g,b )
teplo ( )
{
Pro každé a ∈ g
A. navštívil = Nepravdivé
Pro každé a ∈ g
DFS ( g, a )
}
Zde g, a a b představují graf, první navštívený uzel a uzel v zásobníku.
Implementace DFS v C++
Program v C++ pro DFS implementace je uvedena níže:
#include
#include
#include
použitím jmenný prostor std ;
šablona < typové jméno t >
třída DepthFirstSearch
{
soukromé :
mapa < t,seznam < t > > adjList ;
veřejnost :
DepthFirstSearch ( ) { }
prázdnota Add_edge ( t a, t b, bool vy = skutečný )
{
adjList [ A ] . zatlačit zpátky ( b ) ;
-li ( vy )
{
adjList [ b ] . zatlačit zpátky ( A ) ;
}
}
prázdnota Tisk ( )
{
pro ( auto i : adjList ) {
cout << i. První << '->' ;
pro ( t vstup : i. druhý ) {
cout << vstup << ',' ;
}
cout << endl ;
}
}
prázdnota dfs_helper ( t uzel, mapa < t, bool > & navštívil ) {
navštívil [ uzel ] = skutečný ;
cout << uzel << '' << endl ;
pro ( t soused : adjList [ uzel ] ) {
-li ( ! navštívil [ soused ] ) {
dfs_helper ( soused, navštívil ) ;
}
}
}
prázdnota DFS ( t src )
{
mapa < t, bool > navštívil ;
dfs_helper ( src,navštíveno ) ;
}
} ;
int hlavní ( ) {
DepthFirstSearch < int > G ;
G. Add_edge ( 0 , 5 ) ;
G. Add_edge ( 0 , 7 ) ;
G. Add_edge ( 4 , 7 ) ;
G. Add_edge ( 7 , 8 ) ;
G. Add_edge ( 2 , 1 ) ;
G. Add_edge ( 0 , 6 ) ;
G. Add_edge ( 2 , 4 ) ;
G. Add_edge ( 3 , 2 ) ;
G. Add_edge ( 3 , 6 ) ;
G. Add_edge ( 7 , 5 ) ;
G. Add_edge ( 5 , 8 ) ;
G. Tisk ( ) ;
G. DFS ( 6 ) ;
cout << endl ;
}
V tomto kódu jsme implementovali DFS algoritmus podle výše uvedeného pseudokódu. Máme 12 párů uzlů. Definovali jsme třídu „ G ” což představuje graf s vrcholy aab, které představují navštívené a nenavštívené uzly.
Výstup
Závěr
DFS je oblíbený vyhledávací algoritmus užitečný pro několik scénářů, jako je hledání cyklů v grafu a získávání informací o připojených komponentách nebo všech vrcholech v grafu. Popsali jsme také fungování DFS metoda s příkladem. DFS využívá k provádění této techniky stohy a lze je použít i na stromech.