Menu

Programa C ++ do Depth First Search (DFS) para percorrer um gráfico ou árvore

  • Principal
  • Outro
  • Programa C ++ do Depth First Search (DFS) para percorrer um gráfico ou árvore

depth first search c program traverse graph

Experimente Nosso Instrumento Para Eliminar Problemas

Este tutorial cobre a primeira pesquisa de profundidade (DFS) em C ++ em que um gráfico ou árvore é percorrido em profundidade. Você também aprenderá algoritmo e implementação DFS:

A pesquisa em profundidade (DFS) é outra técnica usada para percorrer uma árvore ou um gráfico.

O DFS começa com um nó raiz ou um nó inicial e, em seguida, explora os nós adjacentes do nó atual indo mais fundo no gráfico ou em uma árvore. Isso significa que no DFS os nós são explorados em profundidade até que um nó sem filhos seja encontrado.

Uma vez que o nó folha é alcançado, o DFS retrocede e começa a explorar mais alguns nós de maneira semelhante.

=> Cuidado com o Guia de treinamento para iniciantes em C ++ aqui.

Pesquisa em profundidade

O que você aprenderá:

Depth First Search (DFS) em C ++

Ao contrário do BFS, no qual exploramos os nós em amplitude, no DFS exploramos os nós em termos de profundidade. No DFS, usamos uma estrutura de dados em pilha para armazenar os nós que estão sendo explorados. As bordas que nos levam a nós inexplorados são chamadas de 'bordas de descoberta', enquanto as bordas que levam aos nós já visitados são chamadas de 'bordas de bloco'.

A seguir, veremos o algoritmo e o pseudocódigo para a técnica DFS.

Algoritmo DFS

  • Passo 1: Insira o nó raiz ou nó inicial de uma árvore ou gráfico na pilha.
  • Passo 2: Retire o item superior da pilha e adicione-o à lista de visitados.
  • Etapa 3: Encontre todos os nós adjacentes do nó marcado como visitado e adicione aqueles que ainda não foram visitados à pilha.
  • Passo 4 : Repita as etapas 2 e 3 até que a pilha esteja vazia.

Pseudo-código

O pseudo-código para DFS é fornecido abaixo.

O pseudo-código para DFS

A partir do pseudocódigo acima, notamos que o algoritmo DFS é chamado recursivamente em cada vértice para garantir que todos os vértices sejam visitados.

Traversals com ilustrações

Vamos agora ilustrar o percurso DFS de um gráfico. Para fins de clareza, usaremos o mesmo gráfico que usamos na ilustração BFS.

Ilustrações DFS com traversals

Seja 0 o nó inicial ou o nó de origem. Primeiro, marcamos como visitado e o adicionamos à lista de visitados. Em seguida, colocamos todos os seus nós adjacentes na pilha.

Empurre todos os nós adjacentes na pilha

Em seguida, pegamos um dos nós adjacentes para processar, ou seja, o topo da pilha que é 1. Marcamos como visitado, adicionando-o à lista de visitados. Agora procure os nós adjacentes de 1. Como 0 já está na lista visitada, nós o ignoramos e visitamos 2 que é o topo da pilha.

Ilustração DFS - Etapa 3

A seguir, marcamos o nó 2 como visitado. Seu nó adjacente 4 é adicionado à pilha.

DFS Ilustração Etapa 4

Em seguida, marcamos 4, que é o topo da pilha conforme visitado. O nó 4 tem apenas o nó 2 como seu adjacente que já foi visitado, portanto, o ignoramos.

DFS Ilustração Etapa 5

Nesse estágio, apenas o nó 3 está presente na pilha. Seu nó adjacente 0 já foi visitado, portanto, o ignoramos. Agora marcamos 3 como visitados.

DFS Ilustração Etapa 6

Agora a pilha está vazia e a lista visitada mostra a sequência da travessia em profundidade do gráfico fornecido.

Se observarmos o gráfico fornecido e a sequência de percurso, notamos que, para o algoritmo DFS, de fato percorremos o gráfico em profundidade e, em seguida, o retrocedemos para explorar novos nós.

Implementação de pesquisa em profundidade

Vamos implementar a técnica de passagem DFS usando C ++.

#include #include using namespace std; //graph class for DFS travesal class DFSGraph { int V; // No. of vertices list *adjList; // adjacency list void DFS_util(int v, bool visited()); // A function used by DFS public: // class Constructor DFSGraph(int V) { this->V = V; adjList = new list(V); } // function to add an edge to graph void addEdge(int v, int w){ adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal function }; void DFSGraph::DFS_util(int v, bool visited()) { // current node v is visited visited(v) = true; cout << v << ' '; // recursively process all the adjacent vertices of the node list::iterator i; for(i = adjList(v).begin(); i != adjList(v).end(); ++i) if(!visited(*i)) DFS_util(*i, visited); } // DFS traversal void DFSGraph::DFS() { // initially none of the vertices are visited bool *visited = new bool(V); for (int i = 0; i < V; i++) visited(i) = false; // explore the vertices one by one by recursively calling DFS_util for (int i = 0; i < V; i++) if (visited(i) == false) DFS_util(i, visited); } int main() { // Create a graph DFSGraph gdfs(5); gdfs.addEdge(0, 1); gdfs.addEdge(0, 2); gdfs.addEdge(0, 3); gdfs.addEdge(1, 2); gdfs.addEdge(2, 4); gdfs.addEdge(3, 3); gdfs.addEdge(4, 4); cout << 'Depth-first traversal for the given graph:'<

Resultado:

Travessia em profundidade para o gráfico fornecido:

0 1 2 4 3

