# Percursos e componentes em grafos

BFS, DFS, ordenação topológica, bipartição e componentes fortemente conexas com Kosaraju e Tarjan.

Página: https://resumos.rgo.pt/cadeiras/da/grafos-percursos/

Num grafo dirigido com arestas $0\to1$, $0\to2$, $1\to3$, $2\to3$ e $3\to4$, existem dois caminhos de 0 até 4, ambos com três arestas. A pesquisa em largura encontra um deles ao expandir os vértices por distância crescente. A pesquisa em profundidade segue primeiro um ramo até ao fim e usa o regresso para analisar ciclos e dependências. A ordem de visita e o estado guardado durante cada pesquisa servem depois para ordenar tarefas e para separar regiões onde todos os vértices se alcançam mutuamente.

Esta lição assume grafos dirigidos salvo indicação em contrário e usa $n=|V|$ vértices e $m=|E|$ arestas. Os custos indicados valem para listas de adjacência.

O vídeo de Rodrigo Dias reúne grafos, força bruta, gulosos e divisão e conquista, como apoio à revisão dessas estratégias.

[Vídeo: Grafos, Brute-force, Greedy e Divide & Conquer... Ufa 😅](https://www.youtube.com/watch?v=PmnwrC0mA-4)

[Abrir no YouTube](https://www.youtube.com/watch?v=PmnwrC0mA-4)

## BFS e caminhos sem pesos

A pesquisa em largura, **BFS**, mantém uma fila. Começa com $d[s]=0$, marca $s$ e coloca-o na fila. Quando retira $u$, descobre cada vizinho ainda não marcado, atribui $d[v]=d[u]+1$, guarda `pai[v]=u` e coloca $v$ na fila.

Marca um vértice **quando o inseres**, para que duas arestas não o insiram duas vezes. A fila processa primeiro todos os vértices de distância 0, depois os de distância 1, e assim sucessivamente, por isso quando descobre $v$ pela primeira vez nenhum caminho mais curto ficou por explorar. Logo $d[v]$ é o mínimo número de arestas de um caminho de $s$ a $v$.

Com arestas $0\to1$, $0\to2$, $1\to3$, $2\to3$, $3\to4$, a fila evolui assim, supondo vizinhos por ordem numérica:

| Retirado | Fila depois de descobrir vizinhos | Nova informação |
| --- | --- | --- |
| 0 | 1, 2 | $d[1]=d[2]=1$ |
| 1 | 2, 3 | $d[3]=2$, pai de 3 é 1 |
| 2 | 3 | 3 já foi descoberto |
| 3 | 4 | $d[4]=3$ |
| 4 | vazia | Termina |

O caminho reconstruído é $0,1,3,4$. $0,2,3,4$ também é mínimo; a ordem de adjacência desempata. Um vértice isolado 5 mantém distância desconhecida e não tem caminho. Não lhe atribuas distância zero.

O programa lê `n m s`, seguido de `m` pares dirigidos `u v`. Os vértices vão de 0 a `n-1`; aceita até 2000 vértices e 20000 arestas.

**main.cpp**

```cpp
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

int main() {
    int n, m, s;
    if (!(std::cin >> n >> m >> s) || n < 1 || n > 2000 ||
        m < 0 || m > 20000 || s < 0 || s >= n) {
        std::cout << "entrada invalida\n";
        return 0;
    }
    std::vector<std::vector<int>> adj(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        if (!(std::cin >> u >> v) || u < 0 || u >= n || v < 0 || v >= n) {
            std::cout << "entrada invalida\n";
            return 0;
        }
        adj[u].push_back(v);
    }
    std::vector<int> dist(n, -1), pai(n, -1);
    std::queue<int> fila;
    dist[s] = 0;
    fila.push(s);
    while (!fila.empty()) {
        int u = fila.front();
        fila.pop();
        for (int v : adj[u]) {
            if (dist[v] != -1) continue;
            dist[v] = dist[u] + 1;
            pai[v] = u;
            fila.push(v);
        }
    }
    for (int v = 0; v < n; ++v)
        std::cout << dist[v] << (v + 1 == n ? '\n' : ' ');
    int destino = n - 1;
    if (dist[destino] == -1) {
        std::cout << "sem caminho\n";
        return 0;
    }
    std::vector<int> caminho;
    for (int v = destino; v != -1; v = pai[v]) caminho.push_back(v);
    std::reverse(caminho.begin(), caminho.end());
    for (int v : caminho) std::cout << v << ' ';
    std::cout << '\n';
}
```

A saída dá as distâncias `0 1 1 2 3 -1`; o caminho para o último vértice é `sem caminho`. Muda `n` para 5 e o programa reconstrói `0 1 3 4`. Com listas de adjacência, a BFS usa $O(n+m)$ tempo e $O(n)$ memória auxiliar. Pesos distintos deixam de ser medidos pelo número de arestas; nesse caso usa os [algoritmos ponderados](https://resumos.rgo.pt/cadeiras/da/caminhos-minimos/).

## DFS, tempos e ciclos

A pesquisa em profundidade, **DFS**, continua pelo vizinho ainda não visitado até não poder avançar; depois regressa. Uma chamada recursiva ou uma pilha com o estado da chamada implementa esse regresso. Uma DFS a partir de $s$ só percorre os alcançáveis. Para percorrer todo o grafo, inicia outra DFS em cada vértice ainda por visitar.

Mantém três estados: branco, ainda não descoberto; cinzento, chamada ativa; preto, chamada terminada. Num grafo dirigido, uma aresta para um vértice cinzento fecha um ciclo, porque existe um caminho de chamadas ativas desse vértice até ao atual. Uma aresta para um preto não prova um ciclo.

Se guardares tempos de descoberta e término, os intervalos de dois vértices são disjuntos ou um contém o outro. A contenção corresponde à relação ancestral na floresta DFS. Uma aresta de árvore descobre um branco; uma aresta de retorno vai para um ancestral cinzento. Num grafo não dirigido, a aresta de volta para o pai não conta como ciclo. Com arestas paralelas, distinguir a **aresta** usada para chegar é mais seguro do que ignorar todo o vizinho pai.

DFS também custa $O(n+m)$. A pilha pode ter profundidade $n$. Grafos muito grandes podem exigir uma implementação iterativa para não esgotar a pilha de execução.

## Ordenação topológica

Uma ordenação topológica de um grafo dirigido põe $u$ antes de $v$ para toda a aresta $u\to v$. Existe exatamente quando o grafo é um **DAG**, isto é, não tem ciclos dirigidos.

O algoritmo de Kahn mantém graus de entrada. Insere numa fila todos os vértices com grau zero; retira um, emite-o e reduz os graus dos seus sucessores. Se um sucessor passa a zero, insere-o.

O invariante é que um vértice emitido não tem predecessores por emitir. Se foram emitidos menos de $n$, o subgrafo restante tem cada vértice com algum predecessor restante, por isso seguir esses predecessores num conjunto finito repete um vértice e revela um ciclo. Não devolvas uma ordenação parcial como se fosse válida.

Para $a\to c$, $b\to c$, $c\to d$, $b\to e$, tanto $a,b,c,d,e$ como $b,e,a,c,d$ são válidas. Não existe uma única ordem obrigatória. Uma fila de prioridade produz o menor disponível segundo uma regra de desempate, com custo adicional. Outra solução é inverter a ordem de término de uma DFS, depois de excluir arestas de retorno.

## Componentes fortemente conexas

Uma componente fortemente conexa, **SCC**, é um conjunto maximal em que cada vértice alcança todos os outros por caminhos dirigidos. “Maximal” significa que não podes acrescentar outro vértice mantendo a propriedade. Não é o mesmo que procurar a componente de maior tamanho.

![Grafo dirigido com ciclo a b c, ciclo d e, aresta de c para d e aresta de e para f. As componentes são a b c, d e e f.](https://resumos.rgo.pt/cadeiras/da/grafos-percursos/figura-1.svg)

Neste grafo, as SCC são $\{a,b,c\}$, $\{d,e\}$ e $\{f\}$. A direção $c\to d$ não as funde: não há regresso de $d$ a $c$. Contrair cada SCC num vértice produz um DAG, a **condensação**. Se a condensação tivesse um ciclo, essas componentes seriam mutuamente alcançáveis e formariam uma única SCC.

### Kosaraju

1.  Faz uma DFS completa em $G$ e guarda os vértices por ordem de término.
2.  Constrói o transposto $G^T$, invertendo todas as arestas.
3.  Faz DFS em $G^T$ por ordem decrescente de término da primeira passagem. Cada nova árvore é uma SCC.

Entre SCC distintas, uma aresta $C\to D$ implica que o maior tempo de término de $C$ é superior ao de $D$. Na segunda passagem, começamos numa SCC sem entrada na condensação ainda não processada de $G$; no transposto, ela não tem saída para uma SCC não processada. A DFS recolhe exatamente os seus vértices. Dentro de uma SCC, inverter as arestas conserva a alcançabilidade mútua.

A primeira DFS deve abranger todos os vértices, não apenas os alcançáveis de um escolhido. As duas passagens e o transposto custam $O(n+m)$.

### Tarjan

Tarjan encontra SCC numa única DFS. Para cada vértice $u$, guarda `index[u]`, o número de descoberta, e `low[u]`, o menor índice a que a exploração de $u$ ainda pode ligar-se dentro da região ativa. Mantém ainda uma pilha dos vértices descobertos que não pertencem a uma SCC já fechada.

Ao descobrir $u$, atribui o mesmo valor a `index` e `low` e empilha-o. Para cada aresta $u\to v$:

*   Se $v$ é novo, faz DFS em $v$ e usa `low[u] = min(low[u], low[v])`.
*   Se $v$ já está na pilha, usa `low[u] = min(low[u], index[v])`.
*   Se $v$ saiu da pilha, pertence a uma SCC fechada e não deve reduzir `low[u]`.

No fim de $u$, se `low[u] == index[u]`, $u$ é a raiz de uma SCC. Desempilha até retirar $u$, incluindo-o. A pilha de Tarjan é distinta da pilha de chamadas: um vértice pode terminar a sua chamada e continuar à espera da raiz da sua SCC.

No ciclo $a\to b\to c\to a$, com índices 0, 1, 2, a aresta $c\to a$ dá `low[c]=0`, que regressa até `low[b]=0`. Só $a$ fecha a SCC.

Segue a DFS por $a,b,c,d,e,f$ no grafo do exemplo:

| Acontecimento | Pilha de Tarjan, da base para o topo | Efeito |
| --- | --- | --- |
| Descobrir $a,b,c$ | $a,b,c$ | Índices 0,1,2 |
| Examinar $c\to a$ | $a,b,c$ | $low[c]=0$; a chamada ainda não termina |
| Descobrir $d,e$ | $a,b,c,d,e$ | Índices 3,4; $e\to d$ dá $low[e]=3$ |
| Descobrir e terminar $f$ | $a,b,c,d,e$ | $f$ fecha sozinho e sai da pilha |
| Terminar $e$ e $d$ | $a,b,c$ | $low[d]=index[d]=3$: fecha $\{d,e\}$ |
| Regressar por $c,b,a$ | Vazia | O valor 0 regressa a $b$; $a$ fecha $\{a,b,c\}$ |

Ao regressar de $d$ para $c$, o valor $low[d]=3$ não reduz $low[c]=0$. A ligação só vai da primeira SCC para a segunda. Se, noutra exploração, encontrarmos um vizinho já retirado da pilha, não usamos o seu índice para reduzir `low`. Uma marca `visited` não distingue esse caso de um vértice ativo; precisamos de `onStack`.

O custo é $O(n+m)$ tempo e $O(n)$ memória auxiliar.

## Testar bipartição

Um grafo não dirigido é bipartido se podemos dar duas cores aos vértices, com cores diferentes nos extremos de cada aresta. Faz BFS em **cada componente**; atribui ao vizinho novo a cor oposta. Se uma aresta liga duas cores iguais, rejeita.

Um ciclo ímpar impede a alternância de fechar corretamente. Reciprocamente, se há conflito, os caminhos da árvore até aos extremos da aresta produzem um ciclo ímpar depois de remover o prefixo comum. Uma árvore e um ciclo de comprimento par são bipartidos; um triângulo não é. A bipartição será usada na redução de [emparelhamento a fluxo](https://resumos.rgo.pt/cadeiras/da/fluxo-maximo/#emparelhamento-bipartido).

## Exercícios

Uma ordem que fica a meio

Num grafo dirigido há arestas a→b, b→c, c→b e d→a. Faz Kahn e explica por que o resultado parcial não é uma ordenação topológica. Identifica as SCC.

Pista

Começa pelos graus de entrada: só d tem grau zero.

Mais uma pista

Depois de emitir d e a, b ainda recebe uma aresta de c e c recebe uma de b.

Solução

Kahn emite d e depois a. Restam b e c com grau positivo, por isso não emite os quatro vértices e rejeita a ordenação. O ciclo b→c→b impede qualquer ordem com todos os predecessores antes dos sucessores. As SCC são {d}, {a} e {b,c}; a condensação é d→a→{b,c}, um DAG.

Confere a tua resposta:

*   Obtive a lista parcial d,a.
*   Identifiquei o ciclo e rejeitei a ordem.
*   Separei as três SCC.

Erros frequentes

Uma lista parcial não pode ser apresentada como resposta válida. Estar numa componente não dirigida não chega para formar uma SCC; é preciso alcançabilidade nos dois sentidos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/da/grafos-percursos/#ordena%C3%A7%C3%A3o-topol%C3%B3gica)

Uma aresta para uma SCC já fechada

Tarjan já fechou a SCC {x,y}. Mais tarde descobre z com uma aresta z→x, mas sem caminho de x para z. Deve essa aresta reduzir low\[z\]? Explica usando a pilha.

Pista

Distingue um vértice já visitado de um vértice ainda na pilha de Tarjan.

Mais uma pista

x foi desempilhado quando a sua SCC fechou. A aresta só permite ir de z para essa componente.

Solução

Não. Para um vizinho já visitado, Tarjan só usa index\[x\] se x ainda estiver na pilha. Como {x,y} já fechou e saiu da pilha, a sua aresta de entrada não pode provar regresso a um ancestral ativo de z. Sem outros caminhos, z fecha uma SCC separada. Reduzir low\[z\] para o índice antigo de x impediria fechar corretamente a nova componente.

Confere a tua resposta:

*   Usei a condição onStack.
*   Mantive z separado de {x,y}.
*   Expliquei a direção da alcançabilidade.

Erros frequentes

A pilha de componentes não é a pilha de chamadas. Usar apenas visited em vez de onStack junta informação de regiões que já foram concluídas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/da/grafos-percursos/#tarjan)