我该如何做这个图遍历？

Question

我有一个定向循环图，由节点a，b，c，d，e，f g组成，其中节点连接到每个其他节点。边缘可以是单向的或双向的。我需要打印出这样的有效命令，例如。 f-> a-> c-> b-> e-> d-> g，这样我就可以从起始节点到达末端节点。请注意，所有节点必须出现在输出列表中。 另请注意，图中可能有周期。

我想出了： 基本上首先我们可以尝试找到一个开始节点。如果有一个节点使得它没有传入边缘（最多可能有一个这样的节点）。我可能会找到一个开始节点或者可能不会。另外我会做一些预处理来找到节点的总数（让我们称它为n）。现在，我将从启动节点标记节点开始创建一个DFS，并在访问它们时计算我访问的节点数量。如果我可以通过这种方法到达n个节点。我做完。如果我击中了一个节点，而这个节点没有到任何未访问节点的传出边缘，那么我已经遇到了一个死路，我只会将该节点再次标记为未访问，减少指针并转到其前一节点以尝试不同的路由。

这是我找到起始节点的情况。如果我没有找到一个起始节点，我只需要在各个节点上尝试。

我不知道我是否接近解决方案。任何人都可以在这方面帮助我吗？

Answer 1

在我看来，如果没有进入的边缘节点，这意味着该节点是开始节点。您可以使用此开始节点遍历图形。如果这个起始节点不能访问所有n个节点，那么就没有解决方案（正如你所说的，所有节点都必须出现在输出列表中）。这是因为如果你从其他一些节点开始，你将无法到达这个开始节点。

Answer 2

与解决方案的问题是，如果你进入一个循环，你不知道是否以及何时退出。

在这些条件，DFS搜索可以很容易地成为非多项式的任务！

让我为您的问题介绍一个多项式算法。 看起来很复杂我希望有简化的空间。

这里我建议的溶液

1）对于每个节点构造它可以达到（如果能达到b和c的节点的表; b可以达到d; C可达到Ë;一个可达到b，c，d，即使强硬也没有一条通过它们的路径）。

如果没有节点可以到达所有你做其他的人：有没有你要找的路径。

2）查找循环。这很简单：如果一个节点可以到达它自己，就有一个循环。这应该是前一点建立表格的一部分。

一旦找到一个循环，就可以将它（及其节点）缩小为代表节点，其代表节点的输入（输出）连接是循环中节点的输入（输出）连接的并集。

你不断减少循环，直到你不能再做。

3）此时如果只剩下一个非循环图，如果有连接的所有节点的路径，存在连接到所有的单个节点，并从它开始可以执行深度优先搜索。

4） 通过用从循环入口点到出口点的循环替换代表性节点的遍历来记录路径。