Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Compute the number of connected components of an undirected graph
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/**
* This class will compute the number of connected components of an un-directed graph. If graph is fully connected than it will return 1.
*
* @author buraktas
*
*/
public class CountConnectedComponents {
public int countConnectedComponents(ArrayList<Vertex> graph) {
initGraphVertice(graph);
int count = 0;
for (Vertex vertex : graph) {
if (!vertex.isExplored()) {
count++;
bfs(graph, vertex);
}
}
return count;
}
private void bfs(ArrayList<Vertex> graph, Vertex source) {
initSourceVertex(source);
Queue<Vertex> queue = new LinkedList<>();
queue.add(source);
while (!queue.isEmpty()) {
Vertex u = queue.poll();
for (Vertex vertex : u.getAdjList()) {
if (!vertex.isExplored()) {
vertex.setExplored(true);
vertex.setParent(u);
queue.add(vertex);
}
}
}
}
// make all vertice unexplored
private void initGraphVertice(ArrayList<Vertex> graph) {
for (Vertex vertex : graph) {
vertex.setExplored(false);
}
}
// make the source vertex unexplored
private void initSourceVertex(Vertex source) {
source.setExplored(true);
}
}
import static org.junit.Assert.assertEquals;
import java.util.ArrayList;
import java.util.Arrays;
import org.junit.Before;
import org.junit.Test;
public class CountConnectedComponentsTest {
private CountConnectedComponents testClass;
private ArrayList<Vertex> graph;
@Before
public void setUp() {
testClass = new CountConnectedComponents();
graph = new ArrayList<>();
}
@Test
public void testWithThreeConnectedComponents() {
Vertex v1 = new Vertex("v1");
Vertex v2 = new Vertex("v2");
Vertex v3 = new Vertex("v3");
Vertex v4 = new Vertex("v4");
Vertex v5 = new Vertex("v5");
Vertex v6 = new Vertex("v6");
Vertex v7 = new Vertex("v7");
Vertex v8 = new Vertex("v8");
Vertex v9 = new Vertex("v9");
Vertex v10 = new Vertex("v10");
v1.setAdjList(new ArrayList<>(Arrays.asList(v3, v5)));
v2.setAdjList(new ArrayList<>(Arrays.asList(v4)));
v3.setAdjList(new ArrayList<>(Arrays.asList(v1, v5)));
v4.setAdjList(new ArrayList<>(Arrays.asList(v2)));
v5.setAdjList(new ArrayList<>(Arrays.asList(v1, v3, v7, v9)));
v6.setAdjList(new ArrayList<>(Arrays.asList(v8, v10)));
v7.setAdjList(new ArrayList<>(Arrays.asList(v5, v9)));
v8.setAdjList(new ArrayList<>(Arrays.asList(v6, v10)));
v9.setAdjList(new ArrayList<>(Arrays.asList(v5)));
v10.setAdjList(new ArrayList<>(Arrays.asList(v6, v8)));
graph.add(v1);
graph.add(v2);
graph.add(v3);
graph.add(v4);
graph.add(v5);
graph.add(v6);
graph.add(v7);
graph.add(v8);
graph.add(v9);
graph.add(v10);
int countConnectedComponents = testClass.countConnectedComponents(graph);
assertEquals(3, countConnectedComponents);
}
@Test
public void testWithFullyConnectedGraph() {
Vertex s = new Vertex("s");
Vertex u = new Vertex("u");
Vertex r = new Vertex("r");
Vertex v = new Vertex("v");
Vertex t = new Vertex("t");
Vertex w = new Vertex("w");
Vertex x = new Vertex("x");
Vertex y = new Vertex("y");
s.setAdjList(new ArrayList<>(Arrays.asList(r, w)));
r.setAdjList(new ArrayList<>(Arrays.asList(v, s)));
v.setAdjList(new ArrayList<>(Arrays.asList(r)));
w.setAdjList(new ArrayList<>(Arrays.asList(s, t, x)));
x.setAdjList(new ArrayList<>(Arrays.asList(w, t, u, y)));
t.setAdjList(new ArrayList<>(Arrays.asList(w, x, u)));
u.setAdjList(new ArrayList<>(Arrays.asList(t, x, y)));
y.setAdjList(new ArrayList<>(Arrays.asList(u, x)));
graph.add(s);
graph.add(r);
graph.add(w);
graph.add(v);
graph.add(t);
graph.add(x);
graph.add(u);
graph.add(y);
int countConnectedComponents = testClass.countConnectedComponents(graph);
assertEquals(1, countConnectedComponents);
}
}
import java.util.ArrayList;
public class Vertex {
private boolean explored;
private ArrayList<Vertex> adjList;
private final String label;
public Vertex(String label) {
this.label = label;
}
public boolean isExplored() {
return explored;
}
public void setExplored(boolean explored) {
this.explored = explored;
}
public ArrayList<Vertex> getAdjList() {
return adjList;
}
public void setAdjList(ArrayList<Vertex> adjList) {
this.adjList = adjList;
}
public String getLabel() {
return label;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment