I DFS , er de noder, der undersøges, lagret i en stakdatastruktur. Kanterne, der leder os til uudforskede noder, kaldes ' opdagelseskanter ' mens kanterne vil føre allerede besøgte noder kaldes ' blokkanter '. DFS er nyttig i scenarier, hvor en programmør ønsker at finde forbundne komponenter eller cyklusser i en graf.
Følg denne artikels retningslinjer for at implementere DFS i C++.
Implementering af DFS i C++
I det følgende afsnit vil vi gennemgå hvordan DFS er implementeret i C++. Man kan følge de givne trin for at implementere DFS .
- Indsæt rodknudepunktet for et træ eller en graf i stakken.
- Tilføj stakkens øverste element til din besøgte liste.
- Opdag alle de tilstødende noder til den besøgte node, og tilføj de noder, der endnu ikke har besøgt stakken.
- Gentag trin 2 og 3, indtil stakken er tom.
DFS Pseudokode
Det DFS pseudokode er vist nedenfor. I den varme() funktion, udfører vi vores DFS funktion på hver node. Fordi grafen kan have to adskilte dele, kan vi køre DFS algoritme på hver knude for at sikre, at vi har dækket hvert hjørne.
DFS ( g a )
en. besøgt = rigtigt
til hver b ∈ g. Adj [ -en ]
hvis b. besøgt == falsk
DFS ( g,b )
varme ( )
{
For hver a ∈ g
en. besøgt = falsk
For hver a ∈ g
DFS ( g, a )
}
Her repræsenterer g, a og b grafen, henholdsvis første besøgte node og node i stakken.
Implementering af DFS i C++
Et C++ program til DFS implementering er angivet nedenfor:
#include
#inkluder
#inkluder
ved brug af navneområde std ;
skabelon < typenavn t >
klasse DepthFirstSearch
{
privat :
kort < t,liste < t > > adjList ;
offentlig :
DepthFirstSearch ( ) { }
ugyldig Tilføj_kant ( t a, t b, bool du = rigtigt )
{
adjList [ -en ] . skub tilbage ( b ) ;
hvis ( du )
{
adjList [ b ] . skub tilbage ( -en ) ;
}
}
ugyldig Print ( )
{
til ( auto jeg : adjList ) {
cout << jeg. først << '->' ;
til ( t indgang : jeg. anden ) {
cout << indgang << ',' ;
}
cout << endl ;
}
}
ugyldig dfs_helper ( t node,kort < t, bool > & besøgt ) {
besøgt [ node ] = rigtigt ;
cout << node << ' ' << endl ;
til ( t nabo : adjList [ node ] ) {
hvis ( ! besøgt [ nabo ] ) {
dfs_helper ( nabo, besøgte ) ;
}
}
}
ugyldig DFS ( t src )
{
kort < t, bool > besøgt ;
dfs_helper ( src, besøgte ) ;
}
} ;
int vigtigste ( ) {
DepthFirstSearch < int > g ;
g. Tilføj_kant ( 0 , 5 ) ;
g. Tilføj_kant ( 0 , 7 ) ;
g. Tilføj_kant ( 4 , 7 ) ;
g. Tilføj_kant ( 7 , 8 ) ;
g. Tilføj_kant ( 2 , 1 ) ;
g. Tilføj_kant ( 0 , 6 ) ;
g. Tilføj_kant ( 2 , 4 ) ;
g. Tilføj_kant ( 3 , 2 ) ;
g. Tilføj_kant ( 3 , 6 ) ;
g. Tilføj_kant ( 7 , 5 ) ;
g. Tilføj_kant ( 5 , 8 ) ;
g. Print ( ) ;
g. DFS ( 6 ) ;
cout << endl ;
}
I denne kode har vi implementeret DFS algoritme efter pseudokoden angivet ovenfor. Vi har 12 par noder. Vi definerede en klasse ' G ” som repræsenterer en graf med toppunkter a og b, der repræsenterer besøgte og ubesøgte noder.
Produktion
Konklusion
DFS er en populær søgealgoritme, der er nyttig til flere scenarier, såsom at finde cyklusser i en graf og få information om de tilsluttede komponenter eller alle hjørner i en graf. Vi beskrev også arbejdet med DFS metode med et eksempel. DFS anvender stakke til at udføre teknikken og kan også bruges på træer.