O(m+n)算法检查有向图是否单边连通
O(m+n) algorithm to check if a directed graph is unilaterally connected
给定一个有向图 G=(V,E) 我如何检查它是否单边连通，即对于任意两对顶点 a 和 b，至少满足以下条件之一：
- 有一条从a到b的路径。
- 有一条从b到a的路径。
想法
想法是使用 SCC（强连通分量）和 Top Sort。这是一个伪算法：
- 首先找到您原始图形的 SCC。在您的每个 SCC 中，都有一条从一个顶点到另一个顶点的路径。
- 将新找到的 SCC 图压缩为新图。这个想法是将所有属于 SCC
1 的节点视为新图的节点 1 等等
- 现在，我们需要 运行 一个 DFS 来检查是否只有一个连通分量。但是我们不能只是 运行 来自任何节点的 DFS，因为这是一个有向图。我们使用 top sort 来查找拓扑顺序，然后 运行 一个 DFS 来检查是否只有一个组件。如果不止一个，那么这个图就不是单边的。
极端案例
如果最初原始图是一个森林（又名断开连接），则它不是单边的。
复杂性
找到 SCCs 需要 2 DFS。
最高排序也需要 1 DFS .
所以，时间复杂度是O(V+E)如你所愿
我对此没有任何正式证据。但这应该有效。如果您有任何困惑，请告诉我。
找到强连通分量，例如 Tarjan's algorithm。 SCC 中的每个节点都可以从任何其他节点到达，因此就它们可以到达的节点和被到达的节点而言，它们是等价的。将每个 SCC 折叠成单个顶点，如果原始图是单边的，则生成的 DAG 将是单边的。
DAG 是单边的，当且仅当它是全序的，即，如果只有一个拓扑顺序。如果有一条从 A 到 B 的路径，那么 A 必须先于 B。如果有一条从 B 到 A 的路径，那么 B 必须先于 A。你不会同时拥有两者，因为图现在是非循环的。如果 A 和 B 之间没有路径，则它们没有顺序，并且该图至少有 2 个拓扑顺序 - 一个是 A 在 B 之前，一个是 B 在 A 之前。
检查总顺序的一种快速方法是使用 Kahn 算法topological sort，并检查以确保在每次迭代时下一个顶点只有一个选择。
Tarjan 的查找 SCC、折叠 SCC 的算法和 Kahn 的拓扑排序算法，全部 运行 时间为 O(V+E)。
给定一个有向图 G=(V,E) 我如何检查它是否单边连通，即对于任意两对顶点 a 和 b，至少满足以下条件之一：
- 有一条从a到b的路径。
- 有一条从b到a的路径。
想法
想法是使用 SCC（强连通分量）和 Top Sort。这是一个伪算法：
- 首先找到您原始图形的 SCC。在您的每个 SCC 中，都有一条从一个顶点到另一个顶点的路径。
- 将新找到的 SCC 图压缩为新图。这个想法是将所有属于 SCC
1的节点视为新图的节点1等等 - 现在，我们需要 运行 一个 DFS 来检查是否只有一个连通分量。但是我们不能只是 运行 来自任何节点的 DFS，因为这是一个有向图。我们使用 top sort 来查找拓扑顺序，然后 运行 一个 DFS 来检查是否只有一个组件。如果不止一个，那么这个图就不是单边的。
极端案例
如果最初原始图是一个森林（又名断开连接），则它不是单边的。
复杂性
找到 SCCs 需要 2 DFS。
最高排序也需要 1 DFS .
所以，时间复杂度是O(V+E)如你所愿
我对此没有任何正式证据。但这应该有效。如果您有任何困惑，请告诉我。
找到强连通分量，例如 Tarjan's algorithm。 SCC 中的每个节点都可以从任何其他节点到达，因此就它们可以到达的节点和被到达的节点而言，它们是等价的。将每个 SCC 折叠成单个顶点，如果原始图是单边的，则生成的 DAG 将是单边的。
DAG 是单边的，当且仅当它是全序的，即，如果只有一个拓扑顺序。如果有一条从 A 到 B 的路径，那么 A 必须先于 B。如果有一条从 B 到 A 的路径，那么 B 必须先于 A。你不会同时拥有两者，因为图现在是非循环的。如果 A 和 B 之间没有路径，则它们没有顺序，并且该图至少有 2 个拓扑顺序 - 一个是 A 在 B 之前，一个是 B 在 A 之前。
检查总顺序的一种快速方法是使用 Kahn 算法topological sort，并检查以确保在每次迭代时下一个顶点只有一个选择。
Tarjan 的查找 SCC、折叠 SCC 的算法和 Kahn 的拓扑排序算法，全部 运行 时间为 O(V+E)。