Depth-First Search on Graph

DFS.cpp

// C++ program to print DFS traversal from a given vertex in a  given graph
#include <iostream>
#include <vector>
 
using namespace std;
 
// Graph class represents a directed graph using adjacency vector representation
class Graph {
    int V;    // No. of vertices
    void DFSUtil(int v, bool visited[]);  // A function used by DFS
    vector<vector<int>> adj;    // Pointer to an array containing adjacency vectors
    vector<int> size(V);
public:
    Graph(int V);   // Constructor
    void addEdge(int v, int w);   // function to add an edge to graph
    void DFS(int v);    // DFS traversal of the vertices reachable from v
};
 
Graph::Graph(int V) {
    this->V = V;
    vector<vector<int>> adj;

    for (int i = 0; i < V; i++) {
        vector<int> row(V);
        adj.push_back(row);
        for (int j = 0; j < V; j++) {
            adj[i][j] = 0;
        }
    }
    this -> adj = adj;
}
 
void Graph::addEdge(int v, int w) {
    adj[v][w] = 1;
    adj[w][v] = 1;

}
 
void Graph::DFSUtil(int v, bool visited[]) {

    // Mark the current node as visited and print it
    visited[v] = true;
    // Recur for all the vertices adjacent to this vertex
    for (int i = 0; i < adj.size(); i++)
        if ((adj[v][i] != 0) && !visited[i]) {
            DFSUtil(i, visited);
        }
    
}
 
// DFS traversal of the vertices reachable from v. 
// It uses recursive DFSUtil()
void Graph::DFS(int v)
{
    // Mark all the vertices as not visited
    bool visited[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;
 
    // Call the recursive helper function to print DFS traversal
    DFSUtil(v, visited);

    return;
}
 
int main() {
    // Create a graph given in the above diagram
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(3, 0);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
    g.addEdge(5, 4);

    cout << "Following is Depth First Traversal (starting from vertex 2) \n";
    g.DFS(2);
 
    return 0;
}