Busca em Profundidade

Busca em profundidade é um dos principais algoritmos de grafos.

O algoritmo encontra o primeiro caminho lexicográfico no grafo a partir de um vértice(nó) fonte $u$ para cada outro vértice. O algoritmo também encontra os menores caminhos em uma árvore, porém, em grafos genéricos, este não é o caso.

O algoritmo funciona em tempo $O(m + n)$, onde $n$ é o número de vértices e $m$ é o número de arestas.

Descrição

A idéia por trás da DFS é ir o mais fundo possível no grafo, e voltar atrás quando você estiver em um vértice sem vértices adjacentes(nós filhos) não visitados.

Nós começamos a procura em um vértice. Depois de visitar o vértice, nós executamos uma DFS para cada vértice adjacente(nós filhos) que não foram visitados antes. Nesse caminho nós visitamos todos os vértices que são alcançáveis pelo vértice inicial.

Aplicações

Classificação das arestas de um grafo

Nós podemos classificar as arestas usando os tempos de entrada e saída dos nós finais $u$ e $v$ das arestas $(u,v)$.

Nós executamos uma DFS e classificamos as arestas encontradas usando as seguintes regras:

Se $v$ não foi visitado:

Se $v$ é visitado antes que $u$:

Nota: Forward edges e cross edges apenas existem em grafos direcionados.

Implementação

vector<vector<int>> g; // grafo como lista de adjacência
int n; // número de vértices(nós)

vector<bool> vis;   //vetor para marcar os visitados

void dfs(int v) {
    vis[v] = true;
    for (int u : g[v]) {
        if (!vis[u])
            dfs(u);  //chamamos a função para ir mais fundo no grafo
    }
}
			

Visualize aqui.

Esta é a implementação mais simples da Busca em Profundidade(dfs). Conforme descrito, pode ser útil também calcular a cor dos vértices e os tempos de entrada e saída. Vamos colorir todos os vértices com a cor 0, se não tivermos visitado ainda, com a cor 1 se já o tivermos visitado e com a cor 2 se já saímos do vértice.

Aqui está uma implementação genérica que adcionalmente programa os 'tempos' e 'cores':

vector<vector<int>> g; //grafo
int n; // número de vértices(nós)

vector<int> cor;

vector<int> time_in, time_out;   //marca o preciso instante do nó(entrada e saída)
int dfs_timer = 0;   //funciona como um relógio para a dfs

void dfs(int v) {
    time_in[v] = dfs_timer++;
    cor[v] = 1;
    for (int u : adj[v])
        if (cor[u] == 0)
            dfs(u);
    cor[v] = 2;
    time_out[v] = dfs_timer++;
}
			

Problemas