Created
February 13, 2018 03:57
-
-
Save thmain/ac1b1a33a50b0a97709dbb637e04c1ba to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.*; | |
public class DisjointSet { | |
static class Edge{ | |
int source; | |
int destination; | |
public Edge(int source, int destination) { | |
this.source = source; | |
this.destination = destination; | |
} | |
} | |
static class Graph{ | |
int vertices; | |
LinkedList<Edge>[] adjList; | |
ArrayList<Edge> allEdges = new ArrayList<>(); | |
Graph(int vertices){ | |
this.vertices = vertices; | |
adjList = new LinkedList[vertices]; | |
for (int i = 0; i <vertices ; i++) { | |
adjList[i] = new LinkedList<>(); | |
} | |
} | |
public void addEgde(int source, int destination){ | |
Edge edge = new Edge(source, destination); | |
adjList[source].addFirst(edge); | |
allEdges.add(edge); //add to total edges | |
} | |
public void makeSet(int [] parent){ | |
//Make set- creating a new element with a parent pointer to itself. | |
for (int i = 0; i <vertices ; i++) { | |
parent[i] = i; | |
} | |
} | |
public int find(int [] parent, int vertex){ | |
//chain of parent pointers from x upwards through the tree | |
// until an element is reached whose parent is itself | |
if(parent[vertex]!=vertex) | |
return find(parent, parent[vertex]);; | |
return vertex; | |
} | |
public void union(int [] parent, int x, int y){ | |
int x_set_parent = find(parent, x); | |
int y_set_parent = find(parent, y); | |
//make x as parent of y | |
parent[y_set_parent] = x_set_parent; | |
} | |
public void disjointSets(){ | |
//create a parent [] | |
int [] parent = new int[vertices]; | |
//makeset | |
makeSet(parent); | |
//iterate through all the edges and keep making the sets | |
for (int i = 0; i <allEdges.size() ; i++) { | |
Edge edge = allEdges.get(i); | |
int x_set = find(parent, edge.source); | |
int y_set = find(parent, edge.destination); | |
//check if source vertex and destination vertex belongs to the same set | |
// if in same set then cycle has been detected else combine them into one set | |
if(x_set==y_set) { | |
//do nothing | |
}else | |
union(parent, x_set, y_set); | |
} | |
printSets(parent); | |
} | |
public void printSets(int [] parent){ | |
//Find different Sets | |
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>(); | |
for (int i = 0; i <parent.length ; i++) { | |
if(map.containsKey(parent[i])){ | |
ArrayList<Integer> list = map.get(parent[i]); | |
list.add(i);//add vertex | |
map.put(parent[i],list); | |
}else{ | |
ArrayList<Integer> list = new ArrayList<>(); | |
list.add(i); | |
map.put(parent[i],list); | |
} | |
} | |
//Print the Different sets | |
Set<Integer> set = map.keySet(); | |
Iterator<Integer> iterator = set.iterator(); | |
while(iterator.hasNext()){ | |
int key = iterator.next(); | |
System.out.println("Set Id: " + key + " elements: " + map.get(key)); | |
} | |
} | |
} | |
public static void main(String[] args) { | |
int vertices = 6; | |
Graph graph = new Graph(vertices); | |
graph.addEgde(0, 1); | |
graph.addEgde(0, 2); | |
graph.addEgde(1, 3); | |
graph.addEgde(4, 5); | |
graph.disjointSets(); | |
} | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment