TL;DR: Kosaraju 算法使用以下方法在有向图中查找强连通分量两次深度优先搜索。首先通过减少完成时间来记录顶点，转置每条边，然后按顺序探索转置图。存储转置时，运行时间为 O(V + E)，辅助存储为 O(V + E)。
Kosaraju 的算法：强连通分量指南
通过直觉、步骤、复杂性、伪代码、示例、常见错误和面试练习来学习 Kosaraju 的强连通分量算法。
尝试 YesToTheOfferKosaraju的算法是什么？
Kosaraju 的算法将有向图划分为强连接组件，或 SCC。在一个 SCC 内，每个顶点都可以到达其他每个顶点。将每个 SCC 收缩为一个节点会生成一个有向非循环图，这使得组件可用于依赖性分析、程序图、可达性和图压缩。
该算法使用深度优先搜索的结构特性。原始图表的完成时间确定了探索转置图表的安全顺序。反转每条边会交换组件之间的源和汇关系，因此当以正确的顺序处理顶点时，一次搜索不会泄漏到未分配的组件中。
两遍算法如何工作？
- 创建一个已访问集和一个空的完成顺序列表。
- 从原始图中每个未访问的顶点运行深度优先搜索。
- 在每个顶点的所有传出邻居完成后追加每个顶点。
- 通过反转每个有向边来构建转置。
- 清除访问集。
- 以相反的完成顺序处理顶点。
- 转置图中的每一棵 DFS 树都是一个强连通分量。
当第一个 DFS 调用返回时，您可以将顶点存储在堆栈上。弹出堆栈自然会减少完成时间。该图可能是断开连接的，因此两个外部循环必须考虑每个顶点，而不是仅从顶点零开始。
为什么冲销完成订单会发现SCC？
想象一下将每个 SCC 压缩到单个节点中。所得的凝结图没有有向循环。在第一个 DFS 中，具有最新相关完成时间的组件的行为类似于此压缩结构中的源。转置图之后，该组件的行为就像一个接收器，因此从那里开始的 DFS 仍保留在其中。
删除该组件会为下一个未分配的组件显示相同的参数。这是面试官通常想要的证明想法：完成顺序可以安全地选择组件，并且转置可以防止第二遍跨越错误的传出边界。您不需要复制冗长的正式证明，但您应该解释这两个角色。
时间和空间复杂度是多少？
每个深度优先搜索通道都会访问每个顶点并检查每个边一次，并且构建转置也需要线性时间。因此总时间为 O(V + E)。对于图和转置的邻接列表，存储是 O(V + E)，加上访问状态、完成顺序和递归或显式堆栈的 O(V)。
| 相 | 时间 | 额外目的 |
|---|---|---|
| 第一个 DFS | O(V + E) | 记录完成订单 |
| 转置 | O(V + E) | 反转边缘方向 |
| 第二次 DFS | O(V + E) | 收集组件 |
| 总计 | O(V + E) | 图形表示中的线性 |
对于非常深的图，递归 DFS 可能会超出语言的调用堆栈限制。提及迭代堆栈显示了生产意识，而不改变渐近界限。
面试时你应该知道哪些伪代码？
完成顺序 = []
访问过=设置（）
对于图中的顶点：
如果顶点不在访问中：
dfs_finish（顶点，图，访问过，完成顺序）
转置=reverse_all_edges(图)
访问过.clear()
组件 = []
对于反向顶点（finish_order）：
如果顶点不在访问中：
组件 = []
dfs_collect（顶点，转置，访问过，组件）
组件.append(组件)
在“dfs_finish”中，在访问邻居后附加顶点。在“dfs_collect”中，在发现顶点时添加该顶点。将这两项职责分开；在第一遍中使用预序是一个常见的错误。
哪些错误通常会破坏 Kosaraju 的实现？
最常见的错误是记录发现顺序而不是完成顺序、忘记反转第二遍的顺序、仅反转某些边、重用已访问状态而不清除它以及跳过孤立或断开连接的顶点。另一个错误是将无向图视为 SCC 具有相同的意义；连接组件是更简单的概念。
测试单个顶点、孤立顶点、一个有向循环、单向链、由一条边连接的两个循环、自循环和断开连接的图。验证分区而不是依赖组件输出顺序，因为不同的有效 DFS 遍历顺序可能会以不同的方式列出组件或顶点。
Kosaraju 与 Tarjan 的算法相比如何？
两种算法都可以在 O(V + E) 中找到 SCC。 Kosaraju 使用两次 DFS 遍历，通常存储转置图，这可以使推理和实现变得简单。 Tarjan 使用一个带有发现索引、低链接值和堆栈的 DFS；它避免了显式转置，但有更多状态需要正确维护。
在面试中，选择您可以可靠解释和实现的算法，除非有限制。如果面试官要求通过一次或不换位，Tarjan 可能更适合。如果优先考虑清晰性和直接证据，Kosaraju 通常是一个很好的选择。
AI如何支持图算法负责任的实践？
AI 可以生成小型反例、跟踪 DFS 状态、比较实现并质疑复杂性解释。编码帮助可以帮助定位排序或访问状态错误，而抄本审查可以显示您是否清楚地解释了证明想法。
始终自己绘制并跟踪至少一张图表、运行测试并验证生成的声明。遵守评估规则，不使用禁止的协助。 YesToTheOffer 支持编码准备、允许的实时推理、私人笔记和面试后审查。
常见问题
FAQ
Kosaraju的算法是用来做什么的？
Kosaraju 的算法在有向图中查找强连通分量。 SCC 有助于简化可达性和依赖结构，因为每个组件都可以收缩到一个节点中，从而生成有向非循环凝结图。
为什么Kosaraju的算法需要两次DFS遍历？
第一遍计算完成时间顺序，以确定接下来可以安全探索哪个组件。第二遍在转置图上运行，其中反转的边防止搜索逃逸到不同的未分配组件中。
Kosaraju算法的复杂度是多少？
时间复杂度为 O(V + E)：两个 DFS 遍历和边反转在邻接表图中都是线性的。原始图和转置图的存储邻接列表使用 O(V + E) 空间，以及附加的 O(V) 遍历状态。
组件输出顺序重要吗？
通常没有。不同的邻接顺序可以改变 DFS 遍历以及顶点或组件的顺序，同时生成相同的有效分区。测试应该将组件成员资格作为集合进行比较，除非问题明确需要特定的排序。
Tarjan的算法比Kosaraju的算法好吗？
两者都不是普遍更好。两者的运行时间都是 O(V + E)。 Tarjan 使用一个 DFS，没有显式转置，但保持低链接状态； Kosaraju 使用两个概念上简单的通道并通常存储反转图。根据约束和实施可靠性进行选择。
将练习变成可重复的系统
制定基于证据的练习计划，在允许的情况下使用负责任的支持，并在对话新鲜时进行审查。
将练习变成可重复的系统
用您自己的证据进行准备，并在更清晰的背景下审查每个答案。
尝试 YesToTheOffer