Mais uma vez, usamos o gráfico do programa que usamos para fins ilustrativos. Vemos que o algoritmo DFS (separado em duas funções) é chamado recursivamente em cada vértice do gráfico para garantir que todos os vértices sejam visitados.

Análise de tempo de execução

A complexidade de tempo do DFS é a mesma do BFS, ou seja, O (| V | + | E |) onde V é o número de vértices e E é o número de arestas em um dado gráfico.

Semelhante ao BFS, dependendo se o gráfico é pouco ou densamente povoado, o fator dominante será vértices ou arestas respectivamente no cálculo da complexidade do tempo.

DFS iterativo

A implementação mostrada acima para a técnica DFS é recursiva por natureza e usa uma pilha de chamadas de função. Temos outra variação para a implementação de DFS, ou seja, “ Pesquisa iterativa em profundidade ”. Neste, usamos a pilha explícita para conter os vértices visitados.

Mostramos a implementação para DFS iterativo abaixo. Observe que a implementação é a mesma que BFS, exceto o fator que usamos a estrutura de dados da pilha em vez de uma fila.

#include using namespace std; // graph class class Graph { int V; // No. of vertices list *adjList; // adjacency lists public: Graph(int V) //graph Constructor { this->V = V; adjList = new list(V); } void addEdge(int v, int w) // add an edge to graph { adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal // utility function called by DFS void DFSUtil(int s, vector &visited); }; //traverses all not visited vertices reachable from start node s void Graph::DFSUtil(int s, vector &visited) { // stack for DFS stack dfsstack; // current source node inside stack dfsstack.push(s); while (!dfsstack.empty()) { // Pop a vertex s = dfsstack.top(); dfsstack.pop(); // display the item or node only if its not visited if (!visited(s)) { cout << s << ' '; visited(s) = true; } // explore all adjacent vertices of popped vertex. //Push the vertex to the stack if still not visited for (auto i = adjList(s).begin(); i != adjList(s).end(); ++i) if (!visited(*i)) dfsstack.push(*i); } } // DFS void Graph::DFS() { // initially all vertices are not visited vector visited(V, false); for (int i = 0; i < V; i++) if (!visited(i)) DFSUtil(i, visited); } //main program int main() { Graph gidfs(5); //create graph gidfs.addEdge(0, 1); gidfs.addEdge(0, 2); gidfs.addEdge(0, 3); gidfs.addEdge(1, 2); gidfs.addEdge(2, 4); gidfs.addEdge(3, 3); gidfs.addEdge(4, 4); cout << 'Output of Iterative Depth-first traversal: '; gidfs.DFS(); return 0; }

Resultado:

Saída da travessia Iterativa de profundidade primeiro:

0 3 2 4 1

Usamos o mesmo gráfico que usamos em nossa implementação recursiva. A diferença na saída é porque usamos a pilha na implementação iterativa. Como as pilhas seguem a ordem LIFO, obtemos uma sequência diferente de DFS. Para obter a mesma sequência, podemos inserir os vértices na ordem inversa.

BFS vs DFS

Até agora, discutimos as técnicas de passagem para gráficos, ou seja, BFS e DFS.

Agora vamos examinar as diferenças entre os dois.

BFSDFS
Significa “Pesquisa em amplitude”Significa “Pesquisa em profundidade”
Os nós são explorados de forma ampla, nível por nível.Os nós são explorados em profundidade até que existam apenas nós folha e então retrocedidos para explorar outros nós não visitados.
O BFS é executado com a ajuda da estrutura de dados da fila.O DFS é executado com a ajuda da estrutura de dados da pilha.
Mais lento no desempenho.Mais rápido que o BFS.
Útil para encontrar o caminho mais curto entre dois nós.Usado principalmente para detectar ciclos em gráficos.

Aplicações de DFS

  • Detectando ciclos no gráfico: Se encontrarmos uma borda posterior ao executar o DFS em um gráfico, podemos concluir que o gráfico tem um ciclo. Portanto, o DFS é usado para detectar os ciclos em um gráfico.
  • Encontrando o caminho: Dados dois vértices x e y, podemos encontrar o caminho entre x e y usando DFS. Começamos com o vértice x e depois empurramos todos os vértices no caminho para a pilha até encontrar y. O conteúdo da pilha fornece o caminho entre x e y.
  • Árvore de abrangência mínima e caminho mais curto: A passagem DFS do gráfico não ponderado nos dá uma árvore de abrangência mínima e o caminho mais curto entre os nós.
  • Classificação Topológica: Usamos classificação topológica quando precisamos agendar as tarefas das dependências fornecidas entre as tarefas. No campo da ciência da computação, nós o usamos principalmente para resolver dependências de símbolos em linkers, serialização de dados, agendamento de instruções, etc. DFS é amplamente usado em classificação topológica.

Conclusão

Nos últimos dois tutoriais, exploramos mais sobre as duas técnicas de passagem para gráficos, ou seja, BFS e DFS. Vimos as diferenças, bem como as aplicações de ambas as técnicas. BFS e DFS alcançam basicamente o mesmo resultado ao visitar todos os nós de um gráfico, mas eles diferem na ordem de saída e na maneira como isso é feito.

Também vimos a implementação de ambas as técnicas. Enquanto o BFS usa uma fila, o DFS faz uso de pilhas para implementar a técnica. Com isso, concluímos o tutorial sobre técnicas de travessia para gráficos. Também podemos usar BFS e DFS em árvores.

como visualizar um arquivo .dat

Aprenderemos mais sobre spanning trees e alguns algoritmos para encontrar o caminho mais curto entre os nós de um gráfico em nosso próximo tutorial.

=> Veja aqui para explorar a lista completa de tutoriais C ++.

Leitura recomendada

^