최소신장트리(MST) feat. KRUSKAL

---

---

최소 신장 트리(MST)

신장트리란?
n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리

 

최소 신장 트리는 가중치가 있는 무방향 그래프에서 모든 정점을 포함하면서 간선의 가중치의 합이 최소가 되는 트리를 의미한다. 즉 신장 트리중 최소의 값을 의미한다.

최소신장트리 예시

 

---

KRUSKAL 알고리즘

그래프 표현방식중 간선리스트를 이용하여 간선을 정렬한후 간선을 하나씩 선택하여 MST를 찾는 알고리즘

1. 최초, 모든 간선을 가중치에 따라 오름차순 정렬
2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 완성시켜 나감
   • 사이클이 존재하면 남아있는 간선 중 그 다음으로 가중치가 낮은 간선 선택
3. n-1 개의 간선이 선택될 때까지 2번을 반복

 

알고리즘 적용 예

---

KRUSKAL 알고리즘 (사이클) - UNION FIND

 

위의 그래프에서 만약 3-4 의 가중치가 30이고,  0-3의 가중치가 22라면

위의 알고리즘 대로 가면 사이클이 발생하게 된다.

이떄 현재 진행되어서 연결된 트리와 연결하려는 노드를 서로소 집합인지 확인하여 서로소 집합이면 Union해주는 연산을 한다.

 

서로소 집합(Union-Find)

 

고로 간선을 선택할때 사이클이 발생하면 해당 간선을 선택하지 않고 다음 간선을 선택한다.

 

 

종료조건

선택된 간선수가 노드수 - 1 개가 되면 모든 노드가 연결되었다는 의미임으로 종료한다.

---

KRUSKAL 알고리즘 구현 코드

static class Edge implements Comparable<Edge>{
    int from;
    int to;
    int value;

    public Edge(int from, int to, int value) {
        this.to = to;
        this.from = from;
        this.value = value;
    }

    @Override
    public int compareTo(Edge o) {
        // TODO Auto-generated method stub
        return Integer.compare(this.value, o.value);
    }
 
}

public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());

    StringTokenizer st = new StringTokenizer(br.readLine());

    V = Integer.parseInt(st.nextToken());
    E = Integer.parseInt(st.nextToken());

    edge = new Edge[E];

    for(int i = 0; i < E; i++) {
        st = new StringTokenizer(br.readLine());

        int from = Integer.parseInt(st.nextToken()) -1;
        int to = Integer.parseInt(st.nextToken()) -1;
        int value = Integer.parseInt(st.nextToken());

        edge[i] = new Edge(from, to, value);
    }

     // 간선 정렬
    Arrays.sort(edge);

    make_set();

    long sum = 0;
    int cnt = 0;

    for(Edge edg : edge) {
        int from = edg.from;
        int to = edg.to;
        int value = edg.value;
        // 사이클이 발생하면 continue;
        if(!union(from,to)) continue;
        sum += value;
        // 종료조건
        if(++cnt == V) break;
    }
    sb.append(sum);
    System.out.print(sb);

}

// UNION - FIND 함수