Busca em Profundidade (DFS)

Agora que sabemos como representar um grafo, aprenderemos a percorrê-lo. Percorrer refere-se ao processo de visita (verificação e/ou atualização) de cada vértice em um grafo. Esse processo é também conhecido como busca em grafo.

Nesta lição, discutiremos um algoritmo de busca em grafos conhecido como Busca em profundidade (DFS).

O algoritmo de busca em profundidade é um algoritmo recursivo para percorrer um grafo. A ideia deste algoritmo é criar uma função recursiva que irá percorrer o nosso grafo. Assim, vamos criar uma função recursiva que receberá um vértice como parâmetro. Quando chamamos , a nossa função fará os seguintes passos:

1. Marca como visitado
2. Itera sobre todos os vizinhos de
3. Se não tiver sido visitado, chamamos

Precisamos marcar um vértice como visitado para não visitar um vértice mais do que uma vez. Para implementar isso, utilizaremos um vetor booleano , onde será igual a se e somente se nós já visitámos o vértice .

Para executar a nossa DFS em uma componente, escolheremos um vértice para ser a fonte da nossa busca e então chamaremos . Executando a nossa DFS a partir de uma fonte, visitaremos todos os vértices que estão na mesma componente da fonte e a complexidade será linear no tamanho da nossa componente (número de vértices + número de arestas) porque visitaremos cada vértice uma vez e cada aresta duas vezes (uma para cada ponta).

A implementação desta função recursiva está no código abaixo.

void dfs(int current)
{
    visited[current] = true; // Marca current como visitado