CSE 101 Class Notes Today: Graphs, Recursionvs. IterationSeptember 29, 2006Breadth- and Depth-First SearchProblem: Given a directed graph G = (V, E), find the set of nodes reachablefrom some node x.In doing this, we want to avoid visiting a node more than once, so we needto keep track of these visited nodes. Initially, Visited[x] is false for all x.We also need to track the set F of “frontier” nodes, which we have seen (asneighbors of a processed node) but have not yet processed.Algorithm1 Frontier <- { x }2 Visited[x] = T3 forall y != x4 Visited[y] = F5 while Frontier not empty6 y <- Choose(Frontier)7 for z in Adj(y)8 if !Visited[z]9 Insert(Frontier, z)10 Visited[z] = T11 Remove(Frontier, y)What data structure should we use? It must support (1) inserting an ele-ment, (2) choosing an arbitrary element, and (3) removing that element. Bothstacks (push, top, pop) and queues (enqueue, head, dequeue (or “decapitate”?))support these operations in constant time.Running TimeAfter a node is added to F , it is marked Visited. No visited node is addedto F . Since a Visited mark is never removed, this implies that each node isadded to F at most once. Therefore the loop at line 7 is done at most once pernode y.1This loop takes O(deg(y)), since it is executed once for each edge from y.The sum of all nodes’ out-degrees in a directed graph is |E|. Therefore the totalrunning time for lines 7-10 is O(Pv∈Vdeg(v)) = O(|E|).The remaining lines are executed |V | times, and take constant time. There-fore the total running time is O(|V | + |E|).Note that this running time is the same whether we use a stack or a queue.However, which we use will determine whether we will execute a depth-first(stack) or breadth-first (queue) search. Using a stack, however, we can gatheradditional information by remembering the order in which we insert and removeitems. In particular, no node is removed from the stack until all its childrenhave been removed. This order of removal (children before parents) is referredto as depth-first
View Full Document
Unlocking...