## Use DFS to find the largest or smallest cycle length

When there is multiple incoming edge into a node (say v), if we visit v by any of the incoming edges and visit all descendent of v we color it with black ( or we mark it as visited) and further do not explore through this node. But this is the case which does not help traversing all the way of coming to the node v. So, if we want to find the largest or smallest cycle of a graph, we need modify DFS algorithm to consider all case.

Now let us set a criteria when we will say a node is visited ( set color to black).

Node {

incoming_vertices[];

};

So if v has edges from w,x,y,z then V.incoming_vertices will have all of these.

So, v.incoming_vertices = [w,x,y,z];

Now when we initialize of DFS we will initialize all nodes for its adjacent vertices. Now if we get an edge (x,v) we will let our modified dfs go through v if v belongs to v.incoming_vertices. After we encounter (x,v) we will remove x from v.incoming_vertices.

Now, we will track level of edge vertex while running DFS. Each time a back edge(v,w) is encountered, compute cycle by level[v] – level[w] and save it if it is the largest or smallest ( whatever you are interested in).

Hope this will work. But I am not really sure of it.