Cycles Detection Algorithms : Almost all the known algorithm for cycle detection in graphs be it a Directed or Undirected follows the following four algorithmic approach for a Graph(V,E) where V is the number of vertices and E is the number of edges.

1. Cycle Vector Space Method
2. Search And Backtrack Method
3. Connection Matrix Method
4. Directed Graph Transformation

Here we will be focusing on the Search and Backtrack method for detection of all elementary cycles .Search and Backtrack: The method can be used only in Directed Cycles and it gives the path of all the elementary cycles in the graph .The method exhaustively searches for the vertices of the graph doing DFS in the graph .The size of the graph is reduced for those that cannot be extended .The procedure backs up to one vertex and the search is extended to other vertices.

The vertices that do not belong to any of the paths are removed thereby reducing the size of the graph .This step is done until no more vertices are left in the graph to be traversed .The method can be implemented using Trajan’s or Tiernan’s algorithm .The algorithm can also be used further in Johnson’s Algorithm to reduce some of the unnecessary searching in the Tiernan’s Algorithm.

The method involves a DFS on the graph.The general DFS that we follow does DFS for a vertex only if it has not been visited in any of the DFS procedure but that would only give us an basic cycle which would result if we reach again a vertex in DFS which was already traversed,but here to find all elementary cycles we do a DFS with all the vertex once and marking each of the vertex not visited after each DFS call.To ensure that we don't repeat the cycles we follow a topological ordering and remove the vertices from the list(used data structure for storing vertices).

Here is an algorithm for the entire process to follow: begin

integer list array A(n);logical array marked(n);integer stack current_stack ;integer stack marked_stack;/* A(n) is the array of list wich is adjacency list representation*/
 integer procedure intialize(); /*initialize the values*/
    begin;
    for i in n do 
         marked(i):=false
integer procedure print_cycles();
    begin
        for i in current_stack do
            print i ;       
logical procedure backtrack(k) do
    begin
        logical flag=false;
        current_stack->push(k);
        marked_stack->push(k);
        marked(n):=true;
        for i in A(k) do
            if i < s; /* To find only disticnt cycles in topological manner*/
               delete A(i);
            if i==s; /Cycle found */
                print_cycles()
            if marked(i):= false;
                backtrack(n); /*continue dfs*/
        if flag :=true;
            for i in marked_stack do /*unmark the elements that have been visited in any of the cycles starting from s*/
                marked(i):=false;
        current_stack->pop(k);
        backtrack:=flag
    end   backtrack(k)
begin 
    integer procedure backtrack_Util();
        begin
            for s in n do
               backtrack(s);
               while marked_stack(s)->empty do
                    for i in marked_stack do
                        marked(i):=false
     end backtrack_Util()

end

Let us demonstrate the entire algorithm with an example and list the cycles . Let us consider a cycle with the following adjacency list representation in topological ordering of vertices: Number of edges 8 Number of vertices 5 0: 1->/ 1: 2->3->4->/ 2: 1->3->/ 3: 0->2->/

The cycles listed here would be

01230 0130 121 1321 232

The time complexity is polynomial to the number of edges in Graph .However the best case arises with only one elementary cycle or the fundamental cycle in which case it is O( |V| +|E|)(directed).Another Algorithm is proposed by Chan and Chang uses set of all permutation of vertices of the graph as search space.