Posts Depth First Search
Post
Cancel

Depth First Search

Problem Description

You are given a connected undirected graph. Perform a Depth First Traversal of the graph. Note: Use a recursive approach to find the DFS traversal of the graph starting from the 0th vertex from left to right according to the graph.

geeksforgeeks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    // Function to return a list containing the DFS traversal of the graph.
    public ArrayList<Integer> dfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
        
        boolean[] visited = new boolean[V+1];
        
        ArrayList<Integer> ans = new ArrayList<>();
        
        dfs(0, visited, adj, ans);
        
        return ans;
        
    }
    
    
    public void dfs(int s, boolean[] visited, ArrayList<ArrayList<Integer>> adj, ArrayList<Integer> ans){
        
        if(visited[s] == true) return;
        
        visited[s] = true;
        ans.add(s);
        
        ArrayList<Integer> neighbours = adj.get(s);
        
        for(int i=0; i<neighbours.size(); i++){
            dfs(neighbours.get(i), visited, adj, ans);
        }
        
    } 
    
}
This post is licensed under CC BY 4.0 by the author.