Depth First Search (DFS) in python

Published on : 6th Oct 2021
Depth First Search (DFS) :
DFS is an algorithm for traversing a graph. We start from an arbitrary node. After that, we explore its adjacent node as far as possible then backtrack. Not to visit a node again, we mark the node as visited. We do this until all nodes explore.


Source code :  
from collections import defaultdict

class Graph:
    def __init__(self, V):
        self.V = V
        self.adj_list = defaultdict(list)

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

    def dfs(self, u, visited, parent):
        visited[u] = True
        print(u, end=" ")

        for v in self.adj_list[u]:
            if not visited[v]:
                self.dfs(v, visited, parent)
                parent[v] = u

def main():
    V = int(input("Enter the no. of vertices: "))
    E = int(input("Enter the no. of edges: "))
    graph = Graph(V)

    for e in range(E):
        u, v = list(map(int, input(f"Enter src and dist vertices respectively for edge {e+1}: ").split(' ')))
        graph.add_edge(u, v)

    print("DFS tree: ", end="")
    visited = [False] * V
    parent = [-1] * V
    for v in range(V):
        if not visited[v]:
            graph.dfs(v, visited, parent)

    print()


if __name__ == '__main__':
    main()
Output :
Enter the no. of vertices: 6
Enter the no. of edges: 5
Enter src and dist vertices respectively for edge 1: 0 4
Enter src and dist vertices respectively for edge 2: 0 3
Enter src and dist vertices respectively for edge 3: 0 1
Enter src and dist vertices respectively for edge 4: 1 2
Enter src and dist vertices respectively for edge 5: 3 4
DFS tree: 0 4 3 1 2 5 