Em DFS , os nós que estão sendo explorados são armazenados em uma estrutura de dados de pilha. As arestas que nos direcionam para nós inexplorados são chamadas de ‘ arestas de descoberta ‘enquanto as arestas que levam aos nós já visitados são chamadas de ‘ arestas do bloco '. DFS é útil em cenários quando um programador deseja encontrar componentes ou ciclos conectados em um gráfico.
Siga as diretrizes deste artigo para implementar DFS em C++.
Implementação de DFS em C++
Na seção a seguir, veremos como DFS é implementado em C++. Pode-se seguir as etapas fornecidas para implementar DFS .
- Insira o nó raiz de uma árvore ou gráfico na pilha.
- Adicione o item do topo da pilha à sua lista de visitas.
- Descubra todos os nós adjacentes ao nó visitado e adicione os nós que ainda não visitaram a pilha.
- Repita as etapas 2 e 3 até que a pilha esteja vazia.
Pseudocódigo DFS
O DFS pseudocódigo é mostrado abaixo. No aquecer() função, executamos nosso DFS função em cada nó. Como o gráfico pode ter duas partes desconectadas, podemos executar o DFS algoritmo em cada nó para garantir que cobrimos todos os vértices.
DFS ( g a )
a. visitado = verdadeiro
para cada b ∈ g. Adj [ a ]
se b. visitado == falso
DFS ( g,b )
aquecer ( )
{
Para cada a ∈ g
a. visitado = falso
Para cada a ∈ g
DFS ( g, um )
}
Aqui g, aeb representam o grafo, primeiro nó visitado e nó na pilha, respectivamente.
Implementando DFS em C++
Um programa C++ para DFS implementação segue abaixo:
#include
#include
#include
usando namespace std ;
modelo < Digite o nome t >
aula DepthFirstSearch
{
privado :
mapa < t,lista < t > > adjList ;
público :
DepthFirstSearch ( ) { }
vazio Add_edge ( t a, t b, bool você = verdadeiro )
{
adjList [ a ] . retrocesso ( b ) ;
se ( você )
{
adjList [ b ] . retrocesso ( a ) ;
}
}
vazio Imprimir ( )
{
para ( auto eu : adjList ) {
cout << eu. primeiro << '->' ;
para ( t entrada : eu. segundo ) {
cout << entrada << ',' ;
}
cout << fim ;
}
}
vazio dfs_helper ( nó t, mapa < t, bool > & visitado ) {
visitado [ nó ] = verdadeiro ;
cout << nó << ' ' << fim ;
para ( t vizinho : adjList [ nó ] ) {
se ( ! visitado [ vizinho ] ) {
dfs_helper ( vizinho, visitou ) ;
}
}
}
vazio DFS ( t src )
{
mapa < t, bool > visitado ;
dfs_helper ( src, visitou ) ;
}
} ;
int principal ( ) {
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. Imprimir ( ) ;
g. DFS ( 6 ) ;
cout << fim ;
}
Neste código, implementamos DFS algoritmo seguindo o pseudocódigo fornecido acima. Temos 12 pares de nós. Definimos uma classe “ G ” que representa um grafo com vértices a e b que representam nós visitados e não visitados.
Saída
Conclusão
DFS é um algoritmo de busca popular útil para vários cenários, como encontrar os ciclos em um grafo e obter informações sobre os componentes conectados ou todos os vértices em um grafo. Descrevemos também o funcionamento do DFS método com um exemplo. DFS emprega pilhas para executar a técnica e também pode ser usado em árvores.