这可以使用“ 广度优先搜索” 解决。
这个想法是通过跳到相邻顶点来遍历源顶点中所有可到达的顶点。首先访问源顶点旁边的顶点，然后访问相距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 visitedvar 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 groupfor (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 groupsconsole.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 vertexvar 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 listvar 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);
