是否存在通过有向图所有顶点的路径？

给定G，一个有向图，是否存在一条经过G中所有顶点的路径（不一定是简单路径）？

我首先需要检查非循环图和强连通图中发生的情况，然后使用强连通分量的图找到一般图的解决方案。

到目前为止，我已经发现，对于强连通图来说，总有一条路径。对于非循环图，如果有多个源，则路径将永远不会存在。另外，如果存在 D out 大于 1 的顶点，则路径将永远不存在。

问题是，我不确定最后一个是否正确，如果错误，我的算法就是错误的。

最后一个假设不成立，例如看一下图表G = (V,E), where E = {(v_i,v_j) | i < j }该图显然是一个 DAG。因此找到最大的强连通分量不会改变图形。另外 - 该图有一个哈密顿路径，但是d_out(v_1) > 1[假设|V| > 3].

然而 - 你走在正确的轨道上。

高级伪代码中的算法：

1. 找到图中的最大强连通分量 - 生成的图是 DAG。
2. Use topological sort on the resulting graph¹.
3. 检查有序排序是否创建哈密顿路径
4. 如果是 - 返回 true，否则返回 false

Claim:

当且仅当 DAG 表示时，存在包含所有顶点的路径 图的 MSCC 具有哈密顿路径

Proof of claim:
<-
if there is a hamiltonian path - then such a path is trivial, for each MSCC - the path goes through all vertices, and then to the out edge that is representing the our edge that was chosen in the hamiltonian path in the MSCC graph.
->
If such a path exists, let it be v0->v1->...vm.
Let's denote V_i the maximal strongly connected component in which v_i lays.
Now, for the path in the original graph v0->v1->...->vm, there is also a path in the MSCC graph²: V_0->V_1->...->V_m.
Note that if V_i appears twice [or more] in the above path - the two occurances are adjacent to each other, otherwise the MSCC found is not maximal because if V_i->V_k->...->V_i is feasible path - then V_i and V_k are not maximal, since you can unite them into one bigger SCC.
Now, for each V_i collapse all occurances of it into one, and you get yourself a path - where each V_i appears at most once [we just showed why], and exactly one [since every v_i was on the original path and we did not remove MSCC's completely - just collapsed them].
Thus - the generated path is a hamiltonian path in the MSCC graph.

建议算法的正确性证明：
由于我们表明 MSCC 图中的哈密顿路径存在当且仅当原始图中存在所请求的路径时 - 那么：
->
算法返回 true -> 算法在 DAG 中找到哈密顿路径 -> Dag 中存在哈密顿路径 [脚注 1] -> 存在原始图中所要求的路径。
<-
算法返回 false -> 算法在 DAG 中未找到哈密尔顿路径 -> DAG 中没有哈密尔顿路径 [脚注 1] -> 原始路径中不存在所请求的路径。

Q.E.D.

1：在 DAG 中，如果存在哈密顿路径，则存在唯一的拓扑排序，如果存在哈密顿路径 - 就是拓扑排序中顶点的顺序。因此，在 DAG 中找到哈密顿路径很容易。
2：实际上，这是一点修改，V_i->V_i并不是 MSCC 图表上真正的边缘，但现在我们将其表示为边缘。