Matemática Discretapara Engenheiros

3. O Algoritmo

Nesta parte, formalizamos a Busca em Profundidade usando a apresentação clássica de Introduction to Algorithms (CLRS).

A DFS não é apenas uma intuição sobre “ir profundamente”. Ela é um procedimento preciso de travessia em grafos, com estado bem definido, estrutura recursiva e marcações de tempo.

3.1 Estado Mantido pela DFS

Para cada vértice u ∈ V, a DFS armazena:

• color[u] — estado da exploração
• π[u] — predecessor (pai) na árvore DFS
• d[u] — tempo de descoberta
• f[u] — tempo de finalização

Esses valores permitem que a DFS faça muito mais do que apenas percorrer o grafo. Eles codificam informação estrutural que será essencial depois para classificação de arestas, detecção de ciclos e ordenação topológica.

3.2 O Significado das Cores

3.3 Procedimento Principal — DFS

O procedimento global da DFS inicializa todos os vértices e depois percorre o grafo. Se encontrar um vértice WHITE, inicia uma nova árvore DFS com raiz nesse vértice.

DFS(G):

    for each vertex u in V[G]:
        color[u] = WHITE
        π[u] = NIL

    time = 0

    for each vertex u in V[G]:
        if color[u] == WHITE:
            DFS-VISIT(G, u)

3.4 Procedimento Recursivo — DFS-VISIT

A exploração real acontece dentro da sub-rotina recursiva:

DFS-VISIT(G, u):

    time = time + 1
    d[u] = time
    color[u] = GRAY

    for each v in Adj[u]:
        if color[v] == WHITE:
            π[v] = u
            DFS-VISIT(G, v)

    color[u] = BLACK
    time = time + 1
    f[u] = time

Esse procedimento captura toda a lógica da exploração profunda: descobrir um vértice, visitar recursivamente os vizinhos ainda não visitados e só então finalizar o vértice atual.

3.5 Tempos de Descoberta e Finalização

A DFS atribui dois timestamps a cada vértice:

• d[u] — quando u é descoberto pela primeira vez
• f[u] — quando a exploração de u é concluída

Esses timestamps são uma das características mais importantes da DFS. Eles transformam uma travessia em uma ferramenta de análise estrutural.

3.6 Ponteiros de Pai e Árvores DFS

Sempre que a DFS descobre um vértice WHITE v a partir de um vértice u, ela define:

Esses ponteiros de pai definem a árvore DFS enraizada no vértice que iniciou a exploração.

Se o grafo tiver múltiplas regiões desconexas, a DFS constrói uma coleção de árvores, chamada de floresta DFS.

3.7 Por que a DFS Pode Produzir uma Floresta

A DFS inicia uma nova exploração recursiva sempre que encontra um vértice que ainda está WHITE no laço externo.

Portanto:

• Se o grafo for totalmente alcançável a partir de uma única fonte, a DFS produz uma árvore.
• Se o grafo tiver múltiplas componentes desconexas, a DFS produz múltiplas árvores.