# 1. Introduction

Depth-First Search (DFS) is a fundamental graph traversal technique that explores nodes as profoundly as possible along each branch before backtracking. It is extensively used in numerous applications, from detecting cycles in graphs to topological sorting. In this post, we'll walk you through a basic implementation of DFS in C++.

# 2. Program Overview

Our program will:

1. Define a Graph class that represents an undirected graph using an adjacency list.

2. The Graph class will have functions to:

- Add an edge to the graph.

- Perform DFS traversal from a given starting vertex.

3. Demonstrate DFS traversal in the main program.

# 3. Code Program

``````#include<iostream>
#include<list>
using namespace std;

class Graph {
int V;  // Number of vertices

// Recursive function for DFS
void DFSUtil(int v, bool visited[]) {
visited[v] = true;
cout << v << " ";

// Recur for all the vertices adjacent to this vertex
if(!visited[*i]) {
DFSUtil(*i, visited);
}
}
}

public:
// Constructor
Graph(int V) {
this->V = V;
}

// Add an edge to the graph
void addEdge(int v, int w) {
}

// DFS traversal
void DFS(int v) {
// Mark all vertices as not visited
bool *visited = new bool[V];
for(int i = 0; i < V; i++) {
visited[i] = false;
}

// Call the recursive function
DFSUtil(v, visited);
}
};

int main() {
Graph g(4);  // Create a graph with 4 vertices

cout << "Depth First Traversal starting from vertex 2:" << endl;
g.DFS(2);

return 0;
}
``````

### Output:

```Depth First Traversal starting from vertex 2:
2 0 1 3
```

# 4. Step By Step Explanation

1. The Graph class represents an undirected graph using an adjacency list.

2. We use a list from the STL to manage the adjacency list for each vertex.

3. The DFSUtil is a recursive function that uses the DFS algorithm to explore all the adjacent vertices of the given vertex.

4. The DFS method initializes a visited array to keep track of visited vertices and calls DFSUtil.

5. In the main function, we create a graph with 4 vertices, add edges to the graph, and then demonstrate DFS starting from vertex 2.