Graph Searching

There are two commonly used algorithms for searching a graph
- Depth First Search attempts to explore a graph by going as far from the root node as possible.
- Breadth First Search attempts to explore a graph in "rings" around the starting node.
These work on directed or undirected graphs.

They work on weighted or not, but they really don't consider the weights.

DFS(G) 
foreach node in G
   node.parent = null
   node.start = ∞
   node.finish = ∞
   node.color = UNEXPLORED;

time = 1
foreach node in G
   
   if node.color == UNEXPLORED
      DFSVisit(G,node,time)

DFS Visit(G, node)
   node.color = WORKING
   node.start = time++
   for each x adjacent to node
      if x.color == UNEXPLORED
         x.parent = node
	 DFSVisit(G,x,time)
   node.color = DONE
   node.finish=time++