Problem Statement

Given a connected undirected graph. Perform a Depth First Traversal of the graph.

Note: Use recursive approach to find the DFS traversal of the graph starting from the 0th vertex.

Problem Link

DFS of Graph | Practice | GeeksforGeeks

Code

class Solution 
{
    public:
	//Function to return a list containing the DFS traversal of the graph.
	vector<int>dfsOfGraph(int V, vector<int> adj[])
	{
	    vector<bool> visited(V,false);
	    vector<int> res;
	    for(int i=0;i<V;i++)
	    {
	        if(!visited[i])
	        dfs(i,adj,visited,res);
	    }
	    
	    return res;
	}
	
	void dfs(int u,vector<int> adj[],vector<bool> &visited,vector<int> &res)
	{
	    if(visited[u])
	    return;
	    
	    visited[u] = true;
	    res.push_back(u);
	    
	    for(int v:adj[u])
	    {
	        if(!visited[v])
	        dfs(v,adj,visited,res);
	    }
	}
};