c++ - back and forward edges in directed graph -
i new graph theory. writing code find forward , edges in directed graph. searched , implemented code below. code going infinite loop. please have look. greateful you.
void dfsvisit(u) { u->color="gray"; u->time=count; count++; for(every child node v of u) { if(v->color == "black") { if(u->time < v->time) cout<<"edge "<<u<<"->"<<v<<" forward edge"<<endl; else cout<<"edge "<<u<<"->"<<v<<" cross edge"<<endl; } if(v->color == "gray") cout<<"edge "<<u<<"->"<<v<<" edge"<<endl; if(v->color == "white") cout<<"edge "<<u<<"->"<<v<<" tree edge"<<endl; dfsvisit(v); } u->color="black"; u->time=count; count++; }
i see 2 possible problems code:
you call
dfsvisit
every child, regardless of color. indented deeper level, didn't add parenthesis around white if - based on pseudocode,cout
affected if statement. since pseudocode, should post original c++ code wrote clear.you have 3 colors in conditions (grey, black, , white), never set white anywhere. edges initialized white before call
dfsvisit
? (you should consider using enum or enum class colors, it's cleanear , you'll less cause bugs typos)
Comments
Post a Comment