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)