## 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;

Graph(int V){
this.V = V;
for(int v = 0;v<V;v++)
}

public void addEdge(int v, int w){
E++;
}

}

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;
}
}

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

//#2

//#3

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```