Graph discovery and cycle detection

Question

Consider the graph below

Assume that the program starts executing at time t = 0 and has initially discovered the node A. At time t = 0 no other nodes are discovered. At time t = 4 the program has discovered all the nodes in the graph above and is back at its starting state thus completing a cycle.

My question is as follows:

• Assuming that no prior information is available about the graph what is the best possible way to do this for a graph with a large number of nodes (n > 1000) and many cycles (not necessarily as simple and direct as above.) I do not want to detect cycles after discovering the whole graph.

Answer 1

The approach you are describing is pretty much a DFS - choose one branch - and develop it as much as you can.

Another common graph discovery algorithm is BFS - "discover" all nodes at distance 0 from the source, then at distance 1, .... until all graph is discovered.

Note that a variation of DFS, that holds a dynamic 'visited' set (and allows to rediscover nodes that are already discovered, but not in the current branch) can be used for cycles detection (assuming you want all cycles), but may take a long time to run - because there could be exponential number of cycles in the graph

Answer 2

I don't want to give you solution , you should try yourself ,
but here is something which will get you going :
I am using Depth First Search here .

initially all nodes grey

for each node
    mark it as white
    dfs(grey child)
    mark node black

dfs(node)
if(child node white) 
  CYCLE detected
else ...normal routine 

If you still are not able to understand , i will elaborate .