使用深度优先搜索在有向图中寻找最长的循环

Question

我需要使用DFS在有向图中找到最长的循环。

我曾经看过维基百科上介绍如何解决这个问题的文章，我认为它是通过将节点标记为三种状态之一来处理问题：节点尚未被访问、已完成对节点的搜索，以及节点已被访问但尚未完成访问。

如果有人能与我分享链接，我会非常感激。顺便说一句，它不是Tarjan算法。

以下是我试图解决的问题，如果您想了解的话。

第一行给出的两个数字是N和M，分别表示节点数和有向边数。

从第二行开始，给出M组两个数字A和B，表示节点A和B相连，但只能从A到B遍历节点。

input.txt：

7 9  
1 2  
2 3  
3 1  
3 4  
4 5  
5 1  
5 6  
6 7  
7 2  

在这种情况下，答案是6，因为2>3>4>5>6>7>2。

- John Graveston

---

这不是 NP 完全问题吗？如果你能够在多项式时间内找到最长的环，那么你也可以判断图中是否存在哈密顿回路。 - Karel Petranek

这是NPC问题，但如果你想在DAG中找到最长路径，它是p，总之，你应该说出你做什么，以便别人帮助你。 - Saeed Amiri

你可能在想维基百科上的拓扑排序文章。虽然，那是一个不同的问题... - gte525u

Answer 1

我认为“最长初级循环（或电路）”是比“最长循环”更好的术语。

无论如何，这份PDF可能会有所帮助：在有向图中找到所有初级电路

这个一年前的stackoverflow问题也有许多相关问题和算法的链接：在有向图中找到所有循环

- ypercubeᵀᴹ

---

非常感谢您提供这篇论文，我寻找那种算法已经好几天了。当人们说“这是NP问题，无法解决”时，真的让我很生气。对于小问题，确实有解决方法，而我的问题肯定足够小！ - Adam Kurkiewicz

第一个链接坏掉了 :( - James Mitchell

@JamesMitchell，这篇论文在siam.org上（如果您有访问权限）：http://epubs.siam.org/doi/abs/10.1137/0204007?journalCode=smjcat。我在问题中添加了一个链接，指向一个具有相同论文的github项目。趁还能下载，赶紧去获取吧 ;) - ypercubeᵀᴹ

Answer 2

确实可以证明，你可以在多项式时间内将汉密尔顿回路问题简化为这个问题，因此它最终成为NP完全问题。无论图形是有向的还是无向的。

至于算法，解决问题的简单方法是回溯——从节点i=1到n开始，始终探索以特定节点i开头的所有循环。完成后，删除节点i并继续处理其余部分的图形，从节点i+1开始。您可能需要在DFS中对节点进行染色，以区分您永远不想再次访问的节点和您在此特定通道中沿路径访问的节点。您还可以在节点上放置类似于发现时间的时间戳，但在这种情况下，您需要每次发现节点时写入这些时间，因为大多数节点将被多次发现。上面列出的论文可能会有所帮助，当然还有更多的方法来解决这个问题。

- martinp

Answer 3

我在另一篇帖子中有一个答案，解释了使用Python和networkX在有向图中找到所有循环的简单方法。查找有向图中的所有循环

该解决方案将输出包含有向图所有循环的列表。

您可以使用此输出来查找最长的循环，并如下所示：

import networkx as nx

# Create Directed Graph
G=nx.DiGraph()

# Add a list of nodes:
G.add_nodes_from(["1","2","3","4","5","6","7","9"])

# Add a list of edges:
G.add_edges_from([("7","9"),("1","2"),("2","3"),("3","1"),("3","4"),("4","5"),("5","1"),("5","6"),("6","7"),("7","2")])

#Return a list of cycles described as a list o nodes
all_cycles = list(nx.simple_cycles(G))

#Find longest cycle
answer = []
longest_cycle_len = 0
for cycle in all_cycles:
    cycle_len = len(cycle)
    if cycle_len>longest_cycle_len:
        answer =cycle
        longest_cycle_len = cycle_len

print "Longest Cycle is {} with length {}.".format(answer,longest_cycle_len)

答案：最长循环是['3'，'4'，'5'，'6'，'7'，'2']，长度为6。

如果您觉得这个有趣，请也给原始答案点赞。这是一个旧的讨论，有很多答案，它将帮助推出新的解决方案。

- fernandosjp

---

在构建all_cycles时，应避免调用list。调用它只会浪费内存，因为在迭代时不需要整个列表。 - Michael Mior

Answer 4

这个问题是NP完全问题，目前没有多项式时间算法可用。

你的问题有多大？我是指输入图中有多少节点？

最长路径问题可以归约为汉密尔顿回路问题： http://mathworld.wolfram.com/HamiltonianCycle.html

- orezvani