Python Data Structures and Algorithms

Depth-first search

As the name suggests, this algorithm traverses the depth of any particular path in the graph before traversing its breadth. As such, child nodes are visited first before sibling nodes. It works on finite graphs and requires the use of a stack to maintain the state of the algorithm:

    def depth_first_search(graph, root):         visited_vertices = list()         graph_stack = list()         graph_stack.append(root)         node = root 

The algorithm begins by creating a list to store the visited nodes. The graph_stack stack variable is used to aid the traversal process. For continuity's sake, we are using a regular Python list as a stack.

The starting node, called root, is passed with the graph's adjacency matrix, graph. root is pushed onto the stack. ...