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.

**For a single component**:

```
class Solution {
// Function to return a list containing the DFS traversal of the graph.
public ArrayList<Integer> dfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
// Code here
ArrayList<Integer> dfs = new ArrayList<>();
boolean visited[] = new boolean[V];
if(!visited[0])
dfsUtil(0,dfs,adj,visited);
return dfs;
}
public void dfsUtil(int node, ArrayList<Integer> dfs, ArrayList<ArrayList<Integer>> list,
boolean[] visited){
dfs.add(node);
visited[node] = true;
List<Integer> deepNodes = list.get(node);
for(Integer n : deepNodes){
if(!visited[n])
dfsUtil(n,dfs,list,visited);
}
}
}
```

**For more than one component**:

Time complexity : O(n) +O(n) i.e. O(n) for runnig for loop and another o(n) for `dfsUtil()`

(remember the TC is not O(n^2) as `dfsUtil()`

will not be called for every iteration in the for loop, it will be called only if there are other component, as in single `dfsUtil()`

call all the nodes in that components will be visited.

```
class Solution {
// Function to return a list containing the DFS traversal of the graph.
public ArrayList<Integer> dfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
// Code here
ArrayList<Integer> dfs = new ArrayList<>();
boolean visited[] = new boolean[V];
for(int i =0;i<V;i++)
if(!visited[i])
dfsUtil(i,dfs,adj,visited);
return dfs;
}
public void dfsUtil(int node, ArrayList<Integer> dfs, ArrayList<ArrayList<Integer>> list,
boolean[] visited){
dfs.add(node);
visited[node] = true;
List<Integer> deepNodes = list.get(node);
for(Integer n : deepNodes){
if(!visited[n])
dfsUtil(n,dfs,list,visited);
}
}
}
```

## Top comments (0)