12.3 Graph Traversal pg575 1. Methods pg575 Depth-first traversal of a graph is roughly analogous to preorder traversal of an ordered Start, 0 tree. Suppose that the traversal has just visited a vertex v, and let W1, W2, ..Wk be the vertices adjacent to v. then we shall next visit w1 and keep w2…Wk waiting. After visiting Wi,we traverse all the vertices to which it is adjacent before returning to Depth-first traversal traverse w2…Wk
12.3 Graph Traversal pg.575 1. Methods pg.575 • Depth-first traversal of a graph is roughly analogous to preorder traversal of an ordered tree. Suppose that the traversal has just visited a vertex v, and let w1 , w2 , … wk be the vertices adjacent to v. Then we shall next visit w1 and keep w2 , … wk waiting. After visiting w1 , we traverse all the vertices to which it is adjacent before returning to traverse w2 , … wk
Breadth-first traversal of a graph is roughly analogous Start to level-by-level traversal of an ordered tree. If the traversal has just visited a vertex v, then it next visits all the vertices adjacent to v, putting the vertices adjacent to these in a waiting list to 7 be traversed after all Breadth-first traversa vertices adjacent to v have been visited
• Breadth-first traversal of a graph is roughly analogous to level-by-level traversal of an ordered tree. If the traversal has just visited a vertex v, then it next visits all the vertices adjacent to v, putting the vertices adjacent to these in a waiting list to be traversed after all vertices adjacent to v have been visited
2. Depth-First Algorithm pg 577-578 template <int max size> void Digraph<max size> depth first(void (*visit)(Vertex &))const Post: The function *visit has been performed at each vertex of the Digraph in depth-first order. Uses: Method traverse to produce the recursive depth-first order. * i bool visited[max size]; Vertex v: for (allv in G)visited=false; for(all v in G) if (visited[v]traverse(v, visited, visit)
2. Depth-First Algorithm pg.577-578 template <int max_size> void Digraph<max_size>:: depth_first(void (*visit)(Vertex &)) const /* Post: The function *visit has been performed at each vertex of the Digraph in depth-first order. Uses: Method traverse to produce the recursive depth-first order. */ { bool visited[max_size]; Vertex v; for (all v in G) visited[v] = false; for (all v in G) if (!visited[v])traverse(v, visited, visit); }
The recursion is performed in an auxiliary function traverse. template <int max size> void Digraph<max size> traverse( Vertex &v, bool visited[ void (visit)(Vertex &))const / Pre: v is a vertex of the Digraph Post: The depth-first traversal, using function*visit has been completed for v and for all vertices that can be reached from v Uses: traverse recursively. * I Vertex W; visited= true; visit)(v) for(all w adjacent to v) if(!visitedlw)traverse(w, visited, visit
The recursion is performed in an auxiliary function traverse. template <int max_size> void Digraph<max_size>:: traverse ( Vertex &v, bool visited[], void (*visit)(Vertex &) ) const /* Pre: v is a vertex of the Digraph . Post: The depth-first traversal, using function*visit , has been completed for v and for all vertices that can be reached from v . Uses: traverse recursively. */ { Vertex w; visited[v] = true; (*visit)(v); for(all w adjacent to v) if(!visited[w])traverse(w, visited, visit); }
3. Breadth-First Algorithm pg 578 template <int max size> void Digraph<max size> breadth first(void visit)(Vertex &))const I Queue g; bool visited[max size]; Vertex V, W, X for(allv in G)visited= false, for(allv in G) if (visited[v]) Iq append(v); while(!.empty() [q retrieve w); if (visited[w) I visited]= true; *visit)(w); for(all x adjacent to w)q append(x) gserve(;
3. Breadth-First Algorithm pg. 578 template <int max_size> void Digraph<max_size>:: breadth_first(void (*visit)(Vertex &)) const { Queue q; bool visited[max_size]; Vertex v, w, x; for (all v in G) visited[v] = false; for (all v in G) if (!visited[v]) { q.append(v); while(!q.empty( )) { q.retrieve(w); if (!visited[w]) { visited[w] = true; (*visit)(w); for(all x adjacent to w) q.append(x); } q.serve( ); } } }