2

I have a directed multigraph with no self-loops:

Multigraph

What's the most efficient way to mark nodes 1, 2 and 3 as being members of a cycle?

My first thought would be to

  1. Perform a depth-first search starting from an arbitrary node
  2. Push all nodes I've seen in a given branch into a "seen" array. Also, mark each node as "checked".
  3. For each new node, check if any of its children are in the seen array
  4. If it is, mark each node in the array between the seen node and its previous occurrence as seen
  5. While traveling down the DFS, make sure to skip any children who have been seen
  6. Repeat 1-5 with the next node that hasn't been marked as "checked" yet (since I may have disconnected regions of the graph)

This seems like it might work, but wonder if it's the most efficient way, give that I've got to maintain an array of "seen" nodes, and, since this has to be called recursively, I think I may be doing a lot of array modification (e.g. at one point in my algorithm I'll have [0,1,2,3,1] and another point I'll have [0,1,2,3,4], for the graph above, so it's not just "build once"). I also have to go through the list an additional time at the start to removed the "checked" mark that may have been left over from a previous test.

Sam Fen
  • 5,074
  • 5
  • 30
  • 56
  • 1
    I think this question is better suited for [Computer Science Stack Exchange](http://cs.stackexchange.com/) – Leonardo Herrera Apr 08 '16 at 17:40
  • Sounds like you want to *identify* a loop, not just detect the presence of one. – Scott Hunter Apr 08 '16 at 17:42
  • Sure, I could move it there, but the [graph-algorithm] tag has 1.5k questions, so it seemed reasonable. – Sam Fen Apr 08 '16 at 17:42
  • @ScottHunter That's correct. I've modified the title to make that clearer, thank you. – Sam Fen Apr 08 '16 at 17:42
  • 1
    @Lashane Hmmm... the accepted answer in that question does not correctly answer this one, since it identifies SCCs, which are not the same as cycles. However, it pointed me to http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph which *does* seem to answer my question. Do you want to change the pointer to the question I'm duplicating, and I'll mark it as solved? – Sam Fen Apr 08 '16 at 18:01

0 Answers0