Home > Uncategorized > Use DFS to find the largest or smallest cycle length

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.

 

 

 

Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: