o GRAPH SEARCHING 
 - depth-first search
 - breadth-first search
 - priority-first search

announcements: Seth will be in the cluster Wed 9:00pm+ (in addition to our
usual times).  Also, Quiz 3 is still on Tues Nov 25.  If you show us a
plane ticket or equivalent, we will give you a makeup quiz the
following Monday. 

========================================================================

I'm going to talk today about searching in graphs.
2 methods you've seen before. One you havent: PriorityFS - generalization.
PFS is what you'll be using on assignment 7.

These methods have different applications, let me start with simplest, DFS.


      A------D----E---H
      | \   /     |
      |  \ /      |
      C---B---G---F

DFS is simplest. Good if, say, graph is some kind of maze and just trying 
to find some way out.  Remember the depth-first search algorithm:

	If there's a neighbor you haven't visited yet, then do it. 
	Otherwise, back up.  

E.g., A=START   (label nodes by order in which visit. Darken edges as visit.)

For each vertex, let's write down where it was visited from.

vertex  A  B  C  D  E  F  G  H
parent     A  B  B  D  E  F  E

a DFS TREE is the tree you get by saying: children of node v are nbrs you 
visit from v.  Like what just drew. [Could be several legal DFS trees]

A---B---C
    |
    D---E---F---G
        |
        H

Let me now give another  way of looking at depth-first-search, because it 
will turn out that all these other kinds will fit into this framework too.

At any point in time, 3 kinds of vertices:
 - visited (done) vertices.
 - Fringe vertices: not-visited neighbors of visited/done
      (seen but not yet visited) [imagine when at node, can see neighbors.]
 - Unseen vertices.

   ------------  
     Fringe    |unseen
   --------+   |    Eg: A vs BCD. Then move B in, G->fringe
   visited |   |
   
Use "active" to denote structure that holds Fringe + maybe some
visited vertices.   Different ADT -> different kind of search.

Generic search routine (pseudocode):


active.insert(start);
while (active is not empty) {
  v = active.remove();    // exactly how will depend on type of search
  if (!visited[v]){
    visit(v);
    for (each neighbor u of v) {
      if (u is unseen) {
        active.insert(u);              // u is now in the fringe
        parent[u] = v;
      } else if (u is fringe) {
 	maybe do some updating too.    // depends on type of search
      }
    }
  }
}
  
DFS: active is a stack
     Treat fringe just like unseen nodes.  (insert and set parents)
	(So, a node may be on the stack more than once)

 --> E.g.  (as visit, check off nodes)

  A -> BCD -> CDGCD -> DGCD -> EGCD -> FHGCD -> GHGCD -> HGCD -> all rest vtd.

A few comments:

  - Why is this search called depth-first search?  Never back up unless
    you've gone as far (deep) as you possibly can.

  - What's the running time?  At most one PUSH for each edge.
    O(|E|)

  - Neat fact (one of reasons sometimes you want to do it): Notice, if
    we draw other graph edges in, they all go from a node to an
    ancestor of node.  Why is that?  Called "back edges".

BFS: "sweeping across the vertices".  Do this by
1. active is a queue.
2. Won't update fringe neighbors. I.e., treat fringe like visited nodes. 

Let's do parent, dist array this time: 
 when put u into ACTIVE, set parent[u] = v. dist[u] = dist[v]+1.
 E.g., 
      A------D----E---H
      | \   /     |
      |  \ /      |
      C---B---G---F

QUEUE: tail    head      (can tell unseen because parent arr not yet set.)
               A         take A off, visit (check it off)
           D C B         (and set parents)
           G D C
             G D   <- refer for later example.
             E G
             F E
             H F
               H
          
PARENT:  A B C D E F G H      Dist
         ---------------- ------------------
         * A A A D G B E    0 1 1 1 2 3 2 3
         
In UNWEIGHTED graph, BFS gives shortest path to each node.

Three important invariants that imply we get shortest paths:
      (1) Any path from unseen node to A must go though fringe (queue)
             -> by defn of Fringe.
      (2) queue = fringe has correct distances.
      (3) nodes in queue of lowest distance are first ones pulled off.

(won't give proof.  Save that for PFS)    

Questions?

Q: what about weighted graphs?  Here, doesn't always find shortest path tree:
       5
    A-----B
  2 |    /|
    C---+ | 
  2 |  2  | 11
    D     |
  2 |     |
    E-----+
BFS
   CB
   EC
   DE
  Why does it fail? 
  2 problems: 1) not true that current distances on fringe are correct.
              2) fringe not in order of closest to farthest.

How to fix this: Any ideas?
 Idea: expand node on Fringe of least calculated distance to start.
   (instead of looking at B first, want to look at C first)
       Update distances to nbrs on fringe.  (B's new distance is 4,
                                            new parent is C, not A)