CODEWITHSUNDEEP
algorithmgraph-algorithm
Mathejunior
Mathejunior

Reputation: 153

Find all cyclic paths in a directed graph

The title is self explanatory. Here's a solution that I found in the internet that can help do this. Here's the link

I don't understand why not visiting a vertex having weight below the given threshold will solve the problem.

Additionally, I have no idea how to solve this using/not using this.

Upvotes: 3

Views: 1523

Answers (2)

Zoomba
Zoomba

Reputation: 1806

If you want to find cycles in a directed (or even undirected) graph there is an intuitive way to do it:

For each edge (u, v) in the graph
     1. Temporarily ignore the edge (u, v) in step 2
     2. Run an algorithm to find all paths from v to u (using a backtrackig algorithm)
     3. Output the computed paths in step 2 along with the edge (u, v) as cycles in the graph

Note that you will get duplicate cycles this way since a cycle of length k will be found k times.

You can play with this idea to find cycles with specific properties, as well. For example, if you are aiming to find the shortest weighted cycle in the graph instead of finding all cycles. You can use a Dijkstra in step 2, and take the minimum over all the cycles you find. If you wanna finding the cycle with the least number of edges you can use a BFS in step 2.

If you are more struggling with finding all paths in a graph, this question might help you. Although it's for a slightly different problem.

Counting/finding paths with backtracking

Upvotes: 0

Patrick87
Patrick87

Reputation: 28322

Let's restrict this to simple cycles - those which contain no subcycles. For each node in the graph, begin a depth-first search for that node. record each branch of the recursion tree which results in a match. While searching, never cross over nodes already traversed in the branch.

Consider the complete directed graph on n vertices. There are n(n-1) arcs and n! simple cycles of length n. The algorithm above isn't much worse than this at all. Simply constructing a new copy of the answer would take nearly as much time as running the above algorithm to do it, in the worst case at least.

Upvotes: 1

Related Questions