DFS Traversal

# Day 7

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.

dfs1
Image: 1

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s