Depth-First Search

🔁 Quick BFS Recap
In Breadth-First Search (BFS), you explore the graph level by level.
🧠 Think of it like:
You’re standing in a room and shout, “Who’s next to me?”
You visit all immediate neighbors first, then move on to their neighbors, and so on.
📦 Uses a queue (FIFO)
✅ Best for shortest path in unweighted graphs
🌐 Real-life: friend suggestions, web crawling, peer-to-peer networks

Now, Let’s Dive into DFS – Depth-First Search

No more level-by-level. It’s time to go DEEP!
In DFS, you pick a path and go as deep as possible, only backtracking when there’s nowhere left to go.
🧠 Imagine: You enter a maze and just keep walking forward till you hit a dead-end, then backtrack and explore the next path.
📦Uses recursion or a stack
✅ Best for:
Exploring complete paths
Detecting cycles
Maze solving
Topological sort

📘 What is DFS?
Depth-First Search (DFS) is a classic graph traversal algorithm.
Instead of exploring layer by layer like BFS, it dives deep into each branch of a graph or tree before backtracking.

🧠 How It Works:
Start from a node (e.g., node 0).
Use a stack (or recursion) to track your path.
Keep a visited[] array to avoid revisiting nodes.
For each node:
Visit it.
Dive into its first unvisited neighbor.
Repeat until stuck, then backtrack.
📥 Stack behavior: Last in, first out (LIFO) — perfect for going deep before backtracking!

🧠 Graph Structure (Adjacency List based on the image):
From the graph:
1: [2, 3]
2: [1, 4]
3: [1, 5]
4: [2, 5]
5: [3, 4]

We’ll assume:
It’s an undirected graph.
DFS starts from node 1.

✅ Dry Run of DFS
Step-by-Step (Recursive DFS)
Start at 1, mark visited → dfs = [1]
Go to neighbor 2 (first unvisited of 1) → dfs = [1, 2]
Go to neighbor 4 (from 2) → dfs = [1, 2, 4]
Go to neighbor 5 (from 4) → dfs = [1, 2, 4, 5]
Go to neighbor 3 (from 5) → dfs = [1, 2, 4, 5, 3]
All neighbors visited. Backtrack until all paths are done.

🔄 Final DFS Traversal Order:
1 → 2 → 4 → 5 → 3

✅ DFS Code in C++

#include <iostream>
#include <vector>
using namespace std;

// Helper method to perform DFS recursively
void dfsHelper(int node, vector<int> adj[], vector<bool>& visited, vector<int>& dfs) {
    visited[node] = true;
    dfs.push_back(node);

    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfsHelper(neighbor, adj, visited, dfs);
        }
    }
}

// DFS function that calls the helper
vector<int> dfsOfGraph(int V, vector<int> adj[]) {
    vector<int> dfs;
    vector<bool> visited(V, false);
    dfsHelper(0, adj, visited, dfs); // starting from node 0
    return dfs;
}

int main() {
    int V = 5;
    vector<int> adj[V];


    // 1-2, 1-3, 2-4, 3-5, 4-5
    adj[0] = {1, 2};    // node 1 -> 2, 3
    adj[1] = {0, 3};    // node 2 -> 1, 4
    adj[2] = {0, 4};    // node 3 -> 1, 5
    adj[3] = {1, 4};    // node 4 -> 2, 5
    adj[4] = {2, 3};    // node 5 -> 3, 4

    vector<int> result = dfsOfGraph(V, adj);

    cout << "DFS Traversal: ";
    for (int node : result)
        cout << node + 1 << " ";  
    cout << endl;

    return 0;
}