[prev] 32 [next]

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: 

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