# 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)

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()