ADMIN: we will look at the email about hw2 turnin.  Also I'll take any
  last-minute questions about hw2.  Expect one more homework (hw3) due
  next week, to be followed by a midterm the week after that, just
  before break.  Do you prefer Wednesday or Friday (just before break)
  for the midterm exam?

Today we will start on Chapter 4, about graphs.  I'm assuming this is
a "second exposure" to graphs, for example you may have seen BFS or
DFS in some context already in CS171.  We'll talk about graphs in
general first, their representation and a few example applications.
(Like, what is printed on the inside of our textbook cover?)

Typical graphs:
   undirected or directed, "large" examples tend to be sparse
   possibly with additional data on the vertices and/or the edges
   representation: adjacency list or adjacency matrix?
     the first is much better for large sparse graphs

Introductory slides (nice example graph visualizations):
    41UndirectedGraphs.pdf

We'll look at the "Paths API" on page 535, and its example
implementation by DepthFirstPaths.java (but we postpone DFS itself for
the next lecture).  We'll run the example.

In fact our textbook implements many graph algorithms in this same
way: you construct some object, like DepthFirstPaths (with the input
graph G as an argument), and just the act of constructing the object
runs the algorithm.  Then in order to see the output of the algorithm,
we examine the resulting object.

Some files:
   ../book/tinyG.txt   (small graph encoded as text, see page 522)
   ../book/tinyCG.txt   (small connected graph encoded as text)
   ../book/Graph.java  (implements Graph API, undirected, adjacency lists)
   ../book/DepthFirstPaths.java (implements Paths API)

To run:
   cd ../book
   run DepthFirstPaths tinyCG.txt




A simple problem, from Section 4.1: count the connected components of
an undirected graph, using DFS (depth first search) to discover each
component.

See "Graph API" on page 522, "Paths API" on page 535, and maybe
"CC API" on page 543.  Corresponding book code:
Some files:
   ../book/tinyG.txt   (small graph encoded as text, see page 522)
   ../book/tinyCG.txt   (small connected graph encoded as text)
   ../book/Graph.java  (implements Graph API, undirected, adjacency lists)
   ../book/DepthFirstPaths.java (implements Paths API)
   ../book/CC.java     (implements CC API)
To run:
   cd ../book
   run DepthFirstPaths tinyCG.txt
   run CC tinyG.txt
   run CC mediumG.txt


We'll simulate the small example by hand, and figure out the
order in which it discovers the vertices and the components.