graphs.depth_first_search

Non recursive implementation of a DFS algorithm.

Attributes

G

Functions

depth_first_search(→ set[str])

Depth First Search on Graph

Module Contents

graphs.depth_first_search.depth_first_search(graph: dict, start: str) → set[str]

Depth First Search on Graph :param graph: directed graph in dictionary format :param start: starting vertex as a string :returns: the trace of the search >>> input_G = { “A”: [“B”, “C”, “D”], “B”: [“A”, “D”, “E”], … “C”: [“A”, “F”], “D”: [“B”, “D”], “E”: [“B”, “F”], … “F”: [“C”, “E”, “G”], “G”: [“F”] } >>> output_G = list({‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’}) >>> all(x in output_G for x in list(depth_first_search(input_G, “A”))) True >>> all(x in output_G for x in list(depth_first_search(input_G, “G”))) True

graphs.depth_first_search.G