DFS of Graph

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:
         0
        / \\
       1  2 4
             \
              3


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 0.
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:
               0
              / \
             1   3
             /
            2


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. 

• method
   Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch. So the basic idea is to start from the root or any arbitrary node and mark the node and move to the adjacent unmarked node and continue this loop until there is no unmarked adjacent node. Then backtrack and check for other unmarked nodes and traverse them. Finally print the nodes in the path.
  
  
• Algorithm: 
  1. Create a recursive function that takes the index of node and a visited array.
  2. Mark the current node as visited and print the node.
  3. Traverse all the adjacent and unmarked nodes and call the recursive function with index of adjacent node.

c++ implementation:

// { Driver Code Starts
#include<bits/stdc++.h>
using namespace std;

 // } Driver Code Ends


class Solution 
{
    public:
//the main dfs program starts from here
vector <int> dfsOfGraph(int N,vector<int> g[])
{ 
bool vis[N];   vector<int> m;
for(int i=0;i<N;i++)
vis[i]=0;

int k;
for(k=0;k<N;k++)
if(vis[k]==0)
dfsui(k,g,vis);

return m;
}
void dfsui(int source, vector<int> g[], bool vis[])
{
     vis[source] = true;
     cout<<source<<" ";

    for(auto i:g[source])
    {
      if(!vis[i])
      dfsui(i, g, vis);
    }
    
}
//ends here
};

// { Driver Code Starts.
int main(){
	int tc;
	cin >> tc;
	while(tc--){
		int V, E;
    	cin >> V >> E;

    	vector<int> adj[V];

    	for(int i = 0; i < E; i++)
    	{
    		int u, v;
    		cin >> u >> v;
    		adj[u].push_back(v);
    		adj[v].push_back(u);
    	}
        // string s1;
        // cin>>s1;
        Solution obj;
        vector<int>ans=obj.dfsOfGraph(V, adj);
        for(int i=0;i<ans.size();i++){
        	cout<<ans[i]<<" ";
        }
        cout<<endl;
	}
	return 0;
}  // } Driver Code Ends

• Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
• Space Complexity :O(V). 
  Since an extra visited array is needed of size V.