In DFS werden die untersuchten Knoten in einer Stapeldatenstruktur gespeichert. Die Kanten, die uns zu unerforschten Knoten führen, heißen „ Entdeckungskanten ' während die Kanten, die zu bereits besuchten Knoten führen, als ' Kanten blockieren '. DFS ist in Szenarien nützlich, in denen ein Programmierer verbundene Komponenten oder Zyklen in einem Diagramm finden möchte.
Befolgen Sie die Richtlinien dieses Artikels zur Implementierung DFS in C++.
Implementierung von DFS in C++
Im folgenden Abschnitt gehen wir darauf ein, wie DFS ist in C++ implementiert. Man kann den angegebenen Schritten zur Implementierung folgen DFS .
- Fügen Sie den Wurzelknoten eines Baums oder Diagramms in den Stapel ein.
- Fügen Sie das oberste Element des Stapels zu Ihrer besuchten Liste hinzu.
- Entdecken Sie alle benachbarten Knoten zum besuchten Knoten und fügen Sie diejenigen Knoten hinzu, die den Stack noch nicht besucht haben.
- Wiederholen Sie die Schritte 2 und 3, bis der Stapel leer ist.
DFS-Pseudocode
Der DFS Pseudocode ist unten gezeigt. Im Hitze() Funktion führen wir unsere aus DFS Funktion auf jedem Knoten. Da der Graph zwei getrennte Teile haben kann, können wir die ausführen DFS Algorithmus auf jedem Knoten, um sicherzustellen, dass wir jeden Scheitelpunkt abgedeckt haben.
DFS ( g ein )
A. hat besucht = WAHR
für jedes b ∈ g. Adj [ A ]
Wenn B. hat besucht == FALSCH
DFS ( g, b )
Hitze ( )
{
Für jedes a ∈ g
A. hat besucht = FALSCH
Für jedes a ∈ g
DFS ( g, a )
}
Hier repräsentieren g, a und b den Graphen, den zuerst besuchten Knoten bzw. den Knoten im Stapel.
Implementieren von DFS in C++
Ein C++-Programm für DFS Umsetzung ist unten angegeben:
#include
#include
#include
verwenden Namensraum Standard ;
Vorlage < Modellname T >
Klasse DepthFirstSearch
{
Privatgelände :
Karte < t, Liste < T > > Anpassungsliste ;
öffentlich :
DepthFirstSearch ( ) { }
Leere Kante hinzufügen ( ta, tb, bool Du = WAHR )
{
Anpassungsliste [ A ] . push_back ( B ) ;
Wenn ( Du )
{
Anpassungsliste [ B ] . push_back ( A ) ;
}
}
Leere Drucken ( )
{
für ( Auto ich : Anpassungsliste ) {
cout << ich. Erste << '->' ;
für ( t-Eintrag : ich. zweite ) {
cout << Eintrag << ',' ;
}
cout << Ende ;
}
}
Leere dfs_helper ( t-Knoten, Karte < T, bool > & hat besucht ) {
hat besucht [ Knoten ] = WAHR ;
cout << Knoten << ' ' << Ende ;
für ( t Nachbar : Anpassungsliste [ Knoten ] ) {
Wenn ( ! hat besucht [ Nachbar ] ) {
dfs_helper ( Nachbar, besucht ) ;
}
}
}
Leere DFS ( t Quelle )
{
Karte < T, bool > hat besucht ;
dfs_helper ( src, besucht ) ;
}
} ;
int hauptsächlich ( ) {
DepthFirstSearch < int > G ;
G. Kante hinzufügen ( 0 , 5 ) ;
G. Kante hinzufügen ( 0 , 7 ) ;
G. Kante hinzufügen ( 4 , 7 ) ;
G. Kante hinzufügen ( 7 , 8 ) ;
G. Kante hinzufügen ( 2 , 1 ) ;
G. Kante hinzufügen ( 0 , 6 ) ;
G. Kante hinzufügen ( 2 , 4 ) ;
G. Kante hinzufügen ( 3 , 2 ) ;
G. Kante hinzufügen ( 3 , 6 ) ;
G. Kante hinzufügen ( 7 , 5 ) ;
G. Kante hinzufügen ( 5 , 8 ) ;
G. Drucken ( ) ;
G. DFS ( 6 ) ;
cout << Ende ;
}
In diesem Code haben wir implementiert DFS Algorithmus, der dem oben angegebenen Pseudocode folgt. Wir haben 12 Knotenpaare. Wir haben eine Klasse definiert “ G “, der einen Graphen mit Knoten a und b darstellt, die besuchte und nicht besuchte Knoten darstellen.
Ausgang
Abschluss
DFS ist ein beliebter Suchalgorithmus, der für verschiedene Szenarien nützlich ist, z. B. um die Zyklen in einem Diagramm zu finden und Informationen über die verbundenen Komponenten oder alle Scheitelpunkte in einem Diagramm zu erhalten. Wir haben auch die Funktionsweise der beschrieben DFS Methode an einem Beispiel. DFS verwendet Stapel, um die Technik auszuführen, und kann auch auf Bäumen verwendet werden.