Finding All Connected Components of an Undirected Graph

Question

I have a list of objects (undirected edges) like below:

pairs = [

 pair:["a2", "a5"],
 pair:["a3", "a6"],
 pair:["a4", "a5"],
 pair:["a7", "a9"]

];

I need to find all components (connected nodes) in separate groups. So from given pairs I need to get:

groups = [
  group1: ["a2", "a5", "a4"],
  group2: ["a3", "a6"],
  group3: ["a7", "a9"]
];

I actually read some answers on here and googled this and that's how I learned this is called "finding connected components in a graph" but, could't find any sample code. I use JavaScript on Node.js but any sample with other languages would be very helpful. Thanks.

Answer 1

This can be solved using a Breadth First Search.

The idea is to traverse all reachable vertices from a source vertex, by hopping to adjacent vertices. Vertices right next to the source vertex are first visited, followed by vertices that are 2 hops away, etc.

The code here is not very efficient due to the graph representation used, which is an edge list . To obtain better performance, you might want to use an adjacency list.

Here's some working code in JavaScript. I used node.js to run this:

// Breadth First Search function
// v is the source vertex
// all_pairs is the input array, which contains length 2 arrays
// visited is a dictionary for keeping track of whether a node is visited
var bfs = function(v, all_pairs, visited) {
  var q = [];
  var current_group = [];
  var i, nextVertex, pair;
  var length_all_pairs = all_pairs.length;
  q.push(v);
  while (q.length > 0) {
    v = q.shift();
    if (!visited[v]) {
      visited[v] = true;
      current_group.push(v);
      // go through the input array to find vertices that are
      // directly adjacent to the current vertex, and put them
      // onto the queue
      for (i = 0; i < length_all_pairs; i += 1) {
        pair = all_pairs[i];
        if (pair[0] === v && !visited[pair[1]]) {
          q.push(pair[1]);
        } else if (pair[1] === v && !visited[pair[0]]) {
          q.push(pair[0]);
        }
      }
    }
  }
  // return everything in the current "group"
  return current_group;
};

var pairs = [
  ["a2", "a5"],
  ["a3", "a6"],
  ["a4", "a5"],
  ["a7", "a9"]
];

var groups = [];
var i, k, length, u, v, src, current_pair;
var visited = {};

// main loop - find any unvisited vertex from the input array and
// treat it as the source, then perform a breadth first search from
// it. All vertices visited from this search belong to the same group
for (i = 0, length = pairs.length; i < length; i += 1) {
  current_pair = pairs[i];
  u = current_pair[0];
  v = current_pair[1];
  src = null;
  if (!visited[u]) {
    src = u;
  } else if (!visited[v]) {
    src = v;
  }
  if (src) {
    // there is an unvisited vertex in this pair.
    // perform a breadth first search, and push the resulting
    // group onto the list of all groups
    groups.push(bfs(src, pairs, visited));
  }
}

// show groups
console.log(groups);

UPDATE: I have updated my answer to demonstrate how to convert an edge list to an adjacency list. The code is commented and should illustrate the concept rather well. The Breadth First Search function is modified to make use of an adjacency list, along with another slight modification (regarding marking vertices as visited).

// Converts an edgelist to an adjacency list representation
// In this program, we use a dictionary as an adjacency list,
// where each key is a vertex, and each value is a list of all
// vertices adjacent to that vertex
var convert_edgelist_to_adjlist = function(edgelist) {
  var adjlist = {};
  var i, len, pair, u, v;
  for (i = 0, len = edgelist.length; i < len; i += 1) {
    pair = edgelist[i];
    u = pair[0];
    v = pair[1];
    if (adjlist[u]) {
      // append vertex v to edgelist of vertex u
      adjlist[u].push(v);
    } else {
      // vertex u is not in adjlist, create new adjacency list for it
      adjlist[u] = [v];
    }
    if (adjlist[v]) {
      adjlist[v].push(u);
    } else {
      adjlist[v] = [u];
    }
  }
  return adjlist;
};

// Breadth First Search using adjacency list
var bfs = function(v, adjlist, visited) {
  var q = [];
  var current_group = [];
  var i, len, adjV, nextVertex;
  q.push(v);
  visited[v] = true;
  while (q.length > 0) {
    v = q.shift();
    current_group.push(v);
    // Go through adjacency list of vertex v, and push any unvisited
    // vertex onto the queue.
    // This is more efficient than our earlier approach of going
    // through an edge list.
    adjV = adjlist[v];
    for (i = 0, len = adjV.length; i < len; i += 1) {
      nextVertex = adjV[i];
      if (!visited[nextVertex]) {
        q.push(nextVertex);
        visited[nextVertex] = true;
      }
    }
  }
  return current_group;
};

var pairs = [
  ["a2", "a5"],
  ["a3", "a6"],
  ["a4", "a5"],
  ["a7", "a9"]
];

var groups = [];
var visited = {};
var v;

// this should look like:
// {
//   "a2": ["a5"],
//   "a3": ["a6"],
//   "a4": ["a5"],
//   "a5": ["a2", "a4"],
//   "a6": ["a3"],
//   "a7": ["a9"],
//   "a9": ["a7"]
// }
var adjlist = convert_edgelist_to_adjlist(pairs);

for (v in adjlist) {
  if (adjlist.hasOwnProperty(v) && !visited[v]) {
    groups.push(bfs(v, adjlist, visited));
  }
}

console.log(groups);