#알고리즘_크루스칼(Kruskal Algorithm) - Java

탐욕적인 방법(greedy)를 이용하여 네트워크의 모든 정점을 최소비용으로 연결하는 최적해답을 구하는 알고리즘이다.

**싸이클을 허용하지 않기 때문에 싸이클을 체크하기 위해 Union-find 사용

 

알고리즘 매커니즘 => 간선을 하나씩 선택해서 MST를 찾는 알고리즘

1. 최초, 모든 간선을 가중치(Edge value)에 따라 오름차순으로 정렬한다.
2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다.
3. 만약 사이클이 존재하면 다음으로 가중치 낮은 간선을 선택한다. (사이클 확인은 union-find를 이용)
4. N-1개의 간선이 MST에 더해질때 까지 2,3를 반복한다.

 

 

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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

package graph;   import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner;     public class k {     static int V, E;     static PriorityQueue<Edge> pq;     static ArrayList<Edge> MST;     static int parent[];     public static void main(String[] args) {                  Scanner sc = new Scanner(System.in);                  V = sc.nextInt();         E = sc.nextInt();                  pq = new PriorityQueue<>();         MST = new ArrayList<>();         parent = new int[V+1];                  // for init         for(int i=0; i<=V; i++)             parent[i] = i;                  for(int i=1; i<=E; i++) {             int u = sc.nextInt();             int v = sc.nextInt();             int val = sc.nextInt();                          pq.add(new Edge(u, v, val));         }                  while(MST.size() < (V-1)) {             Edge e = pq.poll();                          if(find(e.begin) != find(e.end)) {                 MST.add(e);                 union(e.begin, e.end);             }         }         for(int i=0; i<MST.size(); i++) {             System.out.println(MST.get(i).begin+" "+MST.get(i).end+" "+MST.get(i).val);         }     }               public static int find(int n) {         if(n==parent[n])             return n;         else {             int p = find(parent[n]);             parent[n] = p;             return p;         }     }     public static void union(int n1, int n2) {         int p1 = find(n1);         int p2 = find(n2);                  if(p1!=p2) {             parent[p1] = p2;         }     }          public static class Edge implements Comparable<Edge>{           int begin, end, val;                  public Edge(int b, int e, int v) {             this.begin=b;             this.end=e;             this.val=v;         }         @Override         public int compareTo(Edge o) {             // TODO Auto-generated method stub             return this.val - o.val;         }              } }   Colored by Color Scripter

cs