Seja um grafo não direcionado. Uma ponte é definida como uma aresta que, quando removida, desconecta o grafo (ou mais precisamente, aumenta o número de componentes conectados no grafo). A tarefa é encontrar todas as pontes no grafo fornecido.
Informalmente, o problema é formulado da seguinte maneira: dado um mapa de cidades conectadas com estradas, encontre todas as estradas "importantes", isto é, estradas que, quando removidas, causam o desaparecimento de um caminho entre alguns pares de cidades.
O algoritmo descrito aqui é baseado em uma DFS e tem complexidade $O(N+M)$, onde $N$ é o número de vértices e $M$ é o número de arestas no grafo.
Também há o artigo encontrando pontes online - diferentemente do algoritmo offline descrito aqui, o algoritmo online é capaz de manter a lista de todas as pontes em um grafo em constante mudança (supondo que o único tipo de mudança seja a adição de novas arestas).
Escolha um vértice arbitrário do grafo $raiz$ e execute uma DFS a partir dele. Observe que:
Agora temos que aprender a verificar esse fato para cada vértice com eficiência. Usaremos o "tempo de entrada" do nó calculado pela DFS.
Então, seja $tin[v]$ o tempo de entrada para o nó $v$. Introduzimos uma array $low$ que nos permitirá verificar o fato para cada vértice $v$. $low[v]$ é o mínimo de $tin[v]$, os tempos de entrada $tin[p]$ para cada nó $p$ que está conectado ao nó $v$ por uma back-edge $(v, p)$ e os valores de $low[to]$ para cada vértice $to$ que é um descendente direto de $v$ na árvore da DFS:
$$low[v] = \min \begin{cases} tin[v] \\ tin[p]& \text{ para todo }p\text{ em que }(v, p)\text{ back edge} \\ low[to]& \text{ para todo }to\text{ em que }(v, to)\text{ tree edge} \end{cases}$$
Agora, há uma back edge do vértice $v$ ou de um de seus descendentes para um de seus ancestrais se, e somente se, o vértice $v$ tiver um filho $to$ pelo qual $low[to] \leq tin[v]$. Se $low[to] = tin[v]$, a back edge vai diretamente em $v$, caso contrário, vai para um dos ancestrais de $v$.
Portanto, a aresta atual $(v, to)$ na árvore da DFS é uma ponte se, e somente se, $low[to] > tin[v]$.
A implementação precisa distinguir três casos: quando descemos na aresta da árvore da DFS, quando encontramos uma back edge para um ancestral do vértice e quando retornamos a um parente de um vértice. Casos:
Para implementar isso, precisamos de uma função DFS que aceita o vértice parente do nó atual.
Implementação em C++:
int n; // número de nós
vector<vector<int>> adj; // lista de adjacência - grafo
vector<bool> visited;
vector<int> tin, low;
int timer;
void dfs(int v, int p = -1) {
visited[v] = true;
tin[v] = low[v] = timer++;
for (int to : adj[v]) {
if (to == p) continue;
if (visited[to]) {
low[v] = min(low[v], tin[to]);
} else {
dfs(to, v);
low[v] = min(low[v], low[to]);
if (low[to] > tin[v])
IS_BRIDGE(v, to);
}
}
}
void find_bridges() {
timer = 0;
visited.assign(n, false);
tin.assign(n, -1);
low.assign(n, -1);
for (int i = 0; i < n; ++i) {
if (!visited[i])
dfs(i);
}
}
A função principal é find_bridges; ela executa uma inicialização necessária e inicializa a DFS em cada componente conectado do grafo.
A função IS_BRIDGE(a, b) é uma função que processará o fato de que a aresta $(a, b)$ é uma ponte, por exemplo, printando a aresta.
Esta implementação não funciona corretamente se o grafo tiver arestas múltiplas(multiple edges), pois as ignora. Obviamente, essas arestas nunca farão parte da resposta, portanto IS_BRIDGE pode verificar adicionalmente se a ponte relatada não é uma aresta múltipla. Como alternativa, é possível passar para a dfs o índice da aresta usada para entrar no vértice em vez do vértice parente (e armazenar o índice de todos os vértices).