O'Reilly logo

Python Data Structures and Algorithms by Benjamin Baka

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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. ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required