Busca em Profundidade (DFS)

A DFS segue um caminho até o fim e só então volta para tentar os outros.

Intuição

É explorar um labirinto com um fio na mão: você segue em frente até esbarrar num beco ou num lugar já visitado, e então volta pelo fio até a última bifurcação com opções. A pilha de chamadas é o fio.

Visualização

Código

Python

def dfs(grafo, u, descoberta=None):
    if descoberta is None:
        descoberta = {}
    descoberta[u] = len(descoberta) + 1
    for v in grafo[u]:
        if v not in descoberta:
            dfs(grafo, v, descoberta)
    return descoberta

Java

static void dfs(List<Integer>[] g, int u, int[] desc, int[] tempo) {
    desc[u] = ++tempo[0];
    for (int v : g[u])
        if (desc[v] == 0) dfs(g, v, desc, tempo);
}

Complexidade

Tempo $O(V + E)$ e espaço $O(V)$ pela profundidade da recursão.

Quando usar

Detectar ciclos, ordenação topológica, componentes fortemente conexos (Tarjan) e backtracking.

Exercícios

1. Em que ordem os vértices são descobertos na animação?

Contribuição

Se você tiver materiais úteis deste algoritmo, pode colaborar com a biblioteca e ajudar a enriquecer esta seção.