Generic Template:

void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited) {

    visited[node] = true;              // Mark current node as visited

    // Process the current node
    // cout << node << " ";

    for (int neighbor : adj[node]) {   // Visit all adjacent nodes

        if (!visited[neighbor]) {

            dfs(neighbor, adj, visited);
        }
    }
}

int n = adj.size();

vector<bool> visited(n, false);

dfs(start, adj, visited);

Variations

DFS on a GRID

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

void dfs(int row, int col) {

    visited[row][col] = true;

    for (int k = 0; k < 4; k++) {

        int nr = row + dr[k];
        int nc = col + dc[k];

        if (nr >= 0 && nr < NumberOfRows &&
            nc >= 0 && nc < NumberOfCols &&
            !visited[nr][nc]) {

            dfs(nr, nc);
        }
    }
}

Cycle Detection in an Undirected Graph (DFS)

bool dfs(int node,
         int parent,
         vector<vector<int>>& adj,
         vector<bool>& visited) {

    visited[node] = true;

    for (int neighbor : adj[node]) {

        if (!visited[neighbor]) {

            if (dfs(neighbor, node, adj, visited))
                return true;
        }

        else if (neighbor != parent) {

            return true;
        }
    }

    return false;
}

Driver

vector<bool> visited(V, false);

for (int i = 0; i < V; i++) {

    if (!visited[i]) {

        if (dfs(i, -1, adj, visited))
            return true;
    }
}

return false;

Cycle Detection in a Directed Graph (DFS)

bool dfs(int node,
         vector<vector<int>>& adj,
         vector<bool>& visited,
         vector<bool>& pathVisited) {

    visited[node] = true;
    pathVisited[node] = true;

    for (int neighbor : adj[node]) {

        if (!visited[neighbor]) {

            if (dfs(neighbor, adj, visited, pathVisited))
                return true;
        }

        else if (pathVisited[neighbor]) {

            return true;
        }
    }

    pathVisited[node] = false;

    return false;
}

Driver

vector<bool> visited(V, false);
vector<bool> pathVisited(V, false);

for (int i = 0; i < V; i++) {

    if (!visited[i]) {

        if (dfs(i, adj, visited, pathVisited))
            return true;
    }
}

return false;

Applications

1. Puzzles and state exploration
2. Graph Colouring
3. Recursive Traversal
4. Backtracking