Skip to content

Instantly share code, notes, and snippets.

@kkdd
Last active May 31, 2019 10:11
Show Gist options
  • Save kkdd/6089db7834039c5d2fbc to your computer and use it in GitHub Desktop.
Save kkdd/6089db7834039c5d2fbc to your computer and use it in GitHub Desktop.
グラフの連結成分(JavaScript版) ref: https://qiita.com/kkdd/items/fce83a4fc3081378bc23
var graph = {"0": ["1", "2", "3"], "1": ["2"], "2": [], "3": ["4", "6"], "4": [], "5": ["7"], "6": [], "7": []};
// 0
// / | \
// 1--2 3
// | \
// 4 6
// 5--7
function connected_components(graph) {
var seen = [], push = Array.prototype.push;
function notVisited(n) {return seen.indexOf(n) === -1;}
function traverse(n) {
seen.push(n);
var nodes = [n];
graph[n].forEach(function(m){
if (notVisited(m)) push.apply(nodes, traverse(m)); // recursive, depth-first
});
return nodes;
}
var components = [];
for (var n in graph) {
if (notVisited(n)) components.push(traverse(n));
}
return components;
}
var ccs = connected_components(graph);
for (var i = 0, len = ccs.length; i < len; i++) {print("[", ccs[i], "]");}
$ js connected_components.js
[ 0,1,2,3,4,6 ]
[ 5,7 ]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment