引言
Kosaraju 算法用于寻找有向图中的 Strongly Connected Components（SCC，强连通分量）。
理解理论之后，下一步就是把算法真正实现出来。
本文将使用 JavaScript 和 TypeScript 完成完整实现。
整体流程为：
Code
原图 DFS
↓
Finish Order
↓
反转所有边
↓
Transpose Graph DFS
↓
SCCs使用 Adjacency List 表示图
JavaScript
const graph = new Map([
[0, [1]],
[1, [2, 3]],
[2, [0]],
[3, [4]],
[4, [3]]
]);对于稀疏图，邻接表通常比邻接矩阵更节省空间。
第一次 DFS：记录完成顺序
Kosaraju 的关键之一是必须在所有邻居处理完成之后，才把顶点加入 Stack。
JavaScript
function fillOrder(node, graph, visited, stack) {
visited.add(node);
for (const neighbor of graph.get(node) ?? []) {
if (!visited.has(neighbor)) {
fillOrder(neighbor, graph, visited, stack);
}
}
stack.push(node);
}这里保存的是 Finish Order，而不是 Discovery Order。
构造 Transpose Graph
将：
Code
A → B反转为：
Code
B → AJavaScript
function transposeGraph(graph) {
const transpose = new Map();
for (const node of graph.keys()) {
transpose.set(node, []);
}
for (const [node, neighbors] of graph.entries()) {
for (const neighbor of neighbors) {
if (!transpose.has(neighbor)) {
transpose.set(neighbor, []);
}
transpose.get(neighbor).push(node);
}
}
return transpose;
}完整 JavaScript 实现
JavaScript
function kosaraju(graph) {
const visited = new Set();
const stack = [];
function fillOrder(node) {
visited.add(node);
for (const neighbor of graph.get(node) ?? []) {
if (!visited.has(neighbor)) {
fillOrder(neighbor);
}
}
stack.push(node);
}
for (const node of graph.keys()) {
if (!visited.has(node)) {
fillOrder(node);
}
}
const transpose = new Map();
for (const node of graph.keys()) {
transpose.set(node, []);
}
for (const [node, neighbors] of graph.entries()) {
for (const neighbor of neighbors) {
if (!transpose.has(neighbor)) {
transpose.set(neighbor, []);
}
transpose.get(neighbor).push(node);
}
}
visited.clear();
const components = [];
function collect(node, component) {
visited.add(node);
component.push(node);
for (const neighbor of transpose.get(node) ?? []) {
if (!visited.has(neighbor)) {
collect(neighbor, component);
}
}
}
while (stack.length > 0) {
const node = stack.pop();
if (!visited.has(node)) {
const component = [];
collect(node, component);
components.push(component);
}
}
return components;
}TypeScript 泛型版本
TypeScript
type Graph<T> = Map<T, T[]>;这样顶点可以是数字，也可以是字符串，例如服务名称。
TypeScript
function kosaraju<T>(graph: Graph<T>): T[][] {
const visited = new Set<T>();
const stack: T[] = [];
const fillOrder = (node: T): void => {
visited.add(node);
for (const neighbor of graph.get(node) ?? []) {
if (!visited.has(neighbor)) {
fillOrder(neighbor);
}
}
stack.push(node);
};
for (const node of graph.keys()) {
if (!visited.has(node)) {
fillOrder(node);
}
}
const transpose: Graph<T> = new Map();
for (const node of graph.keys()) {
transpose.set(node, []);
}
for (const [node, neighbors] of graph.entries()) {
for (const neighbor of neighbors) {
if (!transpose.has(neighbor)) {
transpose.set(neighbor, []);
}
transpose.get(neighbor)!.push(node);
}
}
visited.clear();
const components: T[][] = [];
const collect = (node: T, component: T[]): void => {
visited.add(node);
component.push(node);
for (const neighbor of transpose.get(node) ?? []) {
if (!visited.has(neighbor)) {
collect(neighbor, component);
}
}
};
while (stack.length > 0) {
const node = stack.pop()!;
if (!visited.has(node)) {
const component: T[] = [];
collect(node, component);
components.push(component);
}
}
return components;
}微服务依赖示例
TypeScript
const services: Graph<string> = new Map([
["user", ["payment"]],
["payment", ["notification"]],
["notification", ["user"]],
["report", ["analytics"]],
["analytics", ["report"]]
]);算法可以找到：
Code
{user, payment, notification}
{report, analytics}这两个 SCC 都代表潜在的循环依赖关系。
时间复杂度
Code
第一次 DFS O(V + E)
构造 Transpose O(V + E)
第二次 DFS O(V + E)因此总复杂度为：
Code
O(V + E)空间复杂度同样保持在线性级别。
JavaScript 的递归深度问题
对于非常深的图，递归 DFS 可能出现：
Code
RangeError: Maximum call stack size exceeded因此在超大规模或 Production 图处理中，通常值得考虑 iterative DFS。
常见错误
实现 Kosaraju 时常见的问题包括：
- 在处理完邻居之前就把顶点加入 Stack。
- 第二次 DFS 前忘记清空
visited。 - 第二次 DFS 仍然使用原图。
- 忽略没有出边的顶点。
- 测试时错误地假设 SCC 内部顺序固定。
总结
Kosaraju 的实现可以浓缩为：
Code
DFS
↓
Finish Order
↓
Transpose
↓
DFS
↓
SCCs使用邻接表时，时间复杂度为 O(V + E)。
TypeScript 的 Generic 和类型安全能力使这种实现很适合扩展到模块依赖、包依赖以及微服务架构分析等实际工程场景。
最值得记住的是：
第一次 DFS 负责确定正确的处理顺序，Transpose Graph 反转组件之间的可达方向，而第二次 DFS 最终揭示每一个 SCC 的边界。