Busca em Profundidade

A busca em profundidade (DFS) segue um caminho até não poder continuar e então retrocede.

static void depthFirst(
        List<List<Integer>> graph, int vertex, boolean[] visited) {
    visited[vertex] = true;
    for (int neighbor : graph.get(vertex)) {
        if (!visited[neighbor]) depthFirst(graph, neighbor, visited);
    }
}

Para percorrer um grafo desconectado, execute a busca a partir de cada vértice ainda não visitado. Uma pilha explícita evita o estouro da pilha de chamadas em grafos profundos.

Invariante e custo

Depois de marcado, um vértice nunca volta a ser visitado recursivamente. Assim, cada vértice é processado no máximo uma vez e cada entrada de adjacência é inspecionada uma vez. O tempo é Θ(V + E), e o estado de visitação mais a pilha usam espaço auxiliar O(V).

Aplicações

• componentes conexos em grafos não direcionados;
• detecção de ciclos com o estado do pai ou de cores;
• ordenação topológica com os tempos de término;
• componentes fortemente conexos;
• pontos de articulação e pontes.

Um indicador booleano de visitação é insuficiente para todo algoritmo de detecção de ciclos direcionados. Três cores — não visitado, ativo e concluído — distinguem uma aresta para a pilha de recursão atual de uma aresta para uma subárvore já concluída.