Tuesday, 29 August 2017

DFS Implementation in Python

Depth First Search (DFS) algorithm is used to traverse a graph depthward motion. DFS Algorithm use data structure stack to remember to get the next vertex to start the search and we will requred an array to keep the track of vertex that it is visited or unvisited.



In DFS traversal we look start from the sorce, then we look for the adjacent unvisited vertices of the source. We display them, mark them visited and put them into the stack. If there is not remain any adjacent vertex which is unvisited. Then, we popped out the top element of the stack and do the same for the popped out element. We will repeat the same till the stack becomes empty.

Algorithm:


1. Display the source vertex and mark it as visited.
2. push the sourve vertex to the STACK
3. do While STACK is not empty:
4.      set: source=STACK.top()
5.      Update Stack by pop out top element of stack
6.    do For i=1 to n:
7.     If graph_matrix[source][i]=1 and vertex_status[i]=unvisited:
8.                    Display vertex 'i' and mark it as visited
9.                    Push the vertex 'i' to the STACK
10.    EndFor
11. EndWhile


PROGRAM:

from collections import defaultdict

class graph:
 def __init__(self):
  self.graph=defaultdict(list)

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

 def DFS(self,s):
  stack=[]
  visited=[False for i in range(len(self.graph))]
  visited[s]=True
  stack.append(s);
  while stack:
   source=stack.pop()
   print(source,end=' ')
   for j in self.graph[source]:
    if visited[j]==False:
     stack.append(j);
     visited[j]=True

g=graph()
g.add_edge(0,1)
g.add_edge(0,2)
g.add_edge(1,3)
g.add_edge(2,3)
g.add_edge(3,4)
g.add_edge(4,5)
print("\n\n\nThe DFS traversal of the Graph is:\n\n")
g.DFS(1)
print("\n\n")


OUTPUT:




EmoticonEmoticon