Skip to content

Commit 839d9d0

Browse files
BIO2CSBIO2CS
committed
Adding Kruskal and UnionFind algorithms
1 parent 6f97a44 commit 839d9d0

File tree

5 files changed

+138
-12
lines changed

5 files changed

+138
-12
lines changed

‎Graph/KruskalMST.java‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package Graph;
2+
3+
import java.util.*;
4+
import UnionFind.QuickFindUF;
5+
6+
public class KruskalMST {
7+
8+
private Queue<WeightedEdge> mst;
9+
private Queue<WeightedEdge> queue;
10+
private QuickFindUF uf;
11+
12+
public KruskalMST(WeightedEdgeGraph g) {
13+
int numberOfEdges = g.E();
14+
int numberOfVertices = g.V();
15+
mst = new LinkedList<WeightedEdge>();
16+
queue = new PriorityQueue<WeightedEdge>(numberOfEdges, new Comparator<WeightedEdge>(){
17+
public int compare(WeightedEdge e1, WeightedEdge e2) {
18+
if (e1.weight() < e2.weight()) return -1;
19+
if (e1.weight() > e2.weight()) return 1;
20+
return 0;
21+
}
22+
});
23+
for (WeightedEdge e : g.edges()) {
24+
queue.offer(e);
25+
}
26+
uf = new QuickFindUF(numberOfVertices);
27+
28+
mst(g);
29+
}
30+
31+
public void mst(WeightedEdgeGraph g) {
32+
while (!queue.isEmpty() && mst.size() < g.V() - 1) {
33+
WeightedEdge front = queue.poll();
34+
int v = front.either();
35+
int w = front.other(v);
36+
if (uf.connected(v, w)) continue;
37+
uf.union(v, w);
38+
mst.offer(front);
39+
}
40+
}
41+
42+
public Iterable<WeightedEdge> edges() {
43+
return mst;
44+
}
45+
46+
public void printMST() {
47+
double totalWeight = 0;
48+
while (!mst.isEmpty()) {
49+
totalWeight += mst.peek().weight();
50+
System.out.println(mst.poll().toString());
51+
}
52+
System.out.println("Total weight of MST is " + totalWeight);
53+
}
54+
}

‎Graph/KruskalTestClient.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package Graph;
2+
3+
public class KruskalTestClient {
4+
5+
public static void main(String[] args) {
6+
/* int v = 9;
7+
WeightedEdgeGraph g = new WeightedEdgeGraph(v);
8+
WeightedEdge[] edges = {new WeightedEdge(0, 1, 4),new WeightedEdge(0, 7, 8),new WeightedEdge(1, 2, 8),
9+
new WeightedEdge(1, 7, 11),new WeightedEdge(2, 3, 7),new WeightedEdge(2, 8, 2),
10+
new WeightedEdge(2, 5, 4),new WeightedEdge(3, 4, 9), new WeightedEdge(3, 5, 14),
11+
new WeightedEdge(4, 5, 10),new WeightedEdge(5, 6, 2),new WeightedEdge(6, 7, 1),
12+
new WeightedEdge(6, 8, 6),new WeightedEdge(7, 8, 7)};*/
13+
14+
int v = 5;
15+
WeightedEdgeGraph g = new WeightedEdgeGraph(v);
16+
WeightedEdge[] edges = {new WeightedEdge(0,2,10), new WeightedEdge(0,3,7),new WeightedEdge(1,3,32),
17+
new WeightedEdge(2,3,9),new WeightedEdge(3,4,23),};
18+
19+
for (WeightedEdge e : edges) {
20+
g.addEdge(e);
21+
}
22+
23+
KruskalMST mst = new KruskalMST(g);
24+
mst.printMST();
25+
}
26+
}

