Algoritmo ingênuo para detectar pontes em um grafo §

---

Problema: Dado um grafo não dirigido , encontrar todas as pontes (ou arestas de corte).

Uma abordagem simples para resolver esse problema de detecção de pontes no grafo, podemos remover cada aresta do grafo e verificar se essa remoção desconecta o grafo.

1. Iterar sobre cada aresta : O algoritmo percorre todas as arestas do grafo G.
2. Remover a aresta: A aresta em teste é removida temporariamente.
3. Verificar a conectividade: Após a remoção, o algoritmo verifica se o grafo ainda está conexo. Isso pode ser feito com uma busca em profundidade (DFS) ou busca em largura (BFS) para ver se todos os vértices ainda são alcançáveis a partir de um ponto de partida.
4. Adicionar a aresta de volta: O estado original do grafo é restaurado para o teste da próxima aresta. Se a aresta foi identificada como uma ponte, ela é registrada.

Implementação em C §

void dfs(int u, bool visited[]) {
    visited[u] = true;
    for (int v = 0; v < V; v++) {
        if (G[u][v] && !visited[v]) {
            dfs(v, visited);
        }
    }
}
 
bool is_connected() {
    bool visited[MAX_VERTICES] = {false};
    
    int start_node = -1;
    for(int i = 0; i < V; i++) {
        for(int j = 0; j < V; j++) {
            if(G[i][j]) {
                start_node = i;
                break;
            }
        }
        if (i != -1) break;
    }
 
    if (start_node == -1) {
        return true; 
    }
 
    dfs(start_node, visited);
 
    for (int i = 0; i < V; i++) {
        bool has_edge = false;
        for(int j = 0; j < V; j++) {
            if(G[i][j]) {
                has_edge = true;
                break;
            }
        }
        if (has_edge && !visited[i]) {
            return false;
        }
    }
 
    return true;
}
 
void detect_bridges() {
    printf("Bridges found:\n");
 
    for (int u = 0; u < V; u++) {
        for (int v = u + 1; v < V; v++) {
            if (G[u][v]) {
                remove_edge(u, v);
 
                if (!is_connected()) {
                    printf("(%d, %d)\n", u, v);
                }
 
                add_edge(u, v);
            }
        }
    }
}

Complexidade:

Referências §

---

Teoria dos Grafos - Pontes e pontos de articulação