寻找无向图的所有连接组件 [英] Finding All Connected Components of an Undirected Graph

问题描述

我有对象（无向边）列表如下图所示：

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"]
];

其实我读这里的一些答案，一派这一点，这就是我了解到这就是所谓的发现连接的部件在图形，但，便无法找到任何样品code 。我使用JavaScript对Node.js的，但与其他语言的任何样品将是非常有益的。谢谢。

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.

推荐答案

这可以通过使用解决的广度优先搜索

This can be solved using a Breadth First Search.

我们的想法是遍历所有可达的顶点从源顶点，通过跳跃至相邻顶点。顶点旁边的源点是第一次访问，其次是顶点2跳走，等。

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.

在code在这里是不是很有效，由于图形重新presentation使用，这是一个边列表。为了获得更好的性能，你可能想使用的邻接表

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.

下面是一些工作code在JavaScript中。我用的node.js 来运行这个：

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);

更新：我已经更新了我的答案来演示如何边列表转换为邻接表。在code被注释掉，并应说明该概念相当不错。广度优先搜索功能被修改为使用邻接表，连同（关于标记顶点访问）另一种轻微的修改。

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);

这篇关于寻找无向图的所有连接组件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！