‎Graph/PrimMSTTestClient.java‎

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -5,13 +5,17 @@
55
public class PrimMSTTestClient {
66

77
public static void main(String[] args) {
8-
int v = 9;
8+
/*int v = 9;
99
WeightedEdgeGraph g = new WeightedEdgeGraph(v);
1010
WeightedEdge[] edges = {new WeightedEdge(0, 1, 4),new WeightedEdge(0, 7, 8),new WeightedEdge(1, 2, 8),
1111
new WeightedEdge(1, 7, 11),new WeightedEdge(2, 3, 7),new WeightedEdge(2, 8, 2),
1212
new WeightedEdge(2, 5, 4),new WeightedEdge(3, 4, 9), new WeightedEdge(3, 5, 14),
1313
new WeightedEdge(4, 5, 10),new WeightedEdge(5, 6, 2),new WeightedEdge(6, 7, 1),
14-
new WeightedEdge(6, 8, 6),new WeightedEdge(7, 8, 7)};
14+
new WeightedEdge(6, 8, 6),new WeightedEdge(7, 8, 7)};*/
15+
int v = 5;
16+
WeightedEdgeGraph g = new WeightedEdgeGraph(v);
17+
WeightedEdge[] edges = {new WeightedEdge(0,2,10), new WeightedEdge(0,3,7),new WeightedEdge(1,3,32),
18+
new WeightedEdge(2,3,9),new WeightedEdge(3,4,23),};
1519

1620
for (WeightedEdge e : edges) {
1721
g.addEdge(e);

‎Graph/PrimMSTUsingAdj.java‎

Lines changed: 7 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,12 @@
22

33
import java.util.*;
44

5+
/**
6+
* Generic PriorityQueue is not going to work because you will change the elements while traversing the queue.
7+
* http://stackoverflow.com/questions/1871253/updating-java-priorityqueue-when-its-elements-change-priority
8+
* @author Huiqiong Gu
9+
*
10+
*/
511
public class PrimMSTUsingAdj {
612

713
private boolean[] visited;
@@ -27,13 +33,7 @@ public PrimMSTUsingAdj(WeightedEdgeGraph g) {
2733
public void mstUsingAdj(WeightedEdgeGraph g) {
2834
while (!heap.isEmpty()) {
2935
PrimNode front = heap.extractMin();
30-
visited[front.v] = true;
31-
System.out.println("Pulling from queue vertex is " + front.v + " weight is " + front.weight);
32-
/*Iterable<WeightedEdge> list = g.adj(front.v);
33-
for (WeightedEdge edge : list) {
34-
int one = edge.either(), other = edge.other(one);
35-
System.out.println("\t\t" + one + "->" + other + ": " + edge.weight());
36-
}*/
36+
visited[front.v] = true;
3737
for (WeightedEdge e : g.adj(front.v)) {
3838
int w = e.other(front.v);
3939
if (visited[w]) continue;
@@ -43,9 +43,6 @@ public void mstUsingAdj(WeightedEdgeGraph g) {
4343
heap.decreaseWeight(w, e.weight());
4444
}
4545
}
46-
/* for (PrimNode n : queue) {
47-
System.out.println("\t" + n.v + ": " + n.weight + "\t\t");
48-
}*/
4946
}
5047
}
5148

‎UnionFind/QuickFindUF.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package UnionFind;
2+
3+
public class QuickFindUF {
4+
5+
private int[] id;
6+
private int count;
7+
8+
public QuickFindUF(int n) {
9+
id = new int[n];
10+
count = n;
11+
12+
for (int i = 0; i < n; i++) {
13+
id[i] = i;
14+
}
15+
}
16+
17+
public int find(int p) {
18+
validate(p);
19+
return id[p];
20+
}
21+
22+
public boolean connected(int p, int q) {
23+
validate(p);
24+
validate(q);
25+
return id[p] == id[q];
26+
}
27+
28+
public void union(int p, int q) {
29+
int pID = id[p], qID = id[q];
30+
if (pID == qID) return;
31+
for (int i = 0; i < id.length; i++) {
32+
if (id[i] == pID) {
33+
id[i] = qID;
34+
}
35+
}
36+
count--;
37+
}
38+
39+
private void validate(int p) {
40+
int n = id.length;
41+
if (p < 0 || p >= n) {
42+
throw new IllegalArgumentException("element " + p + " is out of range");
43+
}
44+
}
45+
}

0 commit comments

Comments
 (0)