Percursos e componentes em grafos

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.

Grafos, Brute-force, Greedy e Divide & Conquer... Ufa 😅Carregar vídeo do YouTube

Abrir no YouTube

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:

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.

#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.

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.

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:

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.