Busca em grafos é, possivelmente, a operação 

 - mais básica
 
 - importante

 - e genérica

para se fazer em um grafo.



Isso porque ela é fundamental para 

 - obter diversos resultados como a conectividade, que é uma das primeiras propriedades que buscamos saber sobre um grafo

 - e ela pode ser especializada em vários tipos de busca



A busca em grafos genérica encontra todos os vértices que podem ser alcançados a partir de um vértice inicial

buscaGenerica(grafo G=(V,E), vértice s) {
	para v \in V
		marque v como não explorado
	
	marque s como explorado
	
	enquanto existir uma aresta (u, v) tal que u está explorado e v não está explorado
		marque v como explorado
}



Corretude:

 - Ao fim do algoritmo, um vértice v está explorado se, e somente se, existe um caminho em G de s até v.
 
Demonstração:

(-->) Vamos provar a ida por indução.

O caso base vale porque no início o único vértice explorado é o próprio s e é conhecido um caminho trivial de s pra s.

Nossa hipótese de indução é que a afirmação é verdadeira até a iteração anterior ao algoritmo explorar o vértice v.

 - Mais precisamente, supomos que é conhecido um caminho de s até qualquer vértice explorado até o início da iteração em que o algoritmo encontra v, e que estes caminhos só usam vértices explorados. 

Desenvolvemos o passo assim:

 - Na iteração em que o algoritmo explora v, ele o faz através de uma aresta (u, v), sendo que u já estava explorado. 
 
 - Pela hipótese de indução, sabemos que existe um caminho de s até u.
 
 - Concatenando o caminho de s até u com a aresta (u, v), temos um caminho de s até v.
 
 - Note que o caminho de s até u não passa por v porque ele só usa vértices explorados.



(<--) Para provar a volta supomos, por contradição, que existe um caminho de s até v, mas v não está explorado.

Lembramos que neste tipo de prova queremos chegar num absurdo.

Começamos percorrendo o caminho de s até v, mas paramos ao encontrar a primeira aresta que leva de um vértice explorado para um vértice não explorado.
 
 - Note que tal aresta deve existir pois o caminho começa com um vértice explorado (s) e termina com um não explorado (v).

 - Digamos que esta aresta é (u, w), sendo que u pode ser o próprio s e w pode ser o próprio v.
 
De posse da aresta (u, w) consideramos o comportamento do algoritmo e notamos que ele não deveria parar enquanto

 - existisse uma aresta do tipo de (u, w), ou seja, que tem uma ponta explorada e a outra não explorada
 
Portanto, temos um absurdo e concluímos a demonstração.