Basic Code Snippet for "DFS(Depth First Search)" in java

Problem statement - Given an undirected graph, you have to find the number of connected components in the graph.

Example - Given n (no of vertices) - 5 and
Edges[][] - { [0,1] , [2,3] , [3,4] }
Result for this case - 2 -> { [0,1] , [2,3,4] }

One of the possible solutions is to use DFS here.

DFS code -

class Solution {

public void dfs(List<Integer>[] adjList, boolean[] visited, int node){
    visited[node]= true;
    
    // explore node's all neighbors
    for(int neighbor: adjList[node]){
        if(!visited[neighbor]){
            dfs(adjList,visited,neighbor);
        }
    }
}
public int countComponents(int n, int[][] edges) {
    // dfs solution
    boolean[] visited= new boolean[n]; //  array to keep track of visited node
    List<Integer>[] adjList= new ArrayList[n];  // array of list to store graph
    
    for(int i=0;i<n;i++){
        adjList[i]=new ArrayList<Integer>();
    }
    
    // create adjacency list / graph
    for(int i=0;i<edges.length;i++){
        adjList[edges[i][0]].add(edges[i][1]);
        adjList[edges[i][1]].add(edges[i][0]);   // since it is undirected
    }
    
    int components=0;
    for(int i=0;i<n;i++){
        if(!visited[i]){
            components++;
			// start the dfs
            dfs(adjList,visited,i);
        }
    }
    
    return components;
}

}

Comments (0)