Find Cycles in Organic Graphs

Question

I want to find all cycles in a graph that is built organically. In a nutshell cycles happen when two branches or paths end at a common vertex. Something like
1->2->3->4
1->5->4
form the cycle of 1->2->3->4->5->1.

Due to the nature of the graph I cannot use DFS or similar algorithms, because there are no back-edges. I have found Find All Cycle Bases In a Graph, With the Vertex Coordinates Given and Algorithms to Identify All the Cycle Bases in a UnDirected Graph to go into the right direction, but no efficient algorithm was presented in the two threads.

Is there an optimized solution in either pseudocode or implemented form or should I lean towards any of the presented solutions and optimize it myself? In the latter case, which offered code sample should I use for this purpose?

Looking forward to your replies.

Answer 1

I think DFS if right for you.

Explore the grapth till you encounter vertex that was already explored

This is the pseudocode:

function DFSFindCycle(Start, Goal)
push(Stack,Start)
while Stack is not empty
    var Node := Pop(Stack)
    Color(Node, Grey)
    for Child in ExpandNotExploredEdges(Node)
        if Node.color != White
    return true 
        if Node.color = White
           push(Stack, Child)
           label edge e, Node:Child as explored
    Color(Node, Black)
retrun false

Hope it helps