DFS of Graph

Problem Statement - link #

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..

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)

Examples #

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.

Constraints #

• 1 ≤ V, E ≤ 10^4

Solutions #

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