REMARKS: I'm sick since Monday, so today I'll be a little slow.  I
still want to get some new homework (hw3) to you by Friday.  Our
midterm exam will be in two weeks, Wednesday 3/7.

We continue with undirected graphs.

Last time we saw the "Paths API" (page 535) and tried running
its its implementation:
   cd ../book
   run DepthFirstPaths tinyCG.txt 0  # a connected graph
   run DepthFirstPaths tinyG.txt  0  # a disconnected graph

(By the way, how does Paths compare to UF?)

We'll look at ../book/DepthFirstPaths.java and see how it works,
by DFS (depth first search, has some nice examples in book).
(See also: DepthFirstSearch.java, which is a little simpler,
and the first example in the book.)

Next we'll look at a the "CC API", page 543.  The idea here is
to somehow identify all the connected components in a graph.
Again we'll use a variant of DFS, see: ../book/CC.java
To run:
    cd ../book
    run CC tinyCG.txt    # 1 component (connected)
    run CC tinyG.txt     # 3 components
    run CC mediumG.txt   # 1 component (larger)

We'll see that both of these DFS examples run in O(V+E) time, in the
adjacency list representation.  In fact, DepthFirstPaths the first one
runs in O(E) time.

Question: for what kind of graphs would O(V+E) be worse than O(E)?

Next topic: breadth first search (BFS), for finding shortest paths.
If we get there, we'll switch back to the slides, page 50.