I DFS , lagras noderna som utforskas i en stackdatastruktur. Kanterna som leder oss till outforskade noder kallas ' upptäcktskanter 'medan kanterna som leder till redan besökta noder kallas' blockkanter '. DFS är användbart i scenarier när en programmerare vill hitta anslutna komponenter eller cykler i en graf.
Följ den här artikelns riktlinjer för att implementera DFS i C++.
Implementering av DFS i C++
I följande avsnitt går vi igenom hur DFS är implementerat i C++. Man kan följa de givna stegen för att implementera DFS .
- Infoga rotnoden för ett träd eller en graf i stacken.
- Lägg till stackens översta objekt till din besökta lista.
- Upptäck alla intilliggande noder till den besökta noden och lägg till de noder som ännu inte har besökt stacken.
- Upprepa steg 2 och 3 tills bunten är tom.
DFS Pseudokod
De DFS pseudokod visas nedan. I den värme() funktion, vi utför vår DFS funktion på varje nod. Eftersom grafen kan ha två frånkopplade delar kan vi köra DFS algoritm på varje nod för att säkerställa att vi har täckt varje vertex.
DFS ( g a )
a. besökt = Sann
för varje b ∈ g. Adj [ a ]
om b. besökt == falsk
DFS ( g,b )
värme ( )
{
För varje a ∈ g
a. besökt = falsk
För varje a ∈ g
DFS ( g, a )
}
Här representerar g, a och b grafen, först besökta nod respektive nod i stacken.
Implementering av DFS i C++
Ett C++-program för DFS implementering ges nedan:
#inkludera
#inkludera
#inkludera
använder sig av namnutrymme std ;
mall < typnamn t >
klass DepthFirstSearch
{
privat :
Karta < t,lista < t > > adjList ;
offentlig :
DepthFirstSearch ( ) { }
tomhet Add_edge ( t a, t b, bool du = Sann )
{
adjList [ a ] . trycka tillbaka ( b ) ;
om ( du )
{
adjList [ b ] . trycka tillbaka ( a ) ;
}
}
tomhet Skriva ut ( )
{
för ( bil i : adjList ) {
cout << i. först << '->' ;
för ( t inträde : i. andra ) {
cout << inträde << ',' ;
}
cout << endl ;
}
}
tomhet dfs_helper ( t nod,karta < t, bool > & besökt ) {
besökt [ nod ] = Sann ;
cout << nod << ' ' << endl ;
för ( t granne : adjList [ nod ] ) {
om ( ! besökt [ granne ] ) {
dfs_helper ( granne, besökte ) ;
}
}
}
tomhet DFS ( t src )
{
Karta < t, bool > besökt ;
dfs_helper ( src, besökte ) ;
}
} ;
int huvud ( ) {
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. Skriva ut ( ) ;
g. DFS ( 6 ) ;
cout << endl ;
}
I den här koden har vi implementerat DFS algoritm efter pseudokoden som anges ovan. Vi har 12 par noder. Vi definierade en klass ' G ” som representerar en graf med hörn a och b som representerar besökta och obesökta noder.
Produktion
Slutsats
DFS är en populär sökalgoritm som är användbar för flera scenarier, som att hitta cyklerna i en graf och få information om de anslutna komponenterna eller alla hörn i en graf. Vi beskrev också hur det fungerar DFS metod med ett exempel. DFS använder stackar för att utföra tekniken och kan även användas på träd.