chap graphs /breadth first (queue-basedsearch static void bfs(graph gint startqueue new aqueue( ()) enqueue(start) setmark(startvisited)while ( length( /process each vertex on int dequeue()previsit(gv)/take appropriate action for (int first( ) () next(vw)if ( getmark( =unvisited/put neighbors on setmark(wvisited) enqueue( )postvisit(gv)/take appropriate action figure implementation for the breadth-first graph traversal algorithm breadth-first search our second graph traversal algorithm is known as breadth-first search (bfsbfs examines all vertices connected to the start vertex before visiting vertices further away bfs is implemented similarly to dfsexcept that queue replaces the recursion stack note that if the graph is tree and the start vertex is at the rootbfs is equivalent to visiting vertices level by level from top to bottom figure provides an implementation for the bfs algorithm figure shows graph and the corresponding breadth-first search tree figure illustrates the bfs process for the graph of figure (atopological sort assume that we need to schedule series of taskssuch as classes or construction jobswhere we cannot start one task until after its prerequisites are completed we wish to organize the tasks into linear order that allows us to complete them one at time without violating any prerequisites we can model the problem using dag the graph is directed because one task is prerequisite of another -the vertices have directed relationship it is acyclic because cycle would indicate conflicting series of prerequisites that could not be completed without violating at least one prerequisite the process of laying out the vertices of dag in linear order to meet the prerequisite rules is called topological sort figure illustrates the problem an acceptable topological sort for this example is