Depth-First Search (DFS) is a graph traversal algorithm used to explore nodes and edges in a graph by going as deep as possible along each branch before backtracking. It’s often implemented using a stack or recursion.

**The basic idea behind DFS is as follows:**

- Choose a starting node and push it onto the stack or start the recursive process.
- Pop a node from the stack and visit it.
- Push all of its neighbors onto the stack if they haven’t been visited.
- Mark the visited node as ‘visited.’
- Repeat steps 2-4 until the stack is empty or there are no unvisited nodes reachable from the current node.
- If using recursion, recursively call the function on unvisited neighbors.

## Applications Of DFS Algorithm

The Depth-First Search (DFS) algorithm is a fundamental graph traversal algorithm that has various applications in computer science and real-world scenarios. Some of the key applications of DFS include:

**Topological Sorting:**DFS can be used to perform topological sorting on directed acyclic graphs (DAGs), which is useful in scheduling tasks with dependencies.**Finding Strongly Connected Components:**DFS can be used to find strongly connected components in a directed graph, which is vital in analyzing networks and dependencies.**Detecting Cycles:**DFS can detect cycles in a graph, which is crucial in tasks such as deadlock detection in operating systems or resource allocation systems.**Path Finding:**DFS can be used to find a path between two nodes in a graph, which is essential in navigation and routing problems.**Maze Generation and Solving:**DFS can be used to generate mazes and solve them efficiently.**Detecting Connected Components:**DFS can be used to find connected components in an undirected graph, helping to identify groups of nodes that are connected to each other.**Detecting Bipartite Graphs:**DFS can determine whether a graph is bipartite, which has applications in areas such as task scheduling and assignment problems.**Network Analysis:**DFS is used in the analysis of networks, such as social networks, to identify and analyze communities and connections.**Game Theory and Puzzles:**DFS can be applied to solve puzzles and analyze game states, such as in chess or other board games.

## Algorithm

**Step 1:**SET STATUS = 1 (ready state) for each node in G**Step 2:**Push the starting node A on the stack and set its STATUS = 2 (waiting state)**Step 3:**Repeat Steps 4 and 5 until STACK is empty**Step 4:**Pop the top node N. Process it and set its STATUS = 3 (processed state)**Step 5:**Push on the stack all the neighbors of N that are in the ready state (whose STATUS = 1) and set their STATUS = 2 (waiting state)**Step 6:**EXIT

## Example Of DFS Algorithm

Certainly, here is an example of the Depth-First Search (DFS) algorithm in action. Suppose we have the following graph:

` ````
``` 2
/ \
0 3
\
1

We can represent this graph using an adjacency list:

` ````
```import java.util.*;
class Graph {
private int V;
private LinkedList adj[];
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i) {
adj[i] = new LinkedList();
}
}
void addEdge(int v, int w) {
adj[v].add(w);
}
void DFSUtil(int v, boolean visited[]) {
visited[v] = true;
System.out.print(v + " ");
Iterator i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
DFSUtil(n, visited);
}
}
}
void DFS(int v) {
boolean visited[] = new boolean[V];
DFSUtil(v, visited);
}
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(0, 1);
g.addEdge(3, 3);
System.out.println
("Following is Depth First Traversal " +
"(starting from vertex 2)");
g.DFS(2);
}
}