Algoritmo otimizado para detectar pontes em um grafo
A lógica do algoritmo otimizado para detecção de pontes é significativamente mais eficiente que a abordagem ingênua. Ele utiliza uma única travessia de Busca em Profundidade (DFS) para identificar todas as pontes com uma complexidade de tempo de
A ideia central é que uma aresta é uma ponte se, e somente se, ela não faz parte de um ciclo no grafo. A implementação usa o algoritmo DFS para identificar quais arestas possuem um “caminho de volta” (através de um ciclo) que conecta seus terminais.
Para isso, o algoritmo utiliza dois conceitos fundamentais durante a travessia DFS:
1. Tempo de Descoberta (pre)
Durante a busca em profundidade, um contador de “tempo” é mantido para registrar quando cada vértice é visitado pela primeira vez.
pre[v]: Armazena o tempo de descoberta do vérticev.- Isso cria uma “árvore DFS”, onde a relação
pre[v] < pre[w]indica quevfoi descoberto antes dew.
2. Menor Ancestral Alcançável (low)
Este é o conceito chave do algoritmo.
Para cada vértice v, o valor low[v] armazena o menor tempo de descoberta (pre) que é alcançável a partir de v (incluindo o próprio v) seguindo as arestas da árvore DFS e no máximo uma aresta de retorno.
- Intuitivamente:
low[v]nos diz qual é o “ancestral mais alto” na árvore DFS que o vérticevou qualquer um de seus descendentes consegue alcançar. - Cálculo do
low[v]:- Inicialmente,
low[v]é definido comopre[v]. - Ao explorar os vizinhos
wdev:- Se
wé um filho devna árvore DFS, após a chamada recursiva parawretornar, o valor delow[v]é atualizado para o mínimo entre seu valor atual elow[w]. Isso propaga a informação do ancestral mais alto alcançável do filho para o pai. - Se
wjá foi visitado e não é o pai direto dev, então a arestaé uma aresta de retorno para um ancestral. Neste caso, low[v]é atualizado para o mínimo entre seu valor atual epre[w].
- Se
- Inicialmente,
Condição para Identificar uma Ponte
Com os valores de pre e low calculados, a identificação de uma ponte se torna uma simples comparação.
Uma aresta de arborescência v é pai de w na árvore DFS) é uma ponte se, e somente se, a seguinte condição for satisfeita:
low[w] > pre[v]
low[w]representa o ancestral mais antigo que a sub-árvore com raiz emwconsegue alcançar.pre[v]é o tempo de descoberta do pai,v.- Se o menor ancestral que
wou seus descendentes podem alcançar (low[w]) ainda foi descoberto depois dev(pre[v]), isso significa que não existe nenhuma aresta de retorno da sub-árvore dewparavou qualquer um de seus ancestrais. - Portanto, a única maneira de ir da sub-árvore de
wpara o resto do grafo é através da aresta. Removê-la desconectaria o grafo, tornando-a uma ponte.
A apresentação também menciona uma condição alternativa equivalente: a aresta low[w] == pre[w]. Isso ocorre porque, se low[w] não pôde ser atualizado para um valor menor que seu próprio tempo de descoberta, significa que não encontrou nenhum caminho de volta para um ancestral.