graph algorithms when discussing dfswe described classification of nontree edges being either back edgeswhich connect vertex to one of its ancestorsforward edgeswhich connect vertex to one of its descendantsor cross edgeswhich connect vertex to another vertex that is neither its ancestor nor its descendant for bfs on an undirected graphall nontree edges are cross edges (see exercise - )and for bfs on directed graphall nontree edges are either back edges or cross edges (see exercise - the bfs traversal algorithm has number of interesting propertiessome of which we explore in the proposition that follows most notablya path in breadthfirst search tree rooted at vertex to any other vertex is guaranteed to be the shortest such path from to in terms of the number of edges proposition let be an undirected or directed graph on which bfs traversal starting at vertex has been performed then the traversal visits all vertices of that are reachable from for each vertex at level ithe path of the bfs tree between and has edgesand any other path of from to has at least edges if (uvis an edge that is not in the bfs treethen the level number of can be at most greater than the level number of we leave the justification of this proposition as an exercise ( - the analysis of the running time of bfs is similar to the one of dfswith the algorithm running in ( mtimeor more specificallyin (ns ms time if ns is the number of vertices reachable from vertex sand ms < is the number of incident edges to those vertices to explore the entire graphthe process can be restarted at another vertexakin to the dfs complete function of code fragment alsothe actual path from vertex to vertex can be reconstructed using the construct path function of code fragment proposition let be graph with vertices and edges represented with the adjacency list structure bfs traversal of takes ( mtime although our implementation of bfs in code fragment progresses level by levelthe bfs algorithm can also be implemented using single fifo queue to represent the current fringe of the search starting with the source vertex in the queuewe repeatedly remove the vertex from the front of the queue and insert any of its unvisited neighbors to the back of the queue (see exercise - in comparing the capabilities of dfs and bfsboth can be used to efficiently find the set of vertices that are reachable from given sourceand to determine paths to those vertices howeverbfs guarantees that those paths use as few edges as possible for an undirected graphboth algorithms can be used to test connectivityto identify connected componentsor to locate cycle for directed graphsthe dfs algorithm is better suited for certain taskssuch as finding directed cycle in the graphor in identifying the strongly connected components