Connected components of undirected graph

Question

Suppose I have an undirected graph G with vertices v1...vn and edges. Right now it is in adjacency list representation.

For every time moment I have as input some subset of vertices that are "active" at this moment. And I need to find all connected components in this subset of vertices for that time moment.

Right now I've implemented this using union-find data structure like this:

initialize sets for every active vertex so that every vertex has itself as "representative" (also called "parent")

for every active vertex v
   for all neighbours of v in G v_neighbour
      if v_neighbour is active
          union set of v and set of v_neighbour

It should work OK, but I want to know if there is a more optimal approach? And what is the running time of that algorithm? O(N*M)?

Answer 1

The right answer in practice may depend on the rough proportion of vertices that are active. If most vertices are active, I would modify the graph structure by stripping out all links to inactive vertices (trivial in adjacency matrix form, very parallelizable in adjacency list form) and then run a standard weakly-connected-components algorithm (which should be O(V+E)). If the number of active vertices is very small, then mutilating the graph might not be worth the time, and just expanding out from the active vertices as you suggested could be better.

As always, our intuitions about these things should be experimentally checked if performance is a key concern.