CMSC 451 Design and Analysis of Computer Algorithms Fall 2006 Notes for Dave Mount s Lectures Note The material given here is based on the presentation in the book Introduction to Algorithms by Cormen Leiserson Rivest and Stein Although the concepts are essentially the same as those in Kleinberg and Tardos the notation differs Graphs Breadth First Search Graph Traversals There are a number of approaches used for solving problems on graphs One of the most important approaches is based on the notion of systematically visiting all the vertices and edge of a graph The reason for this is that these traversals impose a type of tree structure or generally a forest on the graph and trees are usually much easier to reason about than general graphs Breadth first search Given an graph G V E breadth first search starts at some source vertex s and discovers which vertices are reachable from s Define the distance between a vertex v and s to be the minimum number of edges on a path from s to v Breadth first search discovers vertices in increasing order of distance and hence can be used as an algorithm for computing shortest paths At any given time there is a frontier of vertices that have been discovered but not yet processed Breadth first search is named because it visits vertices across the entire breadth of this frontier Initially all vertices except the source are colored white meaning that they are undiscovered When a vertex has first been discovered it is colored gray and is part of the frontier When a gray vertex is processed then it becomes black The search makes use of a queue a first in first out list where elements are removed in the same order they are inserted The first item in the queue the next to be removed is called the head of the queue We will also maintain arrays color u which holds the color of vertex u either white gray or black pred u which points to the predecessor of u i e the vertex who first discovered u and d u the distance from s to u Only the color is really needed for the search in fact it is only necessary to know whether a node is nonwhite We include all this information because some applications of BFS use this additional information Observe that the predecessor pointers of the BFS search define an inverted tree an acyclic directed graph in which the source is the root and every other node has a unique path to the root If we reverse these edges we get a rooted unordered tree called a BFS tree for G Note that there are many potential BFS trees for a given graph depending on where the search starts and in what order vertices are placed on the queue These edges of G are called tree edges and the remaining edges of G are called cross edges It is not hard to prove that if G is an undirected graph then cross edges always go between two nodes that are at most one level apart in the BFS tree Can you see why this must be true Below is a sketch of a proof that on termination d v is equal to the distance from s to v See the CLRS for a detailed proof Theorem Let s v denote the length number of edges on the shortest path from s to v Then on termination of the BFS procedure d v s v Proof Sketch The proof is by induction on the length of the shortest path Let u be the predecessor of v on some shortest path from s to v and among all such vertices the first to be processed by the BFS Thus s v s u 1 When u is processed we have by induction d u s u Since v is a neighbor of u we set d v d u 1 Thus we have d v d u 1 s u 1 s v Lecture Notes 1 CMSC 451 Breadth First Search BFS G s for each u in V color u white d u infinity pred u null color s gray d s 0 Q s while Q is nonempty u Q Dequeue for each v in Adj u if color v white color v gray d v d u 1 pred v u Q Enqueue v color u black initialization initialize source s put s in the queue u is the next to visit if neighbor v undiscovered mark it discovered set its distance and its predecessor put it in the queue we are done with u a s e d g b s a s0 a 1 1 c Q a c d s0 a 1 1 c e 2 b2 f 3 3 g e 2 b f g Q empty Q c d e e 2 1 d b2 f 3 3 g 1 c 1 d Q d e b b2 d e 1 c e 2 s0 a 1 1 d 1 c s0 a 1 1 d c s0 a 1 1 d f c s0 a 1 e 2 Q b f g 1 c 1 d b2 Q e b Fig 1 Breadth first search Example Lecture Notes 2 CMSC 451 as desired Analysis The running time analysis of BFS is similar to the running time analysis of many graph traversal algorithms As done in CLR V V and E E Observe that the initialization portion requires V time The real meat is in the traversal loop Since we never visit a vertex twice the number of times we go through the while loop is at most V exactly V assuming each vertex is reachable from the source The number of iterations through the inner for loop is proportional to deg u 1 The 1 is because even if deg u 0 we need to spend a constant amount of time to set up the loop Summing up over all vertices we have the running time X X T V V deg u 1 V deg u V 2V 2E V E u V u V The analysis is essentially the same for directed graphs Depth First Search Depth First Search The next traversal algorithm that we will study is called depth first search and it has the nice property that nontree edges have a good deal of mathematical structure Consider the problem of searching a castle for treasure To solve it you might use the following strategy As you enter a room of the castle paint some graffiti on the wall to remind yourself that you were already there Successively travel from room to room as long as you come to a place you haven t already been When you return to the same room try a different door leaving the room assuming it goes somewhere you haven t already been When all doors have been tried in a given room then backtrack Notice that this algorithm is described recursively In particular when you enter a new room you are beginning a new search This …