# Kruskal's MST Algorithm 신장트리(Spanning Tree)는 모든 vertex가 edge로 연결하면서 edge 사이에 사이클이 없는 그래프이다. vertex수는 edge수 + 1이 된다.\ \ 모든 vertex가 다 연결은 되어 있지만, 일부 edge를 사용하지 않아도 되는 점을 활용해 여러 문제를 해결할 수 있다. 예를 들어서 **최소 비용으로 연결된 신장 트리를 찾을 때 사용**할 수 있는데, 이것을 최소 신장 트리(Minimum Spanning Tree)라 한다. ### 크루스칼 알고리즘 대표적은 탐욕적 방법으로 최소 신장 트리 알고리즘이다. 동작 과정은\ 먼저 부모테이블을 만들어 자기 자신으로 부모로 초기화하고,\ 간선을 비용 오름차순으로 정렬하고 (sorted),\ 모든 정점을 방문할 때 까지 (for i in range(V)),\ 간선을 순서데로 확인하면서 사이클이 발생하는지 확인하고 (exist\_cycle),\ 사이클이 발생하지 않을 경우만 부모테이블을 업데이트하여 트리에 포함시키고 (union)\ 이 과정을 반복 수행한다. ![](https://2257590298-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MkqRosNMc2ax_2cv-w6%2F-MlED_jKthEnsBtNcvbl%2F-MlEOnqj4xDZmOVR5_nX%2Fimage.png?alt=media\&token=0bd375df-9e21-4aec-a42b-53dcbbc756f0) 간선을 비용 오름차순으로 정렬한다. | edge | 2-3 | 0-3 | 0-2 | 0-1 | 1-3 | | ---- | --- | --- | --- | --- | --- | | cost | 4 | 5 | 6 | 10 | 15 | 모든 정점을 방문할 때 까지 (for i in range(V)),\ 간선을 순서데로 확인하면서 사이클이 발생하는지 확인하고 (exist\_cycle),\ 사이클이 발생하지 않을 경우만 트리에 포함시키고 (union)\ 이 과정을 반복 수행한다. **step 0** ```python n: [0,1,2,3] p: [0,1,2,3] ``` | node | 0 | 1 | 2 | 3 | | ----- | - | - | - | - | | p\[n] | 0 | 1 | 2 | 3 | **step 1** ```python union(2,3) find(2) -> 2 find(3) -> 3 -> p[3] = 2 p: [0,1,2,2] ``` | node | 0 | 1 | 2 | 3 | | ----- | - | - | - | ----- | | p\[n] | 0 | 1 | 2 | **2** | **step 2** ```python union(0,3) find(0) -> 0 find(3) -> find(2) -> 2 -> p[2] = 0 p: [0,1,0,2] ``` | node | 0 | 1 | 2 | 3 | | ----- | - | - | ----- | - | | p\[n] | 0 | 1 | **0** | 2 | **step 3** ```python union(0,2) find(0) -> 0 find(2) -> 0 -> pass ``` | node | 0 | 1 | 2 | 3 | | ----- | - | - | - | - | | p\[n] | 0 | 1 | 0 | 2 | **step 4** ```python union(0,1) find(0) -> 0 find(1) -> 1 -> p[1] = 0 p: [0,0,0,2] ``` | node | 0 | 1 | 2 | 3 | | ----- | - | ----- | - | - | | p\[n] | 0 | **0** | 0 | 2 | ### 코드 {% tabs %} {% tab title="Python" %} ```python def kruskalMST(n, some_list): parent = [] for i in range(n): parent.append(i) def find(parent, i): if parent[i] == i: return i else: parent[i] = find(parent, parent[i]) return parent[i] def exsit_cycle(parent, n1, n2): n1 = find(parent, n1) n2 = find(parent, n2) if n1 == n2: return True else: return False def union(parent, n1, n2): n1 = find(parent, n1) n2 = find(parent, n2) if n1 <= n2: parent[n2] = n1 else: parent[n1] = n2 return parent some_list = sorted(some_list, key=lambda x: x[2]) min_cost = 0 for [n1, n2, w] in some_list: if not exsit_cycle(parent, n1, n2): min_cost += w parent = union(parent, n1, n2) print("{} -- {} == {}".format(n1, n2, w)) print("parent: {}".format(parent)) return min_cost n = 4 some_list = [[0,1,10], [0,2,6], [0,3,5], [1,3,15], [2,3,4]] min_cost = kruskalMST(n, some_list) print("Minimum Spanning Tree: {}".format(min_cost)) ``` {% endtab %} {% tab title="Java" %} ```java // https://velog.io/@ming/MST최소-신장트리-알고리즘 // https://github.com/chaminhye/Algorithm/tree/master/src/concept/graph /* 10 1 2 5 2 3 1 3 6 9 1 4 3 1 3 8 1 5 10 4 5 4 5 6 12 4 6 2 3 4 4 */ import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.StringTokenizer; // https://velog.io/@ming/MST최소-신장트리-알고리즘 // https://github.com/chaminhye/Algorithm/tree/master/src/concept/graph public class Kruskal { static class Edge implements Comparable { int v1; int v2; int w; Edge(int v1, int v2, int w) { this.v1 = v1; this.v2 = v2; this.w = w; } @Override public int compareTo(Edge edge) { return edge.w >= this.w ? -1 : 1; } } public static ArrayList graph = new ArrayList(); public static int[] parent; public static int find(int n) { if (parent[n] == n) { return n; } else { return parent[n] = find(parent[n]); } } public static boolean exist_cycle(int n1, int n2) { n1 = find(n1); n2 = find(n2); if (n1 == n2) { return true; } else { return false; } } public static void union(int n1, int n2) { n1 = find(n1); n2 = find(n2); if (n2 > n1) { parent[n2] = n1; } else { parent[n1] = n2; } } public static void main(String args[]) throws IOException { System.setIn(new FileInputStream("D:\\CS\\wks\\pro\\src\\basic\\kruskal.txt")); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); for (int i = 0; i < N; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); int v1 = Integer.parseInt(st.nextToken()); int v2 = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken()); graph.add(new Edge(v1, v2, w)); } parent = new int[N]; for (int i = 0; i < parent.length; i++) { parent[i] = i; } Collections.sort(graph); int min_cost = 0; for (int i = 0; i < graph.size(); i++) { Edge e = graph.get(i); if (!exist_cycle(e.v1, e.v2)) { min_cost += e.w; union(e.v1, e.v2); System.out.println(String.format("%s -- %s = %s", e.v1, e.v2, e.w)); System.out.println(Arrays.toString(parent)); } } System.out.println(min_cost); } } ``` {% endtab %} {% endtabs %} ### 참고자료 [https://velog.io/@ming/MST최소-신장트리-알고리즘](https://velog.io/@ming/MST%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5%ED%8A%B8%EB%A6%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)\ \ \ --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://ubiradio.gitbook.io/dev/compute-science/kruskals-mst-algorithm.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.