import java.util.List;
import java.util.ArrayList;
class ConnectedComponents {
private boolean[] visited; // visited[v] = true if v connected to s
private int[] id; // id[v] = id of component containing v
private int count;
/** find connected components in G */
public ConnectedComponents(Graph G) {
// initialize data structures
this.visited = new boolean[G.V()];
this.id = new int[G.V()];
this.count = 0; // number of components
// run DFS from one vertex in each component
for(int v = 0; v < G.V(); v++) {
if(!visited[v]) {
dfs(G, v);
count++;
}
}
}
/** are v and w connected? */
boolean connected(int v, int w) {
return id[v] == id[w];
}
/** number of connected components */
int count() {
return count;
}
/** component identifier for v */
int id(int v) {
return id[v];
}
private void dfs(Graph G, int v) {
// all vertices discovered in same call of dfs have same id
visited[v] = true;
id[v] = count;
for (int w : G.adj(v)) {
if(!visited[w]) {
dfs(G, w);
}
}
}
private static Graph prepareGraph() {
int[][] edges = new int[][] {
// {13, 13} V & E
{0, 5},
{4, 3},
{0, 1},
{9, 12},
{6, 4},
{5, 4},
{0, 2},
{11, 12},
{9, 10},
{0, 6},
{7, 8},
{9, 11},
{5, 3}
};
Graph G = new Graph(13, 13);
// add all edges
for(int i = 0; i < edges.length; i++) {
int v = edges[i][0];
int w = edges[i][1];
G.addEdge(v, w);
}
return G;
}
static class Graph {
private final int V; // number of vertices
private final int E; // number of edges
private final List[] adj; // adjacency lists... 0 to V-1
/** create an empty graph with V vertices */
public Graph(int V, int E) {
this.V = V;
this.E = E;
this.adj = new ArrayList[V]; // create empty graph with V vertices
for(int i = 0; i < V; i++) {
adj[i] = new ArrayList<>();
}
}
/** add an edge v-w */
public void addEdge(int v, int w) {
// add edge v-w (parallel edges and self-loops allowed)
adj[v].add(w);
adj[w].add(v);
}
/** vertices adjacent to v */
public Iterable adj(int v) {
return adj[v];
}
/** number of vertices */
public int V() {
return V;
}
/** number of edges */
public int E() {
return E;
}
}
public static void main (String[] args) {
System.out.println("Test connected components ");
ConnectedComponents cc = new ConnectedComponents(prepareGraph());
System.out.println("Number of connected components: " + cc.count());
System.out.println("Id of 3 = " + cc.id(3));
System.out.println("Id of 8 = " + cc.id(8));
System.out.println("Id of 11 = " + cc.id(11));
System.out.println("Is 0 & 3 connected? " + cc.connected(0, 3));
System.out.println("Is 7 & 8 connected? " + cc.connected(7, 8));
System.out.println("Is 10 & 11 connected? " + cc.connected(10, 11));
System.out.println("Is 0 & 8 connected? " + cc.connected(0, 8));
System.out.println("Is 7 & 3 connected? " + cc.connected(7, 3));
System.out.println("Is 10 & 7 connected? " + cc.connected(10, 7));
}
}
Output
Test connected components
Number of connected components: 3
Id of 3 = 0
Id of 8 = 1
Id of 11 = 2
Is 0 & 3 connected? true
Is 7 & 8 connected? true
Is 10 & 11 connected? true
Is 0 & 8 connected? false
Is 7 & 3 connected? false
Is 10 & 7 connected? false
Comments
Post a Comment