Friday, November 27, 2015

Finding Connected Components using DFS

Java implementation for finding the connected components in an undirected graph using DFS.

import java.util.ArrayList;

class Graph{
    
    private final int V;
    private int E;
    
    private ArrayList<ArrayList<Integer>> adj;
    
    Graph(int V){
        this.V = V;
        adj = new ArrayList<>();
        for(int v = 0;v<V;v++)
            adj.add(new ArrayList<>());
    }
    
    public void addEdge(int v, int w){
        adj.get(v).add(w);
        adj.get(w).add(v);
        E++;
    }
    
    public Iterable<Integer> adj(int v){
        return adj.get(v);
    } 
    
    int V(){return V;}
    
    int E(){return E;} 
    
} 

public class ConnectedComponents {
    
    //Component Group ID
    private static int GID = 0;
    private static boolean visited[];
    private static int id[];
    
    public static int nComponents(){
        return GID;
    }
    
    public static void dfs(Graph G, int v){
        if(!visited[v]) { 
            visited[v] = true;
            id[v] = GID;
            for(int w:G.adj(v))dfs(G, w);
        }
    }
    
    public static void findComponents(Graph G){
        visited = new boolean[G.V()];
        id = new int[G.V()];
        
        for(int i=0;i<G.V();++i){
            if(!visited[i]){
                ++GID;
                dfs(G, i);
            }
        }
    }
    
    public static void main(String[] args){
        Graph G = new Graph(11);
        
        //Connected Components #1
        G.addEdge(0, 10);
        G.addEdge(0, 9);
        G.addEdge(0, 5);
        G.addEdge(10, 5);
        G.addEdge(10, 9);
        
        //#2
        G.addEdge(6, 8);
        G.addEdge(8, 7);
        
        //#3
        G.addEdge(1, 2);
        G.addEdge(2, 3);
        G.addEdge(1, 3);
        G.addEdge(3, 4);
        
        findComponents(G);
        System.out.println("Number of connected components : "+nComponents());
       
        System.out.println("Printing the results...");
        for(int i=0;i<G.V();++i){
            System.out.println("Vertex "+i+" CC : "+id[i]);
        }
        
        System.out.println("\nRunning tests...");
        System.out.println("Vertices 1 and 0 in the same CC? : "+(id[1]==id[0]));
        System.out.println("Vertices 0 and 9 in the same CC? : "+(id[0]==id[9]));
        System.out.println("Vertices 1 and 4 in the same CC? : "+(id[1]==id[4]));
        System.out.println("Vertices 3 and 6 in the same CC? : "+(id[3]==id[6]));
        System.out.println("Vertices 6 and 8 in the same CC? : "+(id[6]==id[8]));
    }
}

Output:

Number of connected components : 3
Printing the results...
Vertex 0 CC : 1
Vertex 1 CC : 2
Vertex 2 CC : 2
Vertex 3 CC : 2
Vertex 4 CC : 2
Vertex 5 CC : 1
Vertex 6 CC : 3
Vertex 7 CC : 3
Vertex 8 CC : 3
Vertex 9 CC : 1
Vertex 10 CC : 1

Running tests...
Vertices 1 and 0 in the same CC? : false
Vertices 0 and 9 in the same CC? : true
Vertices 1 and 4 in the same CC? : true
Vertices 3 and 6 in the same CC? : false
Vertices 6 and 8 in the same CC? : true

No comments:

Post a Comment