[prev] 35 [next]

Computing Connected Components (cont)

With this structure, the above tasks become trivial: 

// How many connected subgraphs are there?
int nConnected(Graph g) {
   return g->nC;
}
// Are two vertices in the same connected subgraph?
bool inSameComponent(Graph g, Vertex v, Vertex w) {
   return (g->cc[v] == g->cc[w]);
}

Consider maintenance of such a graph representation:

  • initially, nC = nV   (because no edges)
  • adding an edge may reduce nC
  • removing an edge may increase nC
  • cc[] can simplify path checking
    (ensure v,w are in same component before starting search)
Additional maintenance cost amortised by reduced cost for nConnected() and inSameComponent()