Member-only story
In a former article we talked about graph theory — we specifically looked at breadth-first-search and depth-first-search and how they differ in their method. In this article, we will try to implement the depth-first-search algorithm with Python.
Quick Summary On Depth-First-Search
Now that we have understood how Breadth-First Search works, we can then try to understand the Depth-First Search Algorithm. In contrast to the BFS Algorithm, where we methodically searched each level fully before moving on, the DFS algorithm starts at the root and explores as far as possible along each branch before backtracking. This is done until the whole graph is fully explored. We can illustrate it with an example:
We can again see that vertex “a” is the root in all cases. It becomes clear how the algorithm visits all vertices in a branch, before backtracking and exploring a new branch. One important thing to note is that we do not choose the order randomly for visiting vertices — usually, we choose the vertex with the smallest key value. In the undirected graph above, this is why we choose the branch of vertex b first, since b < c < d.
An obvious question is again — what happens if we cannot reach all possible vertices in our graph from our root? The answer is the same as with BFS, we…
