javascript 查找无向图的所有连通分量
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/21900713/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Finding All Connected Components of an Undirected Graph
提问by user3211198
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 allcomponents (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.
我实际上在这里阅读了一些答案并用谷歌搜索了这个，这就是我了解到这被称为“在图中查找连接组件”的方式，但是，找不到任何示例代码。我在 Node.js 上使用 JavaScript，但任何其他语言的示例都会非常有帮助。谢谢。
回答by yanhan
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.
这个想法是通过跳跃到相邻顶点来遍历从源顶点开始的所有可达顶点。首先访问源顶点旁边的顶点，然后是 2 跳以外的顶点，依此类推。
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.jsto run this:
这是 JavaScript 中的一些工作代码。我曾经node.js运行过这个：
// 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);
回答by Boris Strandjev
The task you want to solve is best sovled with the algorithm of Disjoint Set Forest.
您要解决的任务最好使用Disjoint Set Forest算法解决。
Basically it is meant to solve exactly the problem you describe in optimal manner.
基本上，它旨在以最佳方式准确解决您描述的问题。
- assign every vertex the set of vertices in which it belong. Let us denote it as
root(v). Every such set will be considered as planted tree throughout the whole algorithm. Thus we will associate theroot(v)with the root of the tree. So let's assumeroot(v)returns a vertex index. - The algorithm will go easiest if you keep throughout the algorithm one auxiliary array - the parent vertex of each vertex in its planted tree. If no such vertex exists we will store -1 instead to denote that. Thus you start the algorithm with
parent[v] = -1for eachvas all vertices are initially in their own trees and you have no parents - We will also need one additional array that stores something that is called the rank of a vertex. It is basically equal to the depth of the subtree having the vertex as root. You need not worry too much about it. The array is used for performance optimizations. Lets name it
rank. We initialize all ranks to 1s - You start processing the edges one by one and each edge might possibly trigger merge of trees. That is the interesting part in which you can optimise.
- 为每个顶点分配它所属的顶点集。让我们将其表示为
root(v)。在整个算法中，每个这样的集合都将被视为种植的树。因此，我们将把 与root(v)树的根联系起来。所以让我们假设root(v)返回一个顶点索引。 - 如果您在整个算法中保持一个辅助数组 - 其种植树中每个顶点的父顶点，则该算法将变得最简单。如果不存在这样的顶点，我们将存储 -1 来表示。因此，您开始算法时使用
parent[v] = -1for eachv因为所有顶点最初都在它们自己的树中并且您没有父母 - 我们还需要一个额外的数组来存储称为顶点秩的东西。它基本上等于以顶点为根的子树的深度。你不必太担心。该数组用于性能优化。让我们命名吧
rank。我们将所有等级初始化为 1s - 您开始一条一条地处理边，每条边都可能触发树的合并。这是您可以优化的有趣部分。
Here is a pseudo code:
这是一个伪代码：
parent[v] = -1 for v in Vertices
rank[v] = 1 for v in Vertices
root (v):
processed = []
while parent[v] != -1
processed << v
v = parent[v]
for vertex : processed
parent = v // optimisation: here we move the assoc. trees to be directly connected the root
return v
join (v1, v2):
if rank[v1] < rank[v2]:
parent[v1] = v2
if rank[v1] > rank[v2]:
parent[v2] = v1
parent[v2] = v1
rank[v1]++
merge_trees (v1, v2)
root1 = root(v1)
root2 = root(v2)
if root1 == root2:
// already in same tree nothing else to be done here
return true
else
// join trees
join (v1, v2)
return false
main:
numberTrees = size(Vertives)
for edge: edges
if merge_trees(edge.begin, edge.end):
numberTrees--
print numberTrees // this is the number you are interested in.
NOTEIf you are not intereseted too much in performace you can omit the rank thing. Without it your algorithm might run slower, but maybe it will be easier for you to understand and maintain. In this scenario you can joinvertices in any direction. I should warn you that then there will exist scenarios that will trigger your algorithm to run slower.
注意如果您对性能不太感兴趣，则可以省略排名。没有它，您的算法可能运行得更慢，但也许您会更容易理解和维护。在这种情况下，您可以join在任何方向上创建顶点。我应该警告你，然后会有一些场景会触发你的算法运行得更慢。
回答by Goodwine
You want to do Graph Traversal
你想做图遍历
In your specificexample, you have no # of nodes, and it may even be difficult to traverse the graph so first we'll get a "graph"
在您的具体示例中，您没有节点数量，甚至可能难以遍历图形，因此首先我们将获得一个“图形”
// It will return an object like Vertices{node: EdgesTo{node,node}, node:...}
function toGraph(arr) {
var graph = {}; // this will hold the node "IDs"
for (var i = 0; i < arr.length; i++) {
// "create node" if the it's not added in the graph yet
graph[arr[i][0]] = graph[arr[i][0]] || {};
graph[arr[i][1]] = graph[arr[i][1]] || {};
// add bidirectional "edges" to the "vertices"
// Yes, we set the value to null, but what's important is to add the key.
graph[arr[i][0]][arr[i][1]] = null;
graph[arr[i][1]][arr[i][0]] = null;
}
return graph;
}
Then it is very easy to traverse the graph using any method that you choose (DFS, BFS)
I will make an example using DFS:
我将使用 DFS 举一个例子：
// to be called after getting the result from toGraph(arr)
function getSubGraphs(graph) {
var subGraphs = []; // array of connected vertices
var visited = {};
for (var i in graph) { // for every node...
var subGraph = dfs(graph, i, visited); // ... we call dfs
if (subGraph != null) // if vertex is not added yet in another graph
subGraphs.push(subGraph);
}
return subGraphs;
}
// it will return an array of all connected nodes in a subgraph
function dfs(graph, node, visited) {
if (visited[node]) return null; // node is already visited, get out of here.
var subGraph = [];
visited[node] = true;
subGraph.push(node);
for (var i in graph[node]) {
var result = dfs(graph, i, visited);
if (result == null) continue;
subGraph = subGraph.concat(result);
}
return subGraph;
}
And you would end up calling it like getSubGraphs(toGraph(myArray));and do whatever you need with that.
你最终会这样称呼它getSubGraphs(toGraph(myArray));并做任何你需要的事情。
