我有一个对象列表(无向边),如下所示:
pairs = [
pair:["a2", "a5"],
pair:["a3", "a6"],
pair:["a4", "a5"],
pair:["a7", "a9"]
];
我需要在单独的组中找到所有 组件(连接的节点)。所以从给定的对中我需要得到:
groups = [
group1: ["a2", "a5", "a4"],
group2: ["a3", "a6"],
group3: ["a7", "a9"]
];
我实际上在这里阅读了一些答案并用谷歌搜索了这个,这就是我如何了解到这被称为“在图中查找连接的组件”,但是找不到任何示例代码。我在 Node.js 上使用 JavaScript,但任何其他语言的示例都会非常有帮助。谢谢。
最佳答案
这可以使用广度优先搜索来解决。
这个想法是通过跳到相邻顶点来遍历源顶点的所有可达顶点。首先访问紧邻源顶点的顶点,然后是 2 跳远的顶点,依此类推。
由于使用的是边列表 图形表示,这里的代码效率不是很高。为了获得更好的性能,您可能需要使用邻接列表。
下面是一些可用的 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);
更新:我更新了我的答案以演示如何将边列表转换为邻接列表。该代码已注释,应该可以很好地说明这个概念。广度优先搜索功能被修改为使用邻接表,以及另一个轻微的修改(关于将顶点标记为已访问)。
// 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);
关于javascript - 查找无向图的所有连通分量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21900713/