Algoritmos para Grafos  |  Índice

Componentes conexas

Este capítulo trata das componentes conexas de grafos não-dirigidos.  (Os conceitos correspondentes para grafos dirigidos são mais complexos e serão discutido em outra ocasião.)

Grafos não-dirigidos conexos

Um grafo não-dirigido é conexo se cada um de seus vértices está ao alcance de cada um dos demais.  Em outras palavras, um grafo não-dirigido é conexo se tem a seguinte propriedade:  para cada par s t de seus vértices, existe um caminho com origem s e término t.

Um grafo não-dirigido é desconexo se não for conexo.  Para caracterizar grafos não-dirigidos desconexos, precisamos introduzir duas definições: dizemos que um conjunto X de vértices é

1. isolado se nenhuma aresta tem uma ponta em X e outra fora de X e
2. trivial se X for vazio ou contiver todos os vértices do grafo.

Agora podemos enunciar a caracterização:  um grafo não-dirigido é desconexo se e somente se algum conjunto não-trivial de seus vértices é isolado.

Componentes conexas de grafos não-dirigidos

Num grafo não-dirigido, a relação ao‑alcance‑de entre vértices é uma relação de equivalência, ou seja, uma relação reflexiva, simétrica e transitiva.  A propriedade reflexiva e a simétrica são óbvias.  A propriedade transitiva é tecnicamente um pouco mais delicada porque, por definição, um caminho não deve ter arcos repetidos.

Portanto, a relação ao‑alcance‑de impõe uma partição do conjunto de vértices em classes de equivalência: dois vértices s e t estão na mesma classe se e somente se t está ao alcance de s.

Uma componente conexa (= connected component) de um grafo não-dirigido G é o sub­grafo de G induzido por alguma das classes de equivalência da relação ao‑alcance‑de.  Podemos resumir essa definição dizendo que uma componente de um grafo não-dirigido é um sub­grafo conexo maximal do grafo. (Um sub­grafo conexo H de G é maximal se não existe grafo conexo H' tal que  H ⊂ H' ⊆ G, ou seja, não existe sub­grafo conexo H' de G tal que H é sub­grafo próprio de H'.)

Para resolver o problema, poderíamos verificar, para cada par s t de vértices, se t está ao alcance de s. (Basta usar a função GRAPHreach(), por exemplo.)  Mas esse algoritmo é muito lento. Trataremos a seguir de uma solução bem mais eficiente.

Cálculo das componentes conexas

Há muitas maneiras eficientes de calcular as componentes conexas de um grafo não-dirigido.  A função UGRAPHconComps() abaixo usa uma busca em profundidade. O código é análogo ao da função GRAPHdfs(). Cada etapa da busca descobre uma nova componente conexa.

Para identificar as componentes conexas, vamos atribuir um rótulo cc[v] a cada vértice v de tal modo que dois vértices tenham o mesmo rótulo se e somente se estiverem na mesma componente conexa.  (O vetor cc[] é alocado pelo usuário.)

#define UGraph Graph

/* O tipo UGraph é um sinônimo de Graph
   que tem a missão de deixar claro, para o leitor humano,
   que o grafo é não-dirigido.
   (O "U" de "UGraph" é uma abreviatura de "undirected".) */

int cc[1000];

/* A função UGRAPHconComps() devolve o número de componentes conexas 
   do grafo não-dirigido G.
   Além disso, armazena no vetor cc[]
   uma numeração dos vértices tal que
   dois vértices v e w pertencem à mesma componente 
   se e somente se cc[v] == cc[w].
   (O código foi copiado do programa 18.4 
   de Sedgewick.) */

int UGRAPHconComps( UGraph G) 
{ 
   int id = 0;
   for (vertex v = 0; v < G->V; ++v) 
      cc[v] = -1;
   for (vertex v = 0; v < G->V; ++v)
      if (cc[v] == -1) 
         dfsRconComps( G, v, id++);
   return id;
}

/* A função auxiliar dfsRconComps() atribui o número id 
   a todos os vértices
   que estão na mesma componente conexa que v.
   A função supõe que o grafo G
   é representado por listas de adjacência. */

static void dfsRconComps( UGraph G, vertex v, int id) 
{ 
   cc[v] = id;
   for (link a = G->adj[v]; a != NULL; a = a->next)
      if (cc[a->w] == -1) 
         dfsRconComps( G, a->w, id); 
}

Depois de executar UGRAPHconComps() uma só vez, é fácil verificar, em tempo constante, se dois vértices, digamos s e t, estão na mesma componente conexa:

int UGRAPHconnect( UGraph G, vertex s, vertex t) { 
   return cc[s] == cc[t]; 
}