How to find all cycles containing some vertex in a directed graph?

Question

In a directed graph, what the algorithm can find out all cycles that contain a specific vertex v?

possible duplicate of [Finding all cycles in graph](http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph) — Ilmari Karonen, Dec 15 '13 at 03:39

score 1 · Accepted Answer · answered Dec 15 '13 at 09:01

1

Tarjan's algorithm for strongly connected components will give you the SCC, to which that specific vertex belongs. Now you can run a backtracking algorithm on the SCC to find all the simple cycles, which start and end on v.

answered Dec 15 '13 at 09:01

chill

16,470
2
40
44

How to find all cycles containing some vertex in a directed graph?

1 Answers1