Week 06b: Graph Algorithms 1 (34)

Computing Connected Components (cont)

Consider an application where connectivity is critical

we frequently ask questions of the kind above
but we cannot afford to run components() each time

Add a new fields to the GraphRep structure:

typedef struct GraphRep *Graph;

struct GraphRep {
   ...
   int nC;  // # connected components
   int *cc; // which component each vertex is contained in
   ...      // i.e. array [0..nV-1] of 0..nC-1
}