Depth First Search is a recursive algorithm used to traverse a Graph. The algorithm starts with an arbitrary node(in case of a graph) and traverses all the nodes of the graph in a depth-first manner. It uses a stack to store the intermediate visited nodes.

Since it is a recursive algorithm, it uses visited array of size = no. of nodes in the graph, which checks if we have already visited that particular node of not. It contains the value 0/1 or True/False and prevents the algorithm from falling into an infinite loop.

The graph can be represented as Adjacency List or Adjacency Matrix.

**Algorithm**

- Start from a given node(or any arbitrary node, if nothing is given), mark it visited, and push it onto the stack.
- Visit the next adjacent unvisited node of the current node, mark it visited, and push it into the stack.
- If all adjacent nodes of the current node are visited, go back to the parent, visit the remaining adjacent nodes of the parent node.
- If all nodes are visited, then stop.

```
int DFS(vector<vector<int> > &graph, int v){
if(visited[v] ==1)
return 0;
visited[v] = 1;
cout<<v<<" ";
for(int i=0; i<graph[v].size(); i++)
DFS(graph,graph[v][i]);
return 0;
}
```

**Implementation of the above algorithm in CPP**

```
Output:
```*Nodes are visited using DFS in the following order: 1 6 3 2 5 4*

The time complexity of the above algorithm is O(E+V), where E is total no. of edges and V is total no. of vertices.

**Applications of DFS**

- Shortest Path and Minimum Spanning Tree for unweighted graph
- Topological Sorting
- Test if a graph is bipartite
- Finding connected components.
- Solving puzzles with only one solution, such as mazes.