Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | 16x 11x 11x 11x 11x 32x 32x 32x 32x 32x 28x 17x 17x 17x 11x 10x 10x 32x 20x 20x 32x 32x 32x 32x 20x 11x 32x 15x 11x | import Graph from '../Graph';
type Entry = {
onStack: boolean;
lowlink: number;
index: number;
};
/**
* @description Tarjan's algorithm for finding the strongly connected components of a graph.
* @description https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
* @description.zh-CN Tarjan 算法用于找到图的强连通子图。
* @param graph
* @returns
*/
const tarjan = <NodeIDType>(graph: Graph<NodeIDType>) => {
let index = 0;
const stack: NodeIDType[] = [];
const visited = new Map<NodeIDType, Entry>(); // node id -> { onStack, lowlink, index }
const results: NodeIDType[][] = [];
function dfs(v: NodeIDType) {
const entry = {
onStack: true,
lowlink: index,
index,
};
visited.set(v, entry);
index += 1;
stack.push(v);
graph.successors(v)?.forEach(function (w) {
// 如果 w 没有被访问过，则继续访问 w
if (!visited.has(w)) {
dfs(w);
const wEntry = visited.get(w);
entry.lowlink = Math.min(entry.lowlink, wEntry!.lowlink);
// 如果 w 在栈顶，则说明 w 和 v 不是强连通的
} else if (visited.get(w)?.onStack) {
const wEntry = visited.get(w);
// 如果 w 在栈中，则说明 w 在当前访问的路径上
entry.lowlink = Math.min(entry.lowlink, wEntry!.index);
}
});
// 如果 v 的 lowlink 不等于 v 的 index，则说明 v 和 v 的 lowlink 不是强连通的
if (entry.lowlink === entry.index) {
const cmpt = [];
let w;
do {
// 将 w 出栈，并将 w 的所有邻接点加入强连通子图
w = stack.pop()!;
const wEntry = visited.get(w)!;
wEntry.onStack = false;
cmpt.push(w);
} while (v !== w);
results.push(cmpt);
}
}
graph.nodes().forEach(function (v) {
if (!visited.has(v)) {
dfs(v);
}
});
return results;
};
export default tarjan;
|