15

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

我曾经看到这篇 Wikipedia 文章描述了这样做的方式，我认为它解决了类似用以下三种状态之一标记节点的问题：节点尚未访问，已完成搜索节点，节点已访问，但尚未完成访问.

如果有人可以与我分享链接，我将不胜感激。顺便说一句，这不是 Tarjan 算法。

如果您想知道，下面的问题是我要解决的问题。

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

从第二行开始给出 M 组两个数字 A 和 B，这意味着节点 A 和 B 是连接的，但您只能从 A 遍历节点到 B。

输入.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。

4

4 回答 4

9

我认为最长的基本周期（或电路）是比最长周期更好的术语。

无论如何，这个 pdf 可能会有所帮助：找到有向图的所有基本电路

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

于 2011-01-09T19:47:15.967 回答
4

确实可以证明，您可以在多项式时间内将哈密顿循环简化为这个问题，因此它最终是 NP 完全的。不管图是有向的还是无向的。

就算法而言，解决问题的简单方法是回溯——从节点 i=1 到 n 开始，并始终探索从特定节点 i 开始的所有循环。完成此操作后，您消除节点 i 并继续图表的其余部分，从节点 i+1 开始。您可能想要在 DFS 中进行节点着色之类的操作，以区分您不想再次访问的节点和您在此特定通道中沿路径访问的节点。您可能还想在节点上放置时间戳之类的东西，类似于发现时间，但在这种情况下，您需要在每次发现节点时写入这些时间，因为大多数节点会被多次发现。上面列出的论文可能会有所帮助，并且肯定有更多方法可以做到这一点。

于 2012-05-09T10:00:28.153 回答
0

这个问题是 NP-Complete 并且没有针对它的多项式时间算法。你的问题有多大？我的意思是输入图中将有多少个节点？

最长循环问题简化为哈密顿循环问题： http: //mathworld.wolfram.com/HamiltonianCycle.html

于 2011-10-14T07:23:39.180 回答
0

我有一个答案，解释了在另一篇文章中使用 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。

如果您觉得有趣，也请支持原始答案。这是一个有很多答案的旧讨论，它将有助于提出新的解决方案。

于 2015-12-30T15:34:41.390 回答