dsap.graph.bfs

module documentation

Provides BFS and BFS_complete function to support breadth-first search of a graph.

Function	`BFS`	Perform BFS of the undiscovered portion of Graph g starting at Vertex s.
Function	`BFS_complete`	Perform BFS for entire graph and return forest as a dictionary.

def BFS(g, s, discovered): ¶

Perform BFS of the undiscovered portion of Graph g starting at Vertex s.

discovered is a dictionary mapping each vertex to the edge that was used to discover it during the BFS (s should be mapped to None prior to the call). Newly discovered vertices will be added to the dictionary as a result.

def BFS_complete(g): ¶

Perform BFS for entire graph and return forest as a dictionary.

Result maps each vertex v to the edge that was used to discover it. (vertices that are roots of a BFS tree are mapped to None).