我有一个由节点 a、b、c、d、e、fg 组成的有向循环图，其中任何一个节点都连接到每个其他节点。边缘可以是单向的或双向的。我需要打印出这样的有效订单，例如。f->a->c->b->e->d->g 这样我就可以从开始节点到达结束节点。请注意，所有节点都必须出现在输出列表中。另请注意，图中可能存在循环。
我想出什么：基本上首先我们可以尝试找到一个起始节点。如果存在一个没有传入边的节点（最多可能有一个这样的节点）。我可能会找到一个起始节点，也可能不会。另外我会做一些预处理来找到节点的总数（我们称之为n）。现在我将从开始节点开始一个 DFS，当我到达它们时将节点标记为已访问并计算我访问了多少个节点。如果我可以通过这种方法到达 n 个节点。我做完。如果我点击一个节点，从该节点到任何未访问的节点都没有出边，我已经走到了死胡同，我将再次将该节点标记为未访问，减少指针并转到其前一个节点以尝试不同的路线.
当我找到一个起始节点时就是这种情况。如果我没有找到起始节点，我将不得不尝试使用各种节点。
我不知道我是否接近解决方案。任何人都可以在这方面帮助我吗？
在我看来，如果一个节点没有传入边，这意味着该节点是一个起始节点。您可以使用此起始节点遍历图形。如果这个起始节点不能访问所有n个节点，那么就没有解决方案（正如你所说的，所有节点都必须存在于输出列表中。）。这是因为如果您从其他一些节点开始，您将无法到达该起始节点。
您的解决方案的问题是，如果您进入一个循环，您不知道是否以及何时退出。
在这些条件下进行 DFS 搜索很容易变成非多项式任务！
让我为您的问题介绍一个多项式算法。它看起来很复杂，我希望有简化的空间。
这是我建议的解决方案
1) 对于每个节点，构建它可以到达的节点表（如果 a 可以到达 b 和 c；b 可以到达 d；c 可以到达 e；a 可以到达 b,c,d,e 甚至很难有一个pathfrom a 穿过所有这些）。
如果没有节点可以到达所有其他节点，那么您就完成了：没有您正在寻找的路径。
2) 查找循环。这很简单：如果一个节点可以到达自己，那么就有一个循环。这应该是上一点表构造的一部分。
找到一个循环后，您可以将其（及其节点）缩小到代表节点，其输入（输出）连接是循环中节点的输入（输出）连接的联合。
你不断减少循环，直到你不能再做任何事情。
3）此时你留下了一个无环图，如果有一条连接所有节点的路径，则有一个连接到所有节点的单个节点，你可以从它开始执行深度优先搜索。
4) 通过用从循环的入口点到出口点的循环替换代表节点的遍历来记下路径。