Depth first Search ou Depth first traversal é um algoritmo recursivo para pesquisar todos os vértices de uma estrutura de dados de grafos ou árvores. Atravessar significa visitar todos os nós de um grafo.

> Profundidade Primeiro Algoritmo de Busca

Um padrão de implementação de DFS coloca cada vértice do gráfico em uma das duas categorias:

1. Visitado
2. Não Visitou

O objetivo do algoritmo é a marca de cada vértice como visitado evitando ciclos.,

O algoritmo DFS funciona da seguinte forma:

1. comece por colocar qualquer um dos vértices do grafo em cima de uma pilha.
2. pegue no item superior da pilha e adicione-o à lista visitada.
3. crie uma lista dos nós adjacentes desse vértice. Adicione os que não estão na lista visitada ao topo da pilha.
4. continue repetindo os passos 2 e 3 até que a pilha esteja vazia.

exemplo de pesquisa em profundidade

vamos ver como o algoritmo de busca em profundidade funciona com um exemplo. Usamos um grafo não direcionado com 5 vértices.,

Vamos começar a partir do vértice 0, o algoritmo DFS começa colocando-a no para visitar a lista e colocar todos os seus vértices adjacentes na pilha.

em seguida, vamos visitar o elemento no topo da pilha i.e. 1 e vá para os seus nós adjacentes. Uma vez que 0 já foi visitado, nós visitamos 2.,

Vertex 2 tem uma unvisited adjacentes do vértice 4, de modo que temos a acrescentar que, para o topo da pilha e visitá-lo.

Depois de visitarmos o último elemento 3, ele não tem quaisquer nós adjacentes não visitados, então nós completamos a profundidade primeiro transversal do grafo.,

DFS Pseudocode (implementação recursiva)

o pseudocode para DFS é mostrado abaixo. Na função init (), observe que executamos a função DFS em cada nó. Isto é porque o grafo pode ter duas partes diferentes desconectadas de modo a garantir que nós cobrimos cada vértice, nós também podemos executar o algoritmo DFS em cada nó.,

DFS(G, u) u.visited = true for each v ∈ G.Adj if v.visited == false DFS(G,v) init() { For each u ∈ G u.visited = false For each u ∈ G DFS(G, u)}

DFS Implementation in Python, Java and C/C++

the code for the Depth First Search Algorithm with an example is shown below. O código foi simplificado para que possamos nos concentrar no algoritmo ao invés de outros detalhes.

a Complexidade da Profundidade de Busca

A complexidade de tempo do algoritmo DFS é representado na forma de O(V + E), onde V é o número de nós e E é o número de arestas.

a complexidade espacial do algoritmo é O(V).,

a Aplicação do Algoritmo DFS

1. Para encontrar o caminho
2. Para testar se o grafo é bipartido
3. Para encontrar o fortemente ligado componentes de um gráfico
4. Para a detecção de ciclos em um grafo