Traversing directed cyclic and acyclic graphs using modified BFS algorithm

摘要

Given a graph G={V, E} and a distinguished source vertex ‘s’, the traditional BFS algorithm systematically explores the edges of G to discover every vertex that is reachable from the source vertex ‘s’ and it produces a “Breadth — First — Tree” with root ‘s’. The Breadth-First-Tree formed after running the traditional algorithm may not visit all the vertices in some graphs for instance Directed cyclic and acyclic graphs. As a consequence the traversing may be incomplete. With modified BFS algorithm we can traverse the graphs, which we may not traverse with existing BFS completely but the output may contain multiple trees forming a spanning forest.