참고한 블로그 중 한눈에 보이는 사진이 있어 스크랩(출처)
algorithm Kruskal(G) is
A := ∅
for each v ∈ G.V do
MAKE-SET(v)
for each (u, v) in G.E ordered by weight(u, v), increasing do
if FIND-SET(u) ≠ FIND-SET(v) then
A := A ∪ {(u, v)}
UNION(FIND-SET(u), FIND-SET(v))
return A
Cycle 검사는 Union-find 알고리즘을 이용
Union-find는 여기로
static class edgeSet implements Comparable<edgeSet> {
int u, v, w;
edgeSet(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
@Override
public int compareTo(edgeSet edgeSet) {
// the value 0 if x == y; a value less than 0 if x < y; and a value greater than 0 if x > y
return Integer.compare(this.w, edgeSet.w);
}
@Override
public String toString() {
return "U= " + this.u + " V= " + this.v + " W= " + this.w;
}
}
the value 0 if x == y;
a value less than 0 if x < y;
and a value greater than 0 if x > y
public void rankUnion(int x, int y) {
x = find(x);
y = find(y);
// 동일 루트면 종료
if (x == y) {
return;
}
// 트리 x보다 y가 작다면 x를 작게 만듬
if (rank[x] > rank[y]) {
tree[y] = x;
} else { // 반대면 반대로
tree[x] = y;
}
// 만약 트리 둘의 레벨이 같다면 union 됐으니 레벨 1 증가
if (rank[x] == rank[y]) {
rank[x]++;
}
}
public int find(int x) {
return (tree[x] == x) ? x : (tree[x] = find(tree[x]));
}
public static void main(String[] args) {
unionFind union = new unionFind(1000);
Graph graph = new Graph(1000);
graph.makeEdge(1, 2, 4);
graph.makeEdge(1, 4, 2);
graph.makeEdge(4, 5, 7);
graph.makeEdge(4, 2, 12);
graph.makeEdge(2, 6, 8);
graph.makeEdge(2, 7, 1);
graph.makeEdge(4, 7, 3);
Collections.sort(graph.getGraph());
for (edgeSet i : graph.getGraph()) {
System.out.println(i.toString());
}
int sum = 0;
for (edgeSet edge : graph.getGraph()) {
if (!union.connected(edge.u, edge.v)) {
sum += edge.w;
union.rankUnion(edge.u, edge.v);
}
}
System.out.println(sum);
}
U= 2 V= 7 W= 1
U= 1 V= 4 W= 2
U= 4 V= 7 W= 3
U= 1 V= 2 W= 4
U= 4 V= 5 W= 7
U= 2 V= 6 W= 8
U= 4 V= 2 W= 12
21