Cómo implementar la primera búsqueda de profundidad en C ++

Primera búsqueda de profundidad (DFS) es un poderoso algoritmo recursivo utilizado para buscar todos los nodos de un gráfico o árbol en la estructura de datos. Comienza su búsqueda seleccionando un vértice específico y luego comienza a explorar el gráfico en la medida de lo posible a lo largo de cada rama antes de retroceder. El retroceso ocurre cada vez que el DFS El algoritmo se acerca a un nodo que no tiene vecinos para visitar. Cuando se acerca a un nodo sin vecinos, volverá sobre sus pasos al nodo anterior.

En DFS, 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 los bordes van a liderar los nodos ya visitados se llaman'bordes de bloque'. DFS es útil en escenarios cuando un programador quiere encontrar componentes o ciclos conectados en un gráfico.

Siga las pautas de este artículo para implementar DFS Cª++.

Implementación de DFS en C++

En la siguiente sección, revisaremos cómo DFS se implementa en c++. Uno puede seguir los pasos dados para implementar DFS.

1. Inserte el nodo raíz de un árbol o gráfico en la pila.
2. Agregue el elemento superior de la pila a su lista visitada.
3. Descubra todos los nodos adyacentes al nodo visitado y agregue aquellos nodos que aún no han visitado la pila.
4. Repita los pasos 2 y 3 hasta que la pila esté vacía.

Pseudocódigo DFS

El DFS El seudocódigo se muestra a continuación. En el en eso() función, ejecutamos nuestro DFS función en cada nodo. Debido a que el gráfico puede tener dos partes desconectadas, podemos ejecutar el DFS algoritmo en cada nodo para garantizar que hayamos cubierto cada vértice.

DFS (G A)
a.visitado = verdadero
por cada b ∈ G.Adj [a]
Si b.visitado == falso
DFS (G, B)
en eso()

Por cada a ∈ G
a.visitado = falso
Por cada a ∈ G
DFS (G, A)

Aquí G, A y B representan el gráfico, el nodo y el nodo visitado por primera vez en la pila respectivamente.

Implementación de DFS en C++

Un programa C ++ para DFS La implementación se proporciona a continuación:

#incluir
#incluir
#incluir
usando el espacio de nombres STD;
plantilla
clase de profundidad de clase

privado:
mapa > adjlist;
público:
ProfundidadFirstSearch ()
void add_edge (t a, t b, bool dir = true)

adjlist [a].push_back (b);
if (dir)

adjlist [b].push_back (a);


void prnt ()

para (auto i: adjlist)
cout<";
para (entrada t: yo.segundo)
cout<
cout<

Void dfs_helper (nodo t, mapa &visitado)
visitado [nodo] = true;
cout << node <<" " << endl;
para (t vecino: adjlist [nodo])
si(!visitado [vecino])
dfs_helper (vecino, visitado);



DFS vacío (T SRC)

mapa visitado;
dfs_helper (src, visitado);

;
int main ()
Profundidad de investigación gramo;
gramo.Add_edge (0,5);
gramo.Add_edge (0,7);
gramo.Add_edge (4,7);
gramo.Add_edge (7,8);
gramo.Add_edge (2,1);
gramo.Add_edge (0,6);
gramo.Add_edge (2,4);
gramo.Add_edge (3,2);
gramo.Add_edge (3,6);
gramo.Add_edge (7,5);
gramo.Add_edge (5,8);
gramo.Prnt ();
gramo.Dfs (6);
cout << endl;

En este código, hemos implementado DFS Algoritmo después del código pseudo 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

DFS 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 DFS Método con un ejemplo. DFS emplea pilas para ejecutar la técnica y también se puede usar en árboles.