En SFD , los nodos que se exploran se almacenan en una estructura de datos de pila. Los bordes que nos dirigen a nodos inexplorados se llaman ' bordes de descubrimiento ' mientras que los bordes que van a conducir a los nodos ya visitados se llaman ' bordes de bloque ‘. SFD es útil en escenarios en los que un programador quiere encontrar componentes o ciclos conectados en un gráfico.
Siga las pautas de este artículo para implementar SFD en C++.
Implementación de DFS en C++
En la siguiente sección, veremos cómo SFD está implementado en C++. Uno puede seguir los pasos dados para implementar SFD .
- Inserte el nodo raíz de un árbol o gráfico en la pila.
- Agregue el elemento superior de la pila a su lista visitada.
- Descubra todos los nodos adyacentes al nodo visitado y agregue aquellos nodos que aún no han visitado la pila.
- Repita los pasos 2 y 3 hasta que la pila esté vacía.
Pseudocódigo DFS
El SFD El pseudocódigo se muestra a continuación. En el calor() función, ejecutamos nuestra SFD función en cada nodo. Debido a que el gráfico puede tener dos partes desconectadas, podemos ejecutar el SFD algoritmo en cada nodo para asegurar que hemos cubierto todos los vértices.
SFD ( g un )
a. visitado = verdadero
para cada b ∈ g. adj. [ a ]
si b. visitado == FALSO
SFD ( g,b )
calor ( )
{
Para cada a ∈ g
a. visitado = FALSO
Para cada a ∈ g
SFD ( g, un )
}
Aquí g, a y b representan el gráfico, el primer nodo visitado y el nodo en la pila, respectivamente.
Implementando DFS en C++
Un programa en C++ para SFD la implementación se da a continuación:
#incluir
#include
#include
usando espacio de nombres estándar ;
plantilla < escribe un nombre t >
clase ProfundidadPrimeraBúsqueda
{
privado :
mapa < lista < t > > adjLista ;
público :
ProfundidadPrimeraBúsqueda ( ) { }
vacío Añadir_borde ( ta, tb, bool tú = verdadero )
{
adjLista [ a ] . hacer retroceder ( b ) ;
si ( tú )
{
adjLista [ b ] . hacer retroceder ( a ) ;
}
}
vacío Imprimir ( )
{
para ( auto i : adjLista ) {
cout << i. primero << '->' ;
para ( entrada t : i. segundo ) {
cout << entrada << ',' ;
}
cout << final ;
}
}
vacío dfs_helper ( nodo t,mapa < yo, bool > & visitado ) {
visitado [ nodo ] = verdadero ;
cout << nodo << ' ' << final ;
para ( t vecino : adjLista [ nodo ] ) {
si ( ! visitado [ vecino ] ) {
dfs_helper ( vecino, visitado ) ;
}
}
}
vacío SFD ( t origen )
{
mapa < yo, bool > visitado ;
dfs_helper ( origen, visitado ) ;
}
} ;
En t principal ( ) {
ProfundidadPrimeraBúsqueda < En t > gramo ;
gramo. Añadir_borde ( 0 , 5 ) ;
gramo. Añadir_borde ( 0 , 7 ) ;
gramo. Añadir_borde ( 4 , 7 ) ;
gramo. Añadir_borde ( 7 , 8 ) ;
gramo. Añadir_borde ( 2 , 1 ) ;
gramo. Añadir_borde ( 0 , 6 ) ;
gramo. Añadir_borde ( 2 , 4 ) ;
gramo. Añadir_borde ( 3 , 2 ) ;
gramo. Añadir_borde ( 3 , 6 ) ;
gramo. Añadir_borde ( 7 , 5 ) ;
gramo. Añadir_borde ( 5 , 8 ) ;
gramo. Imprimir ( ) ;
gramo. SFD ( 6 ) ;
cout << final ;
}
En este código, hemos implementado SFD algoritmo siguiendo el pseudocódigo dado anteriormente. Tenemos 12 pares de nodos. Definimos una clase “ GRAMO ” que representa un gráfico que tiene vértices a y b que representan nodos visitados y no visitados.
Producción
Conclusión
SFD es un algoritmo de búsqueda popular útil para varios escenarios, como encontrar los ciclos en un gráfico y obtener información sobre los componentes conectados o todos los vértices en un gráfico. También describimos el funcionamiento del SFD método con un ejemplo. SFD emplea pilas para ejecutar la técnica y también se puede usar en árboles.