DFS traversal is one of the other techniques to traverse the whole graph. The most useful case of DFS is finding a cycle in a graph.

For DFS we need to create an array of size n (number of vertices) and initialize every value of it to False. We mark all the vertices from 0 to n-1 for ease of understanding.

The basic concept for DFS is to traverse all the vertices in the graph, check if it is already visited. If Visited move on to next vertex otherwise mark it as visited and move to other vertice which is connected to this.

We have the following graph to DFS traversal.

In this graph, it is not possible to reach from each vertex to any other vertex (e.g. 3 to 0).

We make a dictionary of all the vertices which contains a list of all the vertices with which it connects.

0 : [1, 2]
1 : [2]
2 : [0, 3]
3 : [3]

We iterate over the dictionary and check if the index value vertex is already visited or not. If it is not visited then we check if vertices in the list are already visited or not and so on.

def DFSAll(self,visited,v):
visited[v]=True
print v,
for nextVertex in self.graph[v]:
if not visited[nextVertex]:
self.DFSAll(visited,nextVertex)

def DFSAllNotConnected(self):
visited = [False]*len(self.graph)
for vertex in self.graph:
if not visited[vertex]:
self.DFSAll(visited,vertex)

We call DFSAllNotConnected with the graph. Then it calls to DFSAll which calls itself recursively for all the edges for the vertex.

If we have a connected graph then we don’t need to go through all the indexes of the graph . We can start with any vertex and it will lead to traversing all the vertex as all the vertex are reachable from this one.

Time Complexity

The time complexity for this is O(V+E). V is the number of vertices and E is the number of edges in the graph.

Use OF DFS

DFS is used in traversing the graph, and finding the cycle in the graph.

Source Code

Source code for the implementation of this can be found here.