# Tarjan 强连通分量 / 桥 / 关节点分解与拓扑排序器

输入边列表（a b / a -> b，可带权重）或邻接表（a: b c）：Tarjan 1972 迭代算法与 Kosaraju 双通道互相验证地分解强连通分量；输出关节点与桥、缩点 DAG 及其 Kahn 拓扑序、环检测报告（含环上节点数与自环），以及深度受限的 BFS/DFS 遍历深度表。

> 标准页面: https://elysiatools.com/zh/tools/tarjan-scc-tarjan-bridge-and-strongly-connected-components-topological-order-graph-decomposer

- **分类:** Development

- **关键词:** Tarjan, 强连通分量, Kosaraju, 关节点, 桥, 缩点, 拓扑排序, 环检测, 图算法

## 概述

Tarjan SCC 用显式栈的迭代实现（disc/low 数组，出栈收集分量）；Kosaraju 先按完成时间迭代排序、再在反图上收集，两算法结果必须逐分量一致（算法互证）。桥与关节点在无向视图上以 low-link 判定：low[v] > disc[u] ⟹ 桥；根节点子树数 ≥ 2 或 low[v] ≥ disc[u] ⟹ 关节点。缩点图取各分量代表节点建 DAG，Kahn 入度法给出拓扑序；原图存在完整拓扑序当且仅当无环（环上节点数按「SCC 尺寸 > 1 ∪ 自环」统计）。BFS 分层推进、DFS 显式栈记录发现深度，均受 maxDepth 限制。复杂度均为 O(V+E)。

## 输入项

- **图（边列表或邻接表，每行一条）** (textarea): a -> b b -> c c -> a d -> c
- **有向图** (checkbox)
- **遍历起点** (text): a
- **最大遍历深度** (number): 4

## 适用场景

- 分析软件包或微服务调用关系中的循环依赖并计算安全拓扑加载顺序时。
- 排查网络拓扑或关键依赖图中的单点故障（割点）与关键链路（桥）时。
- 学习或验证图论算法，需要对 Tarjan 与 Kosaraju 强连通分量结果进行交叉对比时。

## 工作原理

- 解析文本输入的边列表（如 a -> b）或邻接表（如 a: b c），建立图的有向或无向邻接关系。
- 通过显式栈迭代执行 Tarjan 算法与 Kosaraju 算法，计算 disc 与 low 数组以提取强连通分量，并比对验证两算法结果一致性。
- 基于无向视图识别满足 low\[v\] > disc\[u\] 的桥以及割点，随后将各 SCC 缩点构建 DAG 并应用 Kahn 算法推导拓扑序。
- 依据指定的遍历起点与最大深度限制，生成深度受限的分层 BFS 队列与 DFS 栈遍历结果。

## 使用案例

- 微服务架构治理：检测服务间的循环调用依赖，提取最小环集合以完成解耦。
- 构建系统任务调度：分析编译依赖图，通过缩点 DAG 与拓扑排序生成并行构建阶段。
- 网络通信韧性评估：定位拓扑中的关键路由器（割点）与骨干链路（桥），识别单点故障风险。

## 常见问题

### 本工具支持哪些图输入格式？

支持每行一条的边列表（如 `a -> b`、`a b`，可带权重）以及邻接表格式（如 `a: b c`）。

### 为什么同时运行 Tarjan 和 Kosaraju 两个算法？

两者分别采用单遍栈遍历与正反图双遍遍历，工具通过双通道互相验证，确保强连通分量分解结果的准确性。

### 原图包含环时如何输出拓扑排序？

原图若有环则无法直接全排序，工具会将强连通分量缩点生成无环有向图（DAG），并给出缩点图的 Kahn 拓扑排序。

### 关节点和桥的判定基于有向图还是无向图？

关节点（割点）与桥的连通性分析均基于图的无向视图进行 Low-Link 深度优先搜索判定。

### 最大遍历深度参数起什么作用？

该参数用于限制从指定起点出发的 BFS 与 DFS 搜索层级，防止在大图遍历时产生过深输出。

## 相关工具

- [Cron 表达式可视化器](https://elysiatools.com/zh/tools/cron-expression-visualizer): 解析 cron 调度，校验标准 cron 或 Quartz 语法，并用时间轴和分组日历展示未来执行时间
- [Tailwind 色板同步器](https://elysiatools.com/zh/tools/tailwind-color-palette-sync): 输入一组 HEX,选择命名规则(色阶 50–950 / 单名 / 对象嵌套),自动生成 tailwind.config.ts 的 theme.extend.colors 片段,每个色阶同时给出 WCAG AA/AAA 对比等级,可选暗色模式。
- [Cron 表达式解释器](https://elysiatools.com/zh/tools/cron-expression-explainer): 解析 5 段 / 6 段 / Quartz cron 表达式为自然语言调度描述，按字段拆解，并按任意 IANA 时区列出接下来 N 次执行时间，附带 AI 生成的本地化自然语言解释
- [定时任务模拟器](https://elysiatools.com/zh/tools/cron-job-simulator): 模拟一个或两个 5 段式 Cron 表达式的未来执行时间，标出重叠点并提示过密调度。
- [API 契约变异测试器](https://elysiatools.com/zh/tools/api-contract-mutation-tester): 对 OpenAPI 请求字段做语义变异，并可发送到真实后端以检查防御性校验覆盖率
- [CSV 畸形行外科医生](https://elysiatools.com/zh/tools/csv-malformed-row-surgeon): 逐行外科手术式修复畸形 CSV 行：未转义（游离）引号、混合分隔符（同一文件中制表符/分号/逗号混用）、带 BOM 的表头、CRLF/CR 换行符与多余空行。外科医生采用容错解析，以红绿逐行 diff 显示每一处改动（前 → 后，并标注修复原因），列出未改动的行，并输出清洗后的 CSV。可选 AI 修复会在确定性修复后复查可疑行。它补足 CSV 校验器（仅报告问题）——真正修复受损行。
- [OAuth 2.0 / OIDC 授权码 + PKCE 流程可视化](https://elysiatools.com/zh/tools/oauth-oidc-authorization-code-pkce-flow-visualizer): 端到端模拟带 PKCE 的授权码流程：verifier/challenge 生成、授权 URL、令牌交换、ID Token 校验清单与拦截攻击演示。
- [响应式 Picture / srcset 艺术方向构建器](https://elysiatools.com/zh/tools/responsive-picture-srcset-art-direction-builder): 生成完整的 艺术方向标记：按断点的 、1x/2x 密度候选或 {w} 模板宽度描述符、可选 AVIF/WebP 格式层、sizes 处理、防 CLS 的 width/height，同时输出 HTML 与 JSX 两种方言并附基于规范的 lint 提示。

## 示例

- [无版权FLAC音频样本](https://elysiatools.com/zh/samples/flac-samples): 用于测试与开发的 FLAC 无损音频样本集合，包含自然声音与冥想音乐
- [无版权WAV音频样本](https://elysiatools.com/zh/samples/wav-samples): 用于测试与开发的未压缩 WAV 音频样本集合，包含自然声音与冥想音乐
- [Android Java 图像处理示例](https://elysiatools.com/zh/samples/android-image-processing-java): Android Java 图像处理示例，包括图像读取保存、缩放和格式转换
- [Android Kotlin 图像处理示例](https://elysiatools.com/zh/samples/android-image-processing-kotlin): Android Kotlin 图像处理示例，包括图像读取保存、缩放和格式转换