What is a depth-first search?

This is one of the widely used and very popular graph search algorithms. To understand this algorithm, think of a maze. What we do when have to solve a maze? We take a route, keep going till we find a dead end. After hitting the dead end, we take a backtrack and keep coming until we see a path we did not try before. Take that new route. Again keep going till we find a dead end. Take a backtrack again….

The depth-first search works almost in the same way. Using this type of backtracking process. From the starting point, it travels until it finds no more paths to follow. Then takes a backtrack and comes back to a point that has unexplored paths. It keeps doing that until finished traveling all the nodes and edges.

That was just the easiest way I could introduce the depth-first search. I will explain it in more detail later.

Why Depth-Firth Search is Important?

The depth-first search has a wide range of use cases.

1. Solving a maze or puzzle as I described above
2. Scheduling a problem
3. Cycle detection in a graph
4. Network analysis
5. Mapping routes
6. Topological sorting

And many more. The depth-first search is also the base for many other complex algorithms.

How Depth-First Search Works?

In this section, we will see visually the workflow of a depth-first search.

Here is a graph and the source node is shown as the node u.

We can go to node v or x from u. We can go in any direction.

We choose to go to v.

It is clear from the graph that there is only one outgoing route from v. That is y.

So, we are in y now.

As before, from y also there was one outgoing path. That was to x.

So, we had to come to x

Look, we are stuck! There is no outgoing path from x.

As discussed before, in this situation we take a backtrack.

By backtracking, we came back to y. There are no paths to go from here.

So, let’s backtrack again.

Now, we are in v.

Explore v. But no outgoing path from v again. So go back one more step.

We came back to one more step and that is our source node u.

Here we can see that there is an outgoing path that is unexplored by us.

We go from u to x and see that x is already visited before. This type of edge is called a forward edge. Then from x also there is a path to v. Node v is also visited and v is an ancestor to x. So this path is called back edge.

We are done with all the nodes and edges in the ‘uvyx’ circle. Here we explore a new node w.

From w, we can go to z or to y. I choose to go to z for now.

Notice, z comes back to z using a back edge.

There is nowhere to go from z. So we take backtrack again and come back to w. And w has one unexplored edge that goes to y.

This type of connecting edges is called a cross edge.

That was the end of traveling. We traveled through all the nodes and edges.

Developing the Depth-Firth Search Algorithm

Before developing the algorithm, it is important to express the diagram above as an adjacency list. If you have not seen an adjacency list before, it’s a dictionary. Where each node is a key and the nodes that are linked in it with the outgoing paths are the values in a list.

Look at the adjacency list below. Node ‘u’ has two outgoing links going to node ‘v’ and node ‘x’. So, ‘u’ is the key and a list with elements ‘v’ and ‘x’ is the value. In the same way, we have to take every other node and make key-value pairs.

g = {
    'u': ['v', 'x'],
    'v': ['y'],
    'y': ['x'],
    'x': ['v'],
    'w': ['y', 'z'],
    'z': ['z']
    }

The adjacency list is ready.

I will use a recursion method for developing the depth-first search algorithm.

The idea is to traverse all the nodes and vertices the way we traversed in the pictures in the previous section. To keep track of the visited nodes, we will start with an empty list.

class depth_first:
    def __init__(self):
        self.visited = []

Now define a function that will loop through all the nodes and if there is an unvisited node, we will go in that node and find out where this node takes us.

def dfs(self, graph):        
    for ver in graph:
        if ver not in self.visited:
            self.dfs_visit(graph, ver)
    return self.visited

Notice, in this function, we called a function ‘dfs_visit’. This function is supposed to travel a whole unvisited route offered by an unvisited node and add those unvisited nodes to the ‘visited’ list. We will implement this function recursively.

Here is the ‘dfs_visit’ function:

def dfs_visit(self, graph, vertex):
    if vertex not in self.visited:
        self.visited.append(vertex)
        for nb in g[vertex]:
            self.dfs_visit(g, nb)

Have a careful look! This function will add a node if it is not already in the ‘visited’ list. Then it will go to one node adjacent to it and call itself.

That way, it will traverse the whole route that was unvisited before and one at a time.

Here is the complete code:

class depth_first:
    def __init__(self):
        self.visited = []    def dfs(self, graph):
        for ver in graph:
            if ver not in self.visited:
                self.dfs_visit(graph, ver)
        return self.visited

def dfs_visit(self, graph, vertex):
if vertex not in self.visited:
self.visited.append(vertex)
for nb in g[vertex]:
self.dfs_visit(g, nb)

Let’s test it now using the adjacency list we described before.

d = depth_first()
print(d.dfs(g))

Output:

['u', 'v', 'y', 'x', 'w', 'z']

Look, the order of the node is the same as we expected!

Common Mistakes People Make in DFS algorithm

I saw many other websites and blogs that explained the depth-first search algorithm. But the code a lot of them used is like this:

def dfs(graph, vertex, path=[]):
    path += [vertex]    for n in graph[vertex]:
        if n not in path:
            path = dfs(graph, n, path)
    return path

If you notice, it does not loop through the vertices. It starts from the source node and keeps traversing through the adjacency nodes. It will work on a graph where each node has an outgoing node that connects back to any other visited node.

But the diagram we are working on where node ‘y’ does not have an outgoing link to ‘w’, this algorithm will not work. Because it will never reach the ‘w’.

Let’s check

print(dfs(g, 'u'))

Output:

['u', 'v', 'y', 'x']

See, it cannot see the nodes ‘w’ and ‘z’.

Conclusion

I wanted to introduce and explain the process of how the depth-first search works and how to develop the algorithm as clearly as I can. Hopefully, it is easy for you now.

Feel free to follow me on Twitter and like my Facebook page.

#programming #pythonprogramming #algorithms #graphalgorithm #depthfirstsearch #python