최단 경로 알고리즘 - 최소신장트리 (Minimum Spanning Tree)

최소신장트리 (Minimum Spanning Tree)

• 신장트리 : 모든 정점들은 포함하고 간선은 (정점수-1) 개만 포함하는 트리, 사이클 없음
• 신장 트리 중에서 간선 가중치의 합이 최소인 신장 트리
• ★Kruskal : Union-Find(Disjoint Set) 사용 O(|E|log|V|)
• Prim : 우선순위큐 사용 O(|E|log|V|)
• 간선을 기준으로 LinkedList에 담아 정렬 후 Union-Find

---

Union Find by Rank

• 트리의 높이가 높을 수록 Find Set 수행시간 증가

• Union 시 두 집합의 Root 중 Rank 값이 작은 Root를 큰 Root로 변경

• Rank 값이 같을 경우에만 랭크 값 증가

    public static void unionSet(int a, int b) {
        int rootA = findSet(a);
        int rootB = findSet(b);
  
        if(rootA != rootB) {
            if(R[rootA] > R[rootB]) {
                P[rootB] = rootA;
            } else {
                P[rootA] = rootB;
                if(R[rootA] == R[rootB])
                    R[rootB]++;
            }
        }
  
    }
  
    public static int findSet(int n) {
        if(n != P[n])
            P[n] = findSet(P[n]);
        return P[n];
    }