Existem dois tipos de busca em grafo que são muito eficientes e cumprem funções bastante diferentes, embora ambas sejam especializações da busca genérica.

 - Uma delas é a busca em largura, ou BFS (Breadth-First Search)
 
 - A outra é a busca em profundidade, ou DFS (Depth-First Search)

Hoje vamos nos aprofundar na BFS.

Esta busca explora o grafo em camadas a partir do vértice inicial s

 - Por isso ela é útil para calcular a distância não ponderada entre vértices

E seu comportamento está intimamente relacionado com a estrutura de dados fila (queue ou FIFO)



buscaLargura(grafo G=(V,E), vértice s) {
	
	para v \in V
		marque v como não encontrado
	
	marque s como encontrado
	
	seja Q uma fila inicializada com o vértice s
	
	enquanto Q != \empty
		remova um vértice v do início de Q
		para cada aresta (v, w)
			se w não foi encontrado
				marque w como encontrado
				insira w no final de Q



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 largura é um caso particular daquela.

 - além disso, o algoritmo de busca em largura explora o grafo em camadas centradas em s, mas isso vamos mostrar quando usarmos esse algoritmo para calcular distâncias. 
 
Eficiência:

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

 - 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
	
	- em cada iteração do laço principal, um vértice é removido da fila. Logo, ele é executado O(n_s) vezes.
	
	- como cada vértice é colocado apenas uma vez na fila, pois não colocamos vértices já encontrados
	
	   - cada aresta é visitada no máximo duas vezes, uma para cada vértice extremo.
	   
	   - Portanto, o algoritmo executa O(m_s) iterações do laço mais interno.



distancias(grafo G=(V,E), vértice s) {
	
	para v \in V
		marque v como não encontrado
		dist[v] = +\inf
	
	marque s como encontrado
	dist[s] = 0
	
	seja Q uma fila inicializada com o vértice s
	
	enquanto Q != \empty
		remova um vértice v do início de Q
		para cada aresta (v, w)
			se w não foi encontrado
				marque w como encontrado
				insira w no final de Q
				dist[w] = dist[v] + 1

Vamos mostrar que um vértice qualquer v tem dist[v] = k se e somente se ele está na camada k, ou seja, o caminho mais curto de s até v tem comprimento k.

 - A prova segue por indução no número de camadas, ou seja, queremos mostrar que para todo vértice v da camada k temos dist[v] = k.

 - Caso base: temos apenas o vértice s na camada 0 e dist[s] = 0.

 - H.I.: para todo vértice v de uma camada k' < k temos dist[v] = k'.

 - Passo: considere a iteração em que o algoritmo encontra um vértice w e atribui dist[w] = k para ele. Certamente o último vértice que o algoritmo removeu da fila foi um vértice v com dist[v] = k-1, já que dist[w] = dist[v] + 1. Pela H.I. v está na camada k-1, portanto existe um caminho de comprimento k até w. Resta mostrar que não existe um caminho de comprimento menor que k até w. Note que, se fosse esse o caso, pela H.I. teríamos dist[w] = k' para algum k'<k. Como w ainda não havia sido encontrado, sabemos que esse não é o caso. Portanto, o algoritmo calcula corretamente a distância até w.



componentes(grafo G=(V,E)) {
	num_comps = 0
	
	para v \in V
		marque v como não encontrado
	
	para s = 1 até n
		se s não encontrado
			num_comps++
			marque s como encontrado
			comp[s] = num_comps
			
			seja Q uma fila inicializada com o vértice s
			
			enquanto Q != \empty
				remova um vértice v do início de Q
				para cada aresta (v, w)
					se w não foi encontrado
						marque w como encontrado
						insira w no final de Q
						comp[w] = num_comps


Eficiência:

 - O(n + m)