traversalwe can label each vertex by the length of shortest path (in terms of the number of edgesfrom the start vertex in particularif vertex is placed into level by bfs starting at vertex sthen the length of shortest path from to is as with dfswe can visualize the bfs traversal by orienting the edges along the direction in which they are explored during the traversaland by distinguishing the edges used to discover new verticescalled discovery edgesfrom those that lead to already visited verticescalled cross edges (see figure as with the dfsthe discovery edges form spanning treewhich in this case we call the bfs tree we do not call the nontree edges "back edgesin this casehoweverfor none of them connects vertex to one of its ancestors every nontree edge connects vertex to another vertex that is neither ' ancestor nor its descendent the bfs traversal algorithm has number of interesting propertiessome of which we explore in the proposition that follows proposition let be an undirected graph on which bfs traversal starting at vertex has been performed then the traversal visits all vertices in the connected component of the discovery-edges form spanning tree twhich we call the bfs treeof the connected component of for each vertex at level ithe path of the bfs tree between and has edgesand any other path of between and has at least edges if (uvis an edge that is not in the bfs treethen the level numbers of and differ by at most we leave the justification of this proposition as an exercise ( - the analysis of the running time of bfs is similar to the one of dfswhich implies the following proposition let be graph with vertices and edges represented with the adjacency list structure bfs traversal of takes ( mtime alsothere exist ( )-time algorithms based on bfs for the following problemstesting whether is connected computing spanning tree of gif is connected computing the connected components of