Python for Beginners: Depth First Traversal in Python

Graphs are non linear data structures used to represent relationships between different objects. In this article, we will discuss depth first traversal algorithm to print the vertices in a graph. We will also implement the depth first traversal algorithm in python to illustrate the working of the algorithm.

What is depth first traversal?

Depth first traversal is a graph traversal algorithm in which we start from a vertex of a graph and print its value. Then we move to one of the neighbors of the present vertex and print its values. If there are no neighbors of the current vertex that have to be printed, we move to the previous vertex to see if all of their neighbors are printed. If not, we select one of the neighbors and print its value. We repeat this process until all the vertices of the graph are printed.  It should be noted that we have to print each vertex only once. 

Let us try this process on the following graph.

Graph

Here, Let us start from the vertex A. First, we will print A. After that we will select one of the vertices from B, D,E and F as all are neighbors of A. 

Let us select B. After printing B, we will select one of the vertices from A, C and F as these are neighbors of B. Here, A is already printed so it won’t be selected.

Let us select C. After printing C, we have no neighbors of C to print. So, we will move to the previous vertex of C i.e. vertex B to check if all the neighbors of B are already printed. Here, F has not been printed yet. So, we will select F.

After printing F, we have to select one of the vertices from A and B as these are neighbors of F. But, both these vertices are already printed. So, we will move to previous vertex of F i.e. B. 

At B, we can see that all the neighbors of B have already been printed. So, we will move to previous vertex of B i.e. A. 

At A, neighbors D and E have not been printed yet, So we will select one of the vertices.

Let us select D. After printing D, we can see that D does not have any neighbors to print. So, we will move to its previous vertex i.e A. 

Now, only one neighbor of A has not been printed i.e. E. So, we will print E.

At this point, all of the vertices of the graph have been printed in the order A, B, C, F, D, E. Hence, we will stop this process.

You can observe that there may be many depth first traversal of a single graph based on the neighbor that we choose. 

Algorithm for depth first traversal

The algorithm for depth first traversal of a graph is implemented using a stack data structure. Here, we will assume that we have a connected graph. In other words, we can reach each vertex of the graph from the starting vertex.

We will maintain a stack to store the vertices that have not been printed and a list to store the visited vertices. After that we will process the graph using the following algorithm.

1. Create an empty stack S to store the vertices that have not been printed.
2. Create an empty list L to store the visited vertices.
3. Insert the source vertex into S. Also, insert the source vertex to L.
4. If  the stack S is empty, Go to 9 else go to 5.
5. Take out a vertex v from S.
6. Print the value in v. 
7. Insert all the unvisited neighbors of v into the stack S and list L.
8. Go to 4.
9. Stop.

This Algorithm can be demonstrated using the following source code for the graph given in the figure above.

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Given Graph is:")
print(graph)


def DFS_Algorithm(input_graph, source):
    stack = list()
    visited_list = list()
    print("At {}, adding vertex {} to stack and visited list".format(source, source))
    stack.append(source)
    visited_list.append(source)
    while stack:
        vertex = stack.pop()
        print("At vertex :", vertex)
        print("Printing vertex:", vertex)
        for u in input_graph[vertex]:
            if u not in visited_list:
                print("At {}, adding vertex {} to stack and visited list".format(vertex, u))
                stack.append(u)
                visited_list.append(u)
        print("Vertices in visited list are:", visited_list)
        print("Vertices in stack are:", stack)


print("Explanation of DFS traversal of graph with source A is:")
DFS_Algorithm(graph, "A")

Output:

Given Graph is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
Explanation of DFS traversal of graph with source A is:
At A, adding vertex A to stack and visited list
At vertex : A
Printing vertex: A
At A, adding vertex B to stack and visited list
At A, adding vertex D to stack and visited list
At A, adding vertex E to stack and visited list
At A, adding vertex F to stack and visited list
Vertices in visited list are: ['A', 'B', 'D', 'E', 'F']
Vertices in stack are: ['B', 'D', 'E', 'F']
At vertex : F
Printing vertex: F
Vertices in visited list are: ['A', 'B', 'D', 'E', 'F']
Vertices in stack are: ['B', 'D', 'E']
At vertex : E
Printing vertex: E
Vertices in visited list are: ['A', 'B', 'D', 'E', 'F']
Vertices in stack are: ['B', 'D']
At vertex : D
Printing vertex: D
Vertices in visited list are: ['A', 'B', 'D', 'E', 'F']
Vertices in stack are: ['B']
At vertex : B
Printing vertex: B
At B, adding vertex C to stack and visited list
Vertices in visited list are: ['A', 'B', 'D', 'E', 'F', 'C']
Vertices in stack are: ['C']
At vertex : C
Printing vertex: C
Vertices in visited list are: ['A', 'B', 'D', 'E', 'F', 'C']
Vertices in stack are: []

In the output, you can observe that all the vertices are finally present in the visited list and they are printed in the order A, F, E, D, B,C. You can see that the order of vertices is not similar to what we have discussed in the previous section. This is due to the fact that we have many options to choose when we are selecting neighbors of a vertex and the order will depend on the vertex we select.

Implementation of Depth first traversal in Python

As we have discussed the general idea for depth first traversal of a graph and observed how the algorithm works using the python program, we can implement the depth first traversal algorithm as follows.

graph = {'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
print("Given Graph is:")
print(graph)


def dfs_traversal(input_graph, source):
    stack = list()
    visited_list = list()
    stack.append(source)
    visited_list.append(source)
    while stack:
        vertex = stack.pop()
        print(vertex, end=" ")
        for u in input_graph[vertex]:
            if u not in visited_list:
                stack.append(u)
                visited_list.append(u)


print("DFS traversal of graph with source A is:")
dfs_traversal(graph, "A")

Output:

Given Graph is:
{'A': ['B', 'D', 'E', 'F'], 'D': ['A'], 'B': ['A', 'F', 'C'], 'F': ['B', 'A'], 'C': ['B'], 'E': ['A']}
DFS traversal of graph with source A is:
A F E D B C 

Conclusion

In this article, we have discussed the depth first traversal algorithm for a fully connected graph and we have also implemented it in Python. We have used a list as a stack in our implementation but stacks can also be implemented using a linked list in Python. TO read more about other algorithms, you can read this article on In-order tree traversal in Python.

The post Depth First Traversal in Python appeared first on PythonForBeginners.com.

from Planet Python
via read more