Menu
I need to find the longest cycle in a directed graph using DFS.
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.
The two digits given in the first line is N and M, each representing the number of nodes and the number of directed edges.
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:
7 9
1 2
2 3
3 1
3 4
4 5
5 1
5 6
6 7
7 2
The answer in this case is 6, since 2>3>4>5>6>7>2.
453
As far as the algorithm, the easy way to solve the problem is to backtrack---start in nodes i=1 to n, and always explore all cycles starting in the particular node i. Once this is done, you eliminate the node i and continue for the rest of the graph, starting in node i+1.
To detect cycle, check for a cycle in individual trees by checking back edges. To detect a back edge, keep track of vertices currently in the recursion stack of function for DFS traversal. If a vertex is reached that is already in the recursion stack, then there is a cycle in the tree.
Efficient Approach: An efficient approach is to use Dynamic Programming and DFS together to find the longest path in the Graph. Let dp[i] be the length of the longest path starting from the node i. Initially all positions of dp will be 0. We can call the DFS function from every node and traverse for all its children.
Depth First Search (DFS) is a systematic way of visiting the nodes of either a directed or an undirected graph. As with breadth first search, DFS has a lot of applications in many problems in Graph Theory. It comprises the main part of many graph algorithms. DFS visits the vertices of a graph in the following manner.
I think that longest elementary cycle (or circuit) is better terminology than longest cycle.
Anyway, this pdf may be helpful: Finding All the Elementary Circuits of a Directed Graph
This one year old stackoverflow question has also many links to related problems and algorithms: Finding all cycles in a directed graph
104
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
