こんにちは。
「グラフの連結成分」を求めるコードを JavaScript で書いてみました。
$ js connected_components.js
[[ 0,1,2,3,4,6 ], [ 5,7 ]]
connected_components.js
const graph = {"0": ["1", "2", "3"], "1": ["2"], "2": [], "3": ["4", "6"], "4": [], "5": ["7"], "6": [], "7": []};
// 0
// / | \
// 1--2 3
// | \
// 4 6
// 5--7
console.log(connected_components(graph));
function connected_components(graph) {
const components = [];
for (const n in graph) {
if (!visited(n)) components.push(traverse(n));
}
return components;
function traverse(n) { // recursive, depth-first
const nodes = [n];
for (const m of graph[n]) {
if (!visited(m)) concat_(nodes, traverse(m));
};
return nodes;
}
function concat_(a, b) {
Array.prototype.push.apply(a, b);
}
function visited(n) {
return components.flat().includes(n);
}
}