枚举有向无环图中的所有路径 [英] Enumerating all paths in a directed acyclic graph

问题描述

有没有任何标准算法可以找到有向的一个循环图中的所有可能的路径。
如果不是，我如何在BFS / Dijkstra /任何其他算法中更改DAG中的所有路径 p>在指数中的任何图中找到所有可能的路径。它可以通过使用Backtracking来解决。
对于DAG，我们可以使用深度优先搜索（DFS）。
在DFS代码中，从任意节点开始，转到极端死胡同路径，并使用某个数组或列表记下该路径中访问的所有节点。一旦找到死胡同，打印包含访问节点的数组，并弹出最后存储的节点，并从第（n-1）个节点的另一路径开始。如果第（n-1）个节点的所有路径都用尽，则从列表中弹出该节点并从（n-2）节点开始。这样做，直到你到达所有的死角，并达到第一个节点。
所有打印路径都是给定DAG中的路径。

您可以检查代码 http://pastebin.com/p6ciRJCU

Is there any standard algorithm that finds all possible paths in a directed a-cyclic graph. If not, how can i make changes in BFS/Dijkstra/any other algorithm to enumerate all paths in a DAG

解决方案

Finding all the possible paths in any graph in Exponential. It can be solved by using Backtracking. For DAG's we can do it using Depth first search(DFS). In DFS code, Start at any node, Go to the extreme dead end path and note down all the nodes visited in that path using some array or list. As soon as you find a dead end print the array containing the visited nodes and pop the last stored node and start in the other path of the (n-1)th node. If all the paths of the (n-1)th node are exhausted pop that node from list and start at (n-2)node. Do this untill you reach all the dead ends and reach the first node. All the Printed paths are the Paths in the given DAG.

You can check the code http://pastebin.com/p6ciRJCU

这篇关于枚举有向无环图中的所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！