ABOUT ME

Today
Yesterday
Total
  • 최소 신장 트리 알고리즘 (1): 크루스칼 알고리즘 (Kruskal's Algorithm)
    알고리즘 2025. 3. 11. 16:00

    1. 크루스칼 알고리즘이란?

    크루스칼 알고리즘(Kruskal's Algorithm)은 최소 신장 트리(MST: Minimum Spanning Tree)를 구하는 대표적인 알고리즘 중 하나이다. 그래프에서 모든 정점을 최소 비용으로 연결하는 트리를 생성하는 데 사용된다.

    이 알고리즘은 간선을 오름차순으로 정렬한 후, 사이클을 형성하지 않는 선에서 가장 작은 가중치를 가진 간선을 선택하는 방식으로 동작한다. 유니온-파인드(Union-Find) 자료구조를 활용해 사이클 발생 여부를 효율적으로 판별한다.

    1.1 크루스칼 알고리즘의 특징

    • 탐욕적 접근법(Greedy Approach) 기반
    • 무방향 가중 그래프에서 사용
    • 사이클 방지를 위해 유니온-파인드 사용
    • 시간 복잡도: O(E log E) (E는 간선 수)

    2. 크루스칼 알고리즘의 동작 원리

    크루스칼 알고리즘은 다음과 같은 단계로 수행된다:

    1. 간선 정렬: 모든 간선을 가중치 기준으로 오름차순 정렬
    2. 유니온-파인드 초기화: 각 정점을 독립된 집합으로 초기화
    3. 간선 선택:
      • 가중치가 가장 작은 간선을 선택
      • 선택한 간선이 사이클을 형성하지 않으면 트리에 추가
    4. 트리 완성: (V-1)개의 간선을 선택하면 종료 (V는 정점 수)

    2.1 크루스칼 알고리즘 예제

    다음과 같은 가중치 그래프에서 최소 신장 트리를 구하자:

         (A)
        / | 
       1  3  
     (B) (C)-4-(D)
       \  |
        2 5
         (E)

    2.2 크루스칼 알고리즘의 수행 과정

    1. 간선 정렬:
    (A-B: 1) → (B-E: 2) → (A-C: 3) → (C-D: 4) → (C-E: 5)
    1. 간선 선택 및 트리 구성:
    (A-B: 1) 선택
    (B-E: 2) 선택
    (A-C: 3) 선택
    (C-D: 4) 선택
    1. 결과 MST:
         (A)
       /  | 
      1   3  
     (B) (C)-4-(D)
       \   
        2  
         (E)

    3. 크루스칼 알고리즘 구현 (Java)

    import java.util.*;
    
    class Edge implements Comparable<Edge> {
        int src, dest, weight;
    
        public Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    
        @Override
        public int compareTo(Edge other) {
            return this.weight - other.weight;
        }
    }
    
    public class Kruskal {
    
        static int findParent(int[] parent, int node) {
            if (parent[node] == node) return node;
            return parent[node] = findParent(parent, parent[node]);
        }
    
        static void union(int[] parent, int a, int b) {
            a = findParent(parent, a);
            b = findParent(parent, b);
            if (a != b) parent[b] = a;
        }
    
        public static void kruskal(List<Edge> edges, int V) {
            Collections.sort(edges); // 간선을 가중치 기준으로 정렬
    
            int[] parent = new int[V];
            for (int i = 0; i < V; i++) {
                parent[i] = i;
            }
    
            int mstWeight = 0;
            List<Edge> mst = new ArrayList<>();
    
            for (Edge edge : edges) {
                if (findParent(parent, edge.src) != findParent(parent, edge.dest)) {
                    mst.add(edge);
                    mstWeight += edge.weight;
                    union(parent, edge.src, edge.dest);
                }
            }
    
            System.out.println("MST의 총 가중치: " + mstWeight);
            for (Edge edge : mst) {
                System.out.println(edge.src + " - " + edge.dest + ": " + edge.weight);
            }
        }
    
        public static void main(String[] args) {
            List<Edge> edges = new ArrayList<>();
    
            edges.add(new Edge(0, 1, 1));
            edges.add(new Edge(1, 4, 2));
            edges.add(new Edge(0, 2, 3));
            edges.add(new Edge(2, 3, 4));
            edges.add(new Edge(2, 4, 5));
    
            int V = 5; // 정점 수
            kruskal(edges, V);
        }
    }

    4. 크루스칼 알고리즘의 성능 분석

    4.1 시간 복잡도

    • O(E log E): 간선 정렬 (우선순위 큐 사용 시)
    • O(V + E): 유니온-파인드 (경로 압축 및 랭크 사용 시)

    4.2 공간 복잡도

    • O(V + E): 간선 리스트, 부모 배열

    5. 크루스칼 알고리즘의 장점과 단점

    5.1 장점

    • 구현이 비교적 간단
    • 희소 그래프(Sparse Graph, 간선의 수가 정점의 수에 비해 상대적으로 적은 그래프 (E ≪ V²))에 적합
    • 유니온-파인드를 통해 사이클 검사가 빠름

    5.2 단점

    • 밀집 그래프(Dense Graph, 간선의 수가 정점의 수에 비례하거나 매우 많은 그래프 (E ≈ V²))에서는 비효율적
    • 간선 정렬로 인한 추가 메모리 사용

    6. 크루스칼 알고리즘의 활용 사례

    • 네트워크 최적화: 최소 비용으로 네트워크 연결
    • 도로망 설계: 도로 건설 시 최소 비용 경로 계획
    • 전기 회로: 최소 전선으로 회로 설계

    7. 크루스칼 알고리즘 vs. 프림 알고리즘

    특징크루스칼 알고리즘프림 알고리즘

    시간 복잡도 O(E log E) O((V + E) log V)
    구현 방식 간선 중심(E) 정점 중심(V)
    적합한 그래프 희소 그래프 (간선 수가 적을 때) 밀집 그래프 (간선 수가 많을 때)
    사이클 검사 유니온-파인드로 검사 방문한 노드로 검사

    8. 결론

    크루스칼 알고리즘은 간선을 기준으로 최소 신장 트리를 생성하는 강력한 알고리즘으로, 희소 그래프에 적합하며 다양한 분야에서 활용된다. 밀집 그래프에서는 프림 알고리즘이 더 적합할 수 있으므로 문제의 특성에 따라 적절한 알고리즘을 선택하는 것이 중요하다.

Designed by Tistory.