使用DFS在有向图中找到最长的周期 [英] Finding the longest cycle in a directed graph using DFS

问题描述

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

I need to find the longest cycle in a directed graph using DFS.

我曾经见过这篇Wikipedia文章，描述了这样做的方法，并且我认为它已经接近该问题类似于将节点标记为以下三种状态之一：节点尚未访问，完成搜索节点以及节点已访问但尚未完成访问。

I once saw this Wikipedia article describing the way of doing this, and I think it approached the problem something like marking the node with one of three states: Node not yet visited, Finished searching the node, and Node visited, but not yet finished visiting.

如果有人可以与我分享链接，将不胜感激。顺便说一下，它不是塔里安的算法。

I would be grateful if anyone could share the link with me. By the way, it isn't Tarjan's Algorithm.

下面的问题是我要解决的问题，以防万一您想知道。

The problem below is what I'm trying to solve, in case you'd like to know.

第一行中给出的两位数字是N和M，每个数字代表节点数和有向边数。

The two digits given in the first line is N and M, each representing the number of nodes and the number of directed edges.

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

From the second line is given M sets of two digits A and B, which means that node A and B are connected but you can only traverse the node from A to B.

input.txt：

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。

The answer in this case is 6, since 2>3>4>5>6>7>2.

推荐答案

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

I think that longest elementary cycle (or circuit) is better terminology than longest cycle.

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

Anyway, this pdf may be helpful: Finding All the Elementary Circuits of a Directed Graph

这个有一年历史的stackoverflow问题也与相关问题和算法有很多联系：
在有向图中查找所有循环

This one year old stackoverflow question has also many links to related problems and algorithms: Finding all cycles in a directed graph

这篇关于使用DFS在有向图中找到最长的周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！