Busca em profundidade ou DFS (Depth-First Search)

O comportamento da busca em profundidade está intimamente relacionado com a estrutura de dados pilha (stack ou LIFO)



Busca em profundidade implementada com pilha

buscaProfPilha(grafo G=(V,E), vértice s) {
	
	para v \in V
		marque v como não explorado
	
	seja P uma pilha inicializada com o vértice s
	
	enquanto P != \empty
		remova um vértice v do topo de P
			se v não foi explorado
				marque v como explorado
				para cada aresta (v, w)
					se w não foi explorado
						insira w no topo de P
}

Corretude:

 - o algoritmo encontra todos os vértices alcançáveis a partir de s. Esse resultado segue da corretude do algoritmo de busca genérica, já que a busca em profundidade é um caso particular daquela.

Eficiência:

 - o algoritmo leva tempo O(n) para marcar todos os vértices do grafo como não explorados

 - o restante do algoritmo leva tempo O(n_s + m_s), sendo n_s e m_s o número de vértices e arestas da componente que contém o vértice s.
 
 - Isso porque
 
    - cada aresta do componente do vértice s é visitada no máximo duas vezes (no caso do grafo ser não orientado).
	
	- para perceber isso, observe que o algoritmo só visita as arestas de um vértice após remover este vértice da pilha e ele não estar explorado
	
	   - mas neste caso, o vértice é marcado como explorado antes do algoritmo visitar suas arestas
	
	- portanto, uma aresta qualquer será visitada no máximo uma vez a partir de cada vértice extremo (no caso de um grafo não orientado)
	
	   - ou apenas uma vez a partir de sua cauda (no caso de um grafo dirigido)
	   
	- notamos que, embora vértices explorados não sejam adicionados à pilha
	
	   - existe a possiblidade de um vértice ser colocado mais de uma vez na pilha, antes de ter sido explorado
	   
	   - mas nesse caso, ele será marcado como explorado na primeira vez que for removido da pilha
	   
	   - e nas vezes subsequentes será descartado
	   
	- destacamos que o número total de inserções (e remoções) que podem ocorrer na pilha ao longo de toda a execução do algoritmo é limitada pela soma dos graus de entrada dos vértices
	
	   - já que para um vértice ser colocado mais de uma vez, ele tem que ser destino de diversas arestas
	
	- com isso concluímos que o algoritmo executa um número de passos (e operações da pilha) limitado superiormente pelo número de vértices mais arestas da componente de s, ou seja, O(n_s + m_s)



Busca em profundidade recursiva

suponho fase de inicialização em que todo vértice em V é marcado como não encotrado

 - esta inicialização leva tempo linear no número de vértices, i.e., O(n)
 
 - o algoritmo de busca em profundidade subsequente precisa ter acesso (e poder alterar) quem foi encontrado



buscaProfRec(grafo G=(V,E), vértice v) {
	
	marque v como encontrado
	
	para cada aresta (v, w)
		se w não foi encontrado
			buscaProfRec(grafo G=(V,E), vértice w)
}

Corretude:

 - Encontra todos os vértices alcançáveis, ou seja, para os quais existe caminho a partir de v. Segue da corretude da busca genérica, já que é um caso particular daquela.

Eficiência:

 - Leva tempo O(n_v + m_v), onde n_v e m_v são, respectivamente, o número de vértices e arestas da componente do vértice v da primeira chamada da recursão.
 
    - Resultado segue porque cada vértice da componente será visitado uma vez, antes de ser marcado como encontrado.
	
	- E cada aresta será considerada no máximo duas vezes (no caso de grafos não orientados) ou apenas uma (no caso dos orientados).