强连通分量：Kosaraju 算法
Strongly Connected Components : Kosaraju algorithm
在 Kosaraju 算法中，我遇到了两种可能的实现：
1) 按原图中顶点的拓扑顺序在反转图中搜索强连通分量
2) 在反转图中按照顶点的拓扑顺序搜索原图中的强连通分量
我想知道，使用颠倒的拓扑顺序的顶点在原始图中搜索强连通分量是错误的。这在内存方面也会更好，因为不需要新的邻接列表。
来源 :1) E-Maxx , 2) CLRS 书籍
术语问题：
你说的是拓扑排序，但当且仅当图是 DAG（有向无环）时，拓扑顺序才存在。如果您只想使用 DAG，那么您已经拥有 SCC（强连通组件），因为每个顶点都是其自身的组件。如果您想在有向图上找到 SCC，则需要将 拓扑排序 更改为 DFS 完成时间 。 CLRS 书仅提到完成时间 f[u]:
- Call DFS(G^T), but in the main loop of DFS, consider the vertices in order of decreasing f[u]...
重新表述您的问题：
Is it wrong to search for strongly connected components in the original graph consider vertices in order of increasing finishing times f[u]?
答案：
对，错了
反例：考虑下图：
其中包含两个组件 C 和 C'。如果您 运行 第一个 DFS（从节点 u 开始），您将按完成时间以升序结束以下两个列表之一：
DFS 列表 1：{v,w',w,u}
DFS 列表 2：{w',v,w,u}
你实际上问的是你是否可以在原始图上从头开始处理这些列表。如果您选择第一个列表，您将通过从节点 v 开始的 DFS 搜索提取组件 C'，然后从节点 w' 开始通过 DFS 搜索提取组件 C。但是，如果您选择第二个列表并从原始图上的节点 w' 开始 DFS，您将只会得到一个组件（整个图），这是错误的。
请注意，Kosaraju 的算法在这两种情况下都有效，因为它从列表的末尾开始（在这两种情况下都是节点 u），并通过 DFS 搜索在反转图上提取组件 C。当我们到达列表中的节点 v 时，稍后将提取组件 C'。
Kosaraju 算法 是一种线性时间算法，用于查找适用于有向图和无向图的强连通分量。为了更容易理解，我们可以在图中说如果任何一组节点构成一个循环是 强连通分量 (SCC)。
如果我们谈论蛮力方法来解决这个问题，我们可以按照以下步骤操作：
- 找到所有对最短路径使用
Floyd Warshall 算法.
- 检查任意两对之间的距离是否为无穷大，即无法到达则它不是 SCC 否则它是 SCC.
如果我们谈论这种方法的复杂性，它将花费立方时间，即 O(v^3)。因此，我们可以使用 Kosaraju 算法 优化此方法，该算法可以 运行 我们的算法在 O(n+m) 时间内完成。使用Kosaraju算法解决强连通分量问题的步骤是：
- 对图执行深度优先搜索(DFS)并将节点推送到堆栈。
- 通过反转图的边找到图的转置。
- 从堆栈中一个接一个地弹出节点，然后在修改后的图上再次执行 DFS。
每个成功的 DFS 将五个 1-SCC 强连接 component.This Kosaraju 算法 在 [=16= 中的工作原理]O(n+m) 时间，其中 n 是图中的节点数，m 是边数。
在 Kosaraju 算法中，我遇到了两种可能的实现：
1) 按原图中顶点的拓扑顺序在反转图中搜索强连通分量
2) 在反转图中按照顶点的拓扑顺序搜索原图中的强连通分量
我想知道，使用颠倒的拓扑顺序的顶点在原始图中搜索强连通分量是错误的。这在内存方面也会更好，因为不需要新的邻接列表。
来源 :1) E-Maxx , 2) CLRS 书籍
术语问题：
你说的是拓扑排序，但当且仅当图是 DAG（有向无环）时，拓扑顺序才存在。如果您只想使用 DAG，那么您已经拥有 SCC（强连通组件），因为每个顶点都是其自身的组件。如果您想在有向图上找到 SCC，则需要将 拓扑排序 更改为 DFS 完成时间 。 CLRS 书仅提到完成时间 f[u]:
- Call DFS(G^T), but in the main loop of DFS, consider the vertices in order of decreasing f[u]...
重新表述您的问题：
Is it wrong to search for strongly connected components in the original graph consider vertices in order of increasing finishing times
f[u]?
答案：
对，错了
反例：考虑下图：
其中包含两个组件 C 和 C'。如果您 运行 第一个 DFS（从节点 u 开始），您将按完成时间以升序结束以下两个列表之一：
DFS 列表 1：{v,w',w,u}
DFS 列表 2：{w',v,w,u}
你实际上问的是你是否可以在原始图上从头开始处理这些列表。如果您选择第一个列表，您将通过从节点 v 开始的 DFS 搜索提取组件 C'，然后从节点 w' 开始通过 DFS 搜索提取组件 C。但是，如果您选择第二个列表并从原始图上的节点 w' 开始 DFS，您将只会得到一个组件（整个图），这是错误的。
请注意，Kosaraju 的算法在这两种情况下都有效，因为它从列表的末尾开始（在这两种情况下都是节点 u），并通过 DFS 搜索在反转图上提取组件 C。当我们到达列表中的节点 v 时，稍后将提取组件 C'。
Kosaraju 算法 是一种线性时间算法，用于查找适用于有向图和无向图的强连通分量。为了更容易理解，我们可以在图中说如果任何一组节点构成一个循环是 强连通分量 (SCC)。 如果我们谈论蛮力方法来解决这个问题，我们可以按照以下步骤操作：
- 找到所有对最短路径使用 Floyd Warshall 算法.
- 检查任意两对之间的距离是否为无穷大，即无法到达则它不是 SCC 否则它是 SCC.
如果我们谈论这种方法的复杂性，它将花费立方时间，即 O(v^3)。因此，我们可以使用 Kosaraju 算法 优化此方法，该算法可以 运行 我们的算法在 O(n+m) 时间内完成。使用Kosaraju算法解决强连通分量问题的步骤是：
- 对图执行深度优先搜索(DFS)并将节点推送到堆栈。
- 通过反转图的边找到图的转置。
- 从堆栈中一个接一个地弹出节点，然后在修改后的图上再次执行 DFS。
每个成功的 DFS 将五个 1-SCC 强连接 component.This Kosaraju 算法 在 [=16= 中的工作原理]O(n+m) 时间，其中 n 是图中的节点数，m 是边数。