Implement depth-first search (DFS) on a graph.

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking.

Algorithm Steps:

Initialize a set or array to keep track of visited vertices.
Choose a starting vertex and mark it as visited.
For each unvisited neighbor of the current vertex:
- Recursively call DFS on the neighbor (or push it onto the stack in the stack-based approach).
- Mark the neighbor as visited.
Repeat the process until all reachable vertices are visited.
The time complexity of DFS is O(V + E), where V is the number of vertices and E is the number of edges. Each vertex and edge are visited once.

DFS Implementation C++

#include <iostream>
#include <vector>

class Graph {
private:
    int vertices;
    std::vector<std::vector<int>> adjacencyList;

public:
    Graph(int v) : vertices(v), adjacencyList(v) {}

    void addEdge(int u, int v) {
        adjacencyList[u].push_back(v);
        adjacencyList[v].push_back(u); // For an undirected graph
    }

    void dfs(int startVertex, std::vector<bool>& visited) {
        visited[startVertex] = true;
        std::cout << startVertex << " ";

        for (int neighbor : adjacencyList[startVertex]) {
            if (!visited[neighbor]) {
                dfs(neighbor, visited);
            }
        }
    }

    void performDFS(int startVertex) {
        std::vector<bool> visited(vertices, false);
        dfs(startVertex, visited);
    }
};

int main() {
    // Create a sample graph
    Graph graph(7);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 5);
    graph.addEdge(2, 6);

    // Perform DFS starting from vertex 0
    std::cout << "DFS starting from vertex 0: ";
    graph.performDFS(0);
    std::cout << std::endl;

    return 0;
}

Output:

DFS starting from vertex 0: 0 1 3 4 2 5 6