dsap.graph.dfs

module documentation

Provides DFS, DFS_complete, and construct_path functions for depth-first search of a graph.

Function	`construct_path`	Return a list of vertices comprising the directed path from u to v, or an empty list if v is not reachable from u.
Function	`DFS`	Perform DFS of the undiscovered portion of Graph g starting at Vertex u.
Function	`DFS_complete`	Perform DFS for entire graph and return forest as a dictionary.

def construct_path(u, v, discovered): ¶

Return a list of vertices comprising the directed path from u to v, or an empty list if v is not reachable from u.

discovered is a dictionary resulting from a previous call to DFS started at u.

def DFS(g, u, discovered): ¶

Perform DFS of the undiscovered portion of Graph g starting at Vertex u.

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

def DFS_complete(g): ¶

Perform DFS 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 DFS tree are mapped to None.)