Iterative Depth First Traversal of Graph in Python

In this tutorial, we will learn how to perform the Iterative Depth First Traversal of a graph using Python with some examples.

Iterative Depth First Traversal of Graph in Python

Depth First Search is a traversal technique in which we traverse a graph and find vertices exactly once.

For more clarification on Depth First Search here is an example :

http://”C:\DFS.Example.jpg”

From the above example, we can find the Depth First Traversal. So from the above graph, the starting point is ‘0’ then we can process the vertices in the order 0->3->4->5->2->1. To get more clarity on the DFS here there is a simple algorithm.

Algorithm DFS:

Start:

1. Create an empty stack M.
2. Create an empty list to store the visited vertices count.
3. Insert starting vertices into M, and mark the starting as visited.
4. If M is empty, return. Else move to 5 step.
5. Take out a vertex v from M.
6. Print the vertex v.
7. Insert all unvisited vertices in the adjacency list of v into M and mark them as visited.
8. Goto 4 step.

Stop.

Now we are familiar with the concepts of the algorithm, we will impliment the DFS algorithm for the graph and then we will execute the graph given in the above.

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 list of the graph is:")
print(graph)
def dfs(graph, source):  
    M = list()
    visited_vertices = list()
    M.append(source)
    visited_vertices.append(source)
    while M:
        vertex = M.pop()
        print(vertex, end="->")
        for n in graph[vertex]:
            if n not in visited_vertices:
                M.append(n)
                visited_vertices.append(n)
print("Depth First Search Traversal path:")
dfs(graph, 0)

Output:

The list Of the graph is:
graph = {0: [1, 3], 1: [0, 2, 3], 2: [4, 1, 5], 3: [4, 0, 1], 4: [2, 3, 5], 5: [4, 2], 6: []}
Depth First Search Traversal path:
0->3->4->5->2->1->