breadth-first search the advancing and backtracking of depth-first searchas described in the previous sectiondefines traversal that could be physically traced by single person exploring graph in this sectionwe consider another algorithm for traversing connected component of graphknown as breadth-first search (bfsthe bfs algorithm is more akin to sending outin all directionsmany explorers who collectively traverse graph in coordinated fashion bfs proceeds in rounds and subdivides the vertices into levels bfs starts at vertex swhich is at level in the first roundwe paint as "visited,all vertices adjacent to the start vertex --these vertices are one step away from the beginning and are placed into level in the second roundwe allow all explorers to go two steps ( edgesaway from the starting vertex these new verticeswhich are adjacent to level vertices and not previously assigned to levelare placed into level and marked as "visited this process continues in similar fashionterminating when no new vertices are found in level python implementation of bfs is given in code fragment we follow convention similar to that of dfs (code fragment )using discovered dictionary both to recognize visited verticesand to record the discovery edges of the bfs tree we illustrate bfs traversal in figure def bfs(gsdiscovered) """perform bfs of the undiscovered portion of graph starting at vertex discovered is dictionary mapping each vertex to the edge that was used to discover it during the bfs ( should be mapped to none prior to the call newly discovered vertices will be added to the dictionary as result "" level [sfirst level includes only while len(level prepare to gather newly found vertices next level for in level for in incident edges( )for every outgoing edge from opposite( if not in discoveredv is an unvisited vertex discovered[ve is the tree edge that discovered will be further considered in next pass next level append(vrelabel 'nextlevel to become current level next level code fragment implementation of breadth-first search on graphstarting at designated vertex