next up previous contents index CD CD Algorithms
Next: Connected Components Up: Graph Algorithms Previous: Depth-First Search

Applications of Graph Traversal

Most elementary graph algorithms involve making one or two traversals of the graph, while we update our knowledge of the graph as we visit each edge and vertex. Properly implemented using adjacency lists, any such algorithm is destined to be very fast. Both BFS and DFS run in O(n+m) on both directed and undirected graphs where, as usual, n is the number of vertices and m the number of edges in the graph. This is optimal, since it is as fast as one can hope to read the graph. The trick is seeing when traversal approaches are destined to work. We present several examples below.

Mon Jun 2 23:33:50 EDT 1997