Conectividade e Ciclos¶

Conectividade tem significados diferentes em grafos direcionados e não direcionados.

Componentes não direcionados¶

Inicie uma BFS ou DFS a partir de cada vértice ainda não visitado. Cada percurso descobre exatamente um componente conexo. O tempo total é Θ(V + E), e o espaço auxiliar é Θ(V).

Uma DFS não direcionada detecta um ciclo quando encontra um vizinho visitado que não corresponde à aresta de retorno ao pai do vértice atual. Arestas paralelas exigem uma implementação que considere a identidade da aresta; comparar apenas os vértices pais pode deixar de detectar um ciclo de duas arestas em um multigrafo.

Ciclos direcionados¶

Use três estados:

branco: não descoberto;
cinza: ativo no caminho atual da DFS;
preto: completamente processado.

Uma aresta para um vértice cinza é uma aresta de retorno e prova a existência de um ciclo direcionado. Uma aresta para um vértice preto não prova isso. O algoritmo topológico de Kahn oferece outro teste: se não conseguir emitir todos os vértices, existe um ciclo.

Conectividade incremental¶

A união de conjuntos disjuntos responde a consultas de conectividade com eficiência enquanto arestas não direcionadas são apenas adicionadas. Ela não aceita remoções arbitrárias nem reconstrói um caminho real. Conectividade dinâmica com remoções exige técnicas mais fortes ou processamento offline.

Bipartição¶

Colore cada componente com duas cores durante uma BFS/DFS. Toda aresta deve unir cores opostas. Um conflito prova a existência de um ciclo ímpar; inversamente, um grafo não direcionado sem ciclos ímpares é bipartido.

Exercícios¶

Estenda o percurso para retornar os vértices de cada componente.
Reconstrua um ciclo ímpar após um conflito de coloração.
Compare conectividade fraca e forte em grafos direcionados.