DFS of Graph | GeeksforGeeks solution

 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 from left to right according to the graph..

Example 1:

Input:

Output: 0 1 2 4 3
Explanation: 
0 is connected to 1, 2, 4.
1 is connected to 0.
2 is connected to 0.
3 is connected to 4.
4 is connected to 0, 3.
so starting from 0, it will go to 1 then 2
then 4, and then from 4 to 3.
Thus dfs will be 0 1 2 4 3.

Example 2:

Input:

Output: 0 1 2 3
Explanation:
0 is connected to 1 , 3.
1 is connected to 2. 
2 is connected to 1.
3 is connected to 0. 
so starting from 0, it will go to 1 then 2
then back to 0 then 0 to 3
thus dfs will be 0 1 2 3. 

Your task:
You dont need to read input or print anything. Your task is to complete the function dfsOfGraph() which takes the integer V denoting the number of vertices and adjacency list as input parameters and returns  a list containing the DFS traversal of the graph starting from the 0th vertex from left to right according to the graph.

Expected Time Complexity: O(V + E)
Expected Auxiliary Space: O(V)

Constraints:
1 ≤ V, E ≤ 104

Ans: 

   In DFS , we first travel the first given or starting vertex and then anyone vertex adjacent to it. now we traverse other vertex adjacent to second vertex i.e we go into the depth .

code for DFS is :

class Solution {

  public:

    // Function to return a list containing the DFS traversal of the graph.

   void dfs(int v , vector<int>adj[] , vector<bool>&visited ,vector<int>&ans)

   {

       visited[v] = true;

       ans.push_back(v);

       for(int i : adj[v])

       {

           if(!visited[i])

           {

               dfs(i , adj , visited , ans);

           }

       }

       

   }

    vector<int> dfsOfGraph(int V, vector<int> adj[]) {

         

         vector<int>ans;

         vector<bool>visited(V , false);

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

         {

             if(!visited[i])

             {

                 dfs(i , adj , visited , ans);

             }

         }

         return ans;

    }

    

};

References: https://practice.geeksforgeeks.org/problems/depth-first-traversal-for-a-graph/1