### Depth-First Search (DFS) in Graph

Welcome to our beginner's guide to Depth-First Search (DFS) in Graph Theory! DFS is another fundamental algorithm used to traverse or search through the nodes of a graph in a systematic manner. Let's explore this fascinating algorithm together!

## What is Depth-First Search (DFS)?

Depth-First Search is an algorithm used to traverse or search through the nodes of a graph in a depthward motion. It starts at a specific node (often referred to as the "source" node) and explores as far as possible along each branch before backtracking.

Imagine you're exploring a maze again. DFS would explore as far as possible along one path before backtracking and exploring another path.

## How does DFS Work?

DFS employs a simple strategy of exploring nodes as deeply as possible along each branch before backtracking. The algorithm proceeds as follows:

- Start with the source node and mark it as visited.
- Explore one of the unvisited neighbors of the source node.
- If an unvisited neighbor is found, recursively apply steps 1 and 2 to it.
- If no unvisited neighbors are found, backtrack to the previous node and repeat step 2.
- Repeat steps 1-4 until all reachable nodes are visited.

## Exploring Depth-First Search (DFS) with an Example

Depth-First Search (DFS) is a fundamental graph traversal technique. We'll demonstrate it using a simple graph structure:

A / \ B - C / \ \ D - E - F

In this graph, we have the following connections:

**A**is linked to**B**and**C**.**B**is linked to**A**,**D**, and**E**.**C**is linked to**A**and**F**.**D**is linked to**B**and**E**.**E**is linked to**B**,**D**, and**F**.**F**is linked to**C**and**E**.

We begin our DFS traversal from node **A**.

**DFS Traversal Steps:**

**Note:**When we call something recursively, it uses the stack for execution and backtracking.

- Initiate at Node
**A**(Starting Point): - Mark
**A**as visited. - Visited: [A],Recursion Stack: [A]
- Explore unvisited adjacent nodes:
- Move to
**B**, mark as visited. - Visited: [A, B], Stack: [A, B]
- Continue exploring adjacent nodes:
- Proceed to
**D**, mark as visited. - Visited: [A, B, D], Stack: [A, B, D]
- Explore further adjacent nodes:
- Visit
**E**, mark as visited. - Visited: [A, B, D, E], Stack: [A, B, D, E]
- Continue exploration:
- Go to
**F**, mark as visited. - Visited: [A, B, D, E, F], Stack: [A, B, D, E, F]
- Visit
**C**, mark as visited. - Visited: [A, B, D, E, F, C], Stack: [A, B, D, E, F, C]

A / \ B - C / \ \ D - E - F

A / \ B - C / \ \ D - E - F

A / \ B - C / \ \ D - E - F

A / \ B - C / \ \ D - E - F

A / \ B - C / \ \ D - E - F

A / \ B - C / \ \ D - E - F

And at the end Stack: [A, B, D, E, F, C] get backtracked from recurssion.

**Output:** Nodes visited in DFS order: A, B, D, E, F, C

**Time Complexity:**

The time complexity of DFS is O(V + E), where V represents the number of vertices and E the number of edges in the graph.

**Space Complexity:**

The space complexity of DFS, in the worst-case scenario, is O(V), considering V as the number of vertices.

## Implementing DFS in Code

Now, let's take a look at how we can implement Depth-First Search in code. We'll provide examples in several programming languages to help you get started:

```
package codeKatha;
import java.util.*;
public class DFS {
public void depthFirstSearch(Graph graph, Node source) {
Set<Node> visited = new HashSet<>();
dfsHelper(source, visited, graph);
}
private void dfsHelper(Node node, Set<Node> visited, Graph graph) {
visited.add(node);
System.out.println(node);
for (Node neighbor : graph.getNeighbors(node)) {
if (!visited.contains(neighbor)) {
dfsHelper(neighbor, visited, graph);
}
}
}
}
```

```
#include <iostream>
#include <unordered_set>
#include "Graph.h"
void DFS(Node& node, std::unordered_set<Node>& visited, Graph& graph) {
visited.insert(node);
std::cout << node << std::endl;
for (Node neighbor : graph.getNeighbors(node)) {
if (visited.find(neighbor) == visited.end()) {
DFS(neighbor, visited, graph);
}
}
}
```

```
class DFS:
def depth_first_search(self, graph, node, visited):
visited.add(node)
print(node)
for neighbor in graph.get_neighbors(node):
if neighbor not in visited:
self.depth_first_search(graph, neighbor, visited)
```

```
class DFS {
depthFirstSearch(node, visited, graph) {
visited.add(node);
console.log(node);
for (let neighbor of graph.getNeighbors(node)) {
if (!visited.has(neighbor)) {
this.depthFirstSearch(neighbor, visited, graph);
}
}
}
}
```

## Graph: Concept and Important Algorithms

1. Basics of Graph Data Structure2. Breadth-First Search (BFS) in Graph

3. Depth-First Search (DFS) in Graph

4. Topological Sort in Graph

5. Union-Find Algorithm in Graph

6. Prim's Algorithm in Graph

7. Dijkstra's Algorithm in Graph

8. Kruskal's Algorithm in Graph

Congratulations! You've now learned the basics of Depth-First Search in graph theory. Feel free to experiment with the provided code examples and explore further applications of DFS in your projects.

## Comments

## Post a Comment