Aplicações de DFS e Grafos: Ordenação Topológica

1. O Problema das Dependências

Imagine que você precisa se vestir. Você não pode calçar o sapato antes da meia, nem o cinto antes da calça. Ou em Computação: para compilar o módulo A, você precisa antes ter compilado B e C.

Esse problema é modelado como encontrar uma ordem linear de execução em um Grafo Direcionado. Essa ordenação chama-se Ordenação Topológica.

Requisito: O grafo não pode ter ciclos. Ele deve ser um DAG (Directed Acyclic Graph). Se houver ciclo (A precisa de B, B precisa de A), é impossível satisfazer as dependências.

2. Solução com DFS (A Mágica da Pós-Ordem)

A ideia é simples: uma tarefa só está “pronta” quando todas as suas dependências (filhos no grafo) foram finalizadas. Na DFS, o momento em que “terminamos” um nó (quando a chamada recursiva retorna) significa que já visitamos todos os seus descendentes.

Algoritmo: 1. Execute a DFS em todos os nós não visitados. 2. No momento em que a DFS de um vértice \(u\) terminar, adicione \(u\) em uma Lista. 3. No final, a Ordenação Topológica é a lista invertida (do último que terminou para o primeiro).

Stack<Integer> topoSort = new Stack<>();
boolean[] visitado = new boolean[V];

void dfsTopo(int u) {
    visitado[u] = true;
    for (int v : adj.get(u)) {
        if (!visitado[v]) dfsTopo(v);
    }
    // Todos os filhos de u já foram processados.
    // u já pode entrar na lista.
    topoSort.push(u);
}

// No main:
for (int i=0; i<V; i++) if (!visitado[i]) dfsTopo(i);

while (!topoSort.isEmpty()) System.out.print(topoSort.pop() + " ");

3. Solução com Algoritmo de Kahn (Graus de Entrada)

Geralmente preferido por ser iterativo (usa Fila) e detectar ciclos facilmente.

Algoritmo: 1. Calcule o Grau de Entrada (Indegree) de todos os vértices. 2. Adicione todos os nós com Indegree == 0 em uma Fila. (Esses não tem dependências). 3. Enquanto a fila não vazia: - Remova \(u\). Imprima (ou salve). - Para cada vizinho \(v\) de \(u\): - Decremente Indegree[v]-- (removemos a dependência \(u\)). - Se Indegree[v] virou 0, adicione \(v\) na Fila. 4. Se ao final o número de nós impressos for \(< V\), o grafo tem ciclo.

public List<Integer> kahn(int V, List<List<Integer>> adj) {
    int[] inDegree = new int[V];
    for (int u = 0; u < V; u++) {
        for (int v : adj.get(u)) inDegree[v]++;
    }
    
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < V; i++) {
        if (inDegree[i] == 0) q.add(i);
    }
    
    List<Integer> result = new ArrayList<>();
    while (!q.isEmpty()) {
        int u = q.poll();
        result.add(u);
        
        for (int v : adj.get(u)) {
            inDegree[v]--;
            if (inDegree[v] == 0) q.add(v);
        }
    }
    
    if (result.size() != V) {
        throw new IllegalStateException("Grafo contém Ciclo!");
    }
    return result;
}

4. Componentes Conexos (Flood Fill)

Em um grafo não-direcionado, queremos saber quantos “grupos” isolados existem. Exemplo: Contar quantas ilhas existem num mapa, ou quantas redes sociais desconectadas.

Algoritmo: 1. Inicialize count = 0. 2. Para cada vértice i de 0 a V-1: - Se !visitado[i]: - count++. - Chame dfs(i) (ou bfs) para marcar todo mundo que pertence ao mesmo grupo de i.

int contarComponentes() {
    int count = 0;
    Arrays.fill(visitado, false);
    for (int i = 0; i < V; i++) {
        if (!visitado[i]) {
            count++;
            dfs(i); // Inunda o componente
        }
    }
    return count;
}

Em matrizes (pixel art, jogos), isso se chama Flood Fill (Balde de Tinta do Paint).

5. Verificação de Grafo Bipartido (Coloração)

Um grafo é Bipartido se pudermos dividir os vértices em dois conjuntos \(A\) e \(B\) tal que todas as arestas liguem um nó de \(A\) a um de \(B\). Propriedade: Um grafo é bipartido \(\iff\) não contém ciclo de tamanho ímpar.

Algoritmo (DFS/BFS): 1. Tente colorir o nó inicial com Cor 0. 2. Pinte todos os vizinhos com Cor 1. 3. Os vizinhos dos vizinhos com Cor 0… (flip-flop). 4. Se encontrar um vizinho que já tem a mesma cor que você: Impossível, não é bipartido.

int[] color = new int[V]; // -1: sem cor, 0: Azul, 1: Vermelho
Arrays.fill(color, -1);

boolean isBipartite(int start) {
    Queue<Integer> q = new LinkedList<>();
    q.add(start);
    color[start] = 0;
    
    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : adj.get(u)) {
            if (color[v] == -1) {
                color[v] = 1 - color[u]; // Cor oposta
                q.add(v);
            } else if (color[v] == color[u]) {
                return false; // Conflito de cores
            }
        }
    }
    return true;
}
Back to top