-
Notifications
You must be signed in to change notification settings - Fork 5
/
Kruskal.java
55 lines (49 loc) · 1.49 KB
/
Kruskal.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package com.vee.algorithms.graph;
import java.awt.Point;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.HashMap;
import java.util.*;
public class Kruskal {
public static void main(String args[]) {
Map<Point, Integer> map = new HashMap<>();
map.put(new Point(1,5), 1);
map.put(new Point(3,4), 2);
map.put(new Point(5,4), 7);
map.put(new Point(1,2), 3);
map.put(new Point(5,3), 6);
map.put(new Point(2,5), 4);
map.put(new Point(2,3), 5);
Set<Point> s = new Kruskal().mst(map);
s.forEach(p -> {System.out.println(p.x + " " + p.y); } );
}
Set<Point> mst(Map<Point, Integer> edges) {
Map<Integer, Integer> map = new HashMap<>();
edges.keySet().forEach(p -> {
map.put(p.x, p.x);
map.put(p.y, p.y);
});
Set<Point> A = new LinkedHashSet<>();
edges.entrySet().stream().sorted(Map.Entry.comparingByValue()).forEach(e -> {
Point edge = e.getKey();
if (findSet(edge.x, map) != findSet(edge.y, map)) {
A.add(edge);
map.put(edge.y, findSet(edge.x, map));
}
});
int[][] arr = new int[][] {{1,10},{2,9},{3,8},{4,7}};
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[1] - b[1]);
Arrays.asList(arr).stream().forEach(pq::add);
System.out.println(Arrays.deepToString(pq.toArray()));
Arrays.sort(arr, (int a[], int b[]) -> a[1] - b[1]);
System.out.println(Arrays.deepToString(arr));
return A;
}
private int findSet(int v, Map<Integer, Integer> map) {
while (map.get(v) != v) {
v = map.get(v);
}
return v;
}
}