DEV Community

Prashant Mishra

Posted on • Originally published at practice.geeksforgeeks.org

Depth first search GeeksForGeeks

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])
return dfs;
}
public void dfsUtil(int node, ArrayList<Integer> dfs, ArrayList<ArrayList<Integer>> list,
boolean[] visited){
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])

return dfs;
}
public void dfsUtil(int node, ArrayList<Integer> dfs, ArrayList<ArrayList<Integer>> list,
boolean[] visited){
visited[node] = true;
List<Integer> deepNodes = list.get(node);
for(Integer n : deepNodes){
if(!visited[n])
dfsUtil(n,dfs,list,visited);
}
}
}
``````