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.

- Connected Components
- Tree and Cycle Detection
- Two-Coloring Graphs
- Topological Sorting
- Articulation Vertices

Mon Jun 2 23:33:50 EDT 1997