Depth-first search is a traversal technique in which we traverse a graph and print the vertices exactly once. In this article, we will study and implement the depth-first search for traversing graphs in python.
Recommended read: Implementing a graph in Python
What is the Depth-First Search Algorithm?
In a depth-first search, we traverse each vertex of the graph exactly once by starting from any single vertex. For each selected vertex we first print the vertex and then we move to one of its neighbors and print it and move to one of its neighbors and so on. This process is continued till all the vertices are traversed. While traversing a graph with depth-first search, it looks like we are moving in a path starting from the selected vertex to traverse all the vertices.
This can be understood clearly from the following example.
If we visit the above graph in a depth-first manner starting from 0, we will process the vertices in the order 0–>3–>4–>5–>2–>1. There may be alternative traversal too. In case we process 1 before 3 while we are at 0, then the BFS traversal of the graph will look like: 0–>1–>3->4->2->5.
Depth-First Search Algorithm for a Graph
As we have a general idea for the depth-first search, we will now formulate the algorithm for the DFS traversal of the graph. Here, we will assume that all the vertices of the graph are reachable from the starting vertex.
Suppose that we have been given a graph in its adjacency list representation and a starting vertex. Now we have to traverse the graph in the depth-first search manner.
We will first print the value in the starting vertex, then we will move to one of its neighbors, print its value, and move to one of its neighbors, and so on till all the vertices of the graph are printed.
So, we have the task of printing the vertices of the graph starting from the first vertex till every vertex is traversed in a serial order. To implement this concept we will use last in first out technique i.e. stack to process the graph. Also, we will use a list of visited vertices to check if the vertex is traversed in the past or not so that no vertices are printed twice.
We will print a vertex, add it to the list of visited vertices, and put its neighbors in the stack. Then, we will take out the vertices one by one from the stack, add them to the visited list after printing them, and then we will put their neighbors into the stack. Here is the algorithm for depth-first search traversal for a graph that depicts the entire process.
Algorithm DFS:
Input: Graph(Adjacency list) and Source vertex
Output: DFS traversal of graph
Start:
1.Create an empty stack S.
2.Create an empty list to keep record of visited vertices.
3.Insert source vertex into S, mark the source as visited.
4.If S is empty, return. Else goto 5.
5.Take out a vertex v from S.
6.Print the Vertex v.
7.Insert all the unvisited vertices in the adjacency list of v into S and mark them visited.
10.Goto 4.
Stop.
Implementation of depth-first search traversal of a graph in python
Now that we are familiar with the concepts and algorithm, we will implement the depth-first search algorithm for the graph and then we will execute the algorithm for the graph given in the above example.
graph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2], 6: []}
print("The adjacency List representing the graph is:")
print(graph)
def dfs(graph, source):
S = list()
visited_vertices = list()
S.append(source)
visited_vertices.append(source)
while S:
vertex = S.pop()
print(vertex, end="-->")
for u in graph[vertex]:
if u not in visited_vertices:
S.append(u)
visited_vertices.append(u)
print("DFS traversal of graph with source 0 is:")
dfs(graph, 0)
Output:
The adjacency List representing the graph is:
{0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2], 6: []}
DFS traversal of graph with source 0 is:
0-->3-->4-->5-->2-->1-->
If you have not been able to understand the execution of the code, here is a modified DFS algorithm explaining each step.
graph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2], 6: []}
print("The adjacency List representing the graph is:")
print(graph)
def dfs_explanation(graph, source):
S = list()
visited_vertices = list()
S.append(source)
visited_vertices.append(source)
while S:
vertex = S.pop()
print("processing vertex {}.".format(vertex))
for u in graph[vertex]:
if u not in visited_vertices:
print("At {}, adding {} to Stack".format(vertex, u))
S.append(u)
visited_vertices.append(u)
print("Visited vertices are:", visited_vertices)
print("Explanation of DFS traversal of graph with source 0 is:")
dfs_explanation(graph, 0)
Output:
The adjacency List representing the graph is:
{0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2], 6: []}
Explanation of DFS traversal of graph with source 0 is:
processing vertex 0.
At 0, adding 1 to Stack
At 0, adding 3 to Stack
Visited vertices are: [0, 1, 3]
processing vertex 3.
At 3, adding 4 to Stack
Visited vertices are: [0, 1, 3, 4]
processing vertex 4.
At 4, adding 2 to Stack
At 4, adding 5 to Stack
Visited vertices are: [0, 1, 3, 4, 2, 5]
processing vertex 5.
Visited vertices are: [0, 1, 3, 4, 2, 5]
processing vertex 2.
Visited vertices are: [0, 1, 3, 4, 2, 5]
processing vertex 1.
Visited vertices are: [0, 1, 3, 4, 2, 5]
Conclusion
In this article, we have seen the underlying concepts behind the depth-first search traversal algorithm for a graph, designed its algorithm, and then implemented it in python. Stay tuned for more informative articles.