我想在有向图中找到所有周期 . 从一个节点开始深度优先搜索将找到一些周期（找到后边缘） . 因此，我将dfs应用于图中的所有节点（即，每次根是不同的节点） . 我能够使用它来获得所有循环（通过消除重复的循环） . 但是，我不确定这是否适用于所有图表以及这是否是正确的方法 . 任何人都可以建议我这是否适用于所有情况 .
谢谢
如果您已断开节点（图形未连接），则必须遍历每个节点的图形 . 如果您使用DFS或BFS并不重要，因为您没有在找到特定节点时停止遍历 .
我会保留一个全局的VisitedNodes列表，因此您不必从已访问过的节点执行完全遍历，而不是通常的“Per-Path”祖先列表以避免循环 .
答案是 NO ！因为在所有节点上运行DFS表示多项式时间算法 . 并且没有多项式时间算法来查找有向图中的所有周期 .
考虑这种情况，假设您有一个包含n个节点的完整图形（每个节点指向所有其余节点），则此n个节点的每个非空子集指示一个周期 . 这些子集有2 ^ n -1个数，因此无法在多项式时间内找到指数个周期 .
2 回答
如果您已断开节点（图形未连接），则必须遍历每个节点的图形 . 如果您使用DFS或BFS并不重要，因为您没有在找到特定节点时停止遍历 .
我会保留一个全局的VisitedNodes列表，因此您不必从已访问过的节点执行完全遍历，而不是通常的“Per-Path”祖先列表以避免循环 .
答案是 NO ！因为在所有节点上运行DFS表示多项式时间算法 . 并且没有多项式时间算法来查找有向图中的所有周期 .
考虑这种情况，假设您有一个包含n个节点的完整图形（每个节点指向所有其余节点），则此n个节点的每个非空子集指示一个周期 . 这些子集有2 ^ n -1个数，因此无法在多项式时间内找到指数个周期 .