[알고리즘]크루스칼 알고리즘(kruskal's Algorithm) 정리 및 백준 문제 추천

gpt가 생성한 크루스칼 알고리즘 이미지

 

개념

최소 신장 트리(MST,  Minimum Spanning Tree)

연결된 무방향 가중치 그래프에서 모든 정점을 포함하면서, 가중치의 합이 최소가 되는 트리

  위 내용은 gpt가 설명하는 MST의 정의입니다. 두 정점 사이의 간선이 서로 다른 가중치를 가지는 그래프에 대하여 최소 신장 트리는 다음과 같은 특징을 만족합니다. 

1. 모든 정점을 포함
2. 사이클이 없음 
3. 간선의 가중치 합이 최소

 아래 그래프를 예시로 들어보겠습니다. 

 위 그래프에서 최소 신장트리는 다음과 같습니다. 

최소 신장 트리를 구하는 대표적인 알고리즘은 크루스칼과 프림 알고리즘이 있습니다. 이번 게시물에서는 그 중 크루스칼에 대해 알아보고자 합니다. 

 

크루스칼 알고리즘(kruskal's Algorithm)

간선을 가중치 순(오름차순)으로 정렬한 후 사이클을 이루지 않도록 간선을 선택하는 방식 . 그리디 알고리즘 (Greedy Algorithm)을 활용하여 최소 신장 트리를 구한다.  

동작 과정

1. 간선 정렬: 가중치의 오름차순으로 간선을 정렬한다. 
2. 간선 선택: 가중치가 작은 간선부터 순서대로 하나씩 선택합니다.
3. 사이클 확인: 간선을 선택했을 때 사이클이 생성이 되지 않았을 경우만 트리에 추가합니다.
4. 최소 신장 트리 완성 

위에서 주어진 그래프로 예시를 들어보겠습니다. 먼저 간선을 오름차순으로 정렬합니다 . 

 

• 2-4 (가중치: 1)
• 2-5 (가중치: 2)
• 1-3 (가중치: 3)
• 1-2 (가중치: 4)
• 4-5 (가중치: 5)
• 3-4 (가중치: 6)

 

이제 순서대로 진행해보겠습니다. 

2 - 4 간선 추가

2 - 5간선 추가(가중치: 2)

1 - 3 간선 추가(가중치: 3)

1 - 2 간선 추가(가중치: 4)

4 - 5 간선, 사이클이 발생하므로 넘어간다.

3 - 4 간선, 사이클이 발생하므로 넘어간다.

최소 신장 트리 완성

 위와 같은 과정을 통해 최소 신장 트리가 완성되었습니다. 

 

유니온 - 파인드 알고리즘 

두 정점이 같은 집합에 속해있는지 확인하는 알고리즘. 
상호 배타적 집합(Disjoint-set) 

 유니온(union) 연산과 파인드(find) 연산으로 구성된다. 

• 유니온 연산: 두 개의 집합을 하나의 집합으로 합치는 연산 
• 파인드 연산: 특정 원소가 속한 집합의 대표자(root)를 찾는 연산

 

코드 설명

구현 핵심

크루스칼 알고리즘을 구현하는 데 필요한 코드는 다음과 같습니다. 

• 간선을 가중치 순으로 정렬
• 그래프의 사이클 존재 여부 확인

n은 정점의 개수, V를 간선의 개수라고 가정할 때 시간복잡도를 계산해보겠습니다. 정렬은 O(nlogn)의 시간 복잡도를 가지고 있으며 그래프의 사이클 존재여부 확인은 O(n*α(V)) 의 시간 복잡도를 가집니다. 보통은 O(nlogn)의 값이 크므로 시간 복잡도는 O(nlogn)입니다.

• O( α(V) ): 유니온 파인드 알고리즘의 시간 복잡도.
• α는 아커만 함수의 역함수.

코드 예시(수도 코드)

Kruskal-Algorithm(G):
  Input: 그래프 G(V, E) - V는 정점 집합, E는 간선 집합
  Output: 최소 신장 트리 T

  1. T = ∅  // 최소 신장 트리를 저장할 집합을 초기화
  2. 모든 간선 e ∈ E를 가중치의 오름차순으로 정렬
  3. 유니온-파인드 자료 구조를 사용해 각 정점을 개별 집합으로 초기화
  
  4. for 각 간선 e in E (가중치 순으로 정렬된 순서대로):
      5. u = e의 시작 정점
      6. v = e의 끝 정점
      
      // 같은 집단 여부를 확인하는 것은 파인드 연산을 이용. 
      7. if u와 v가 서로 다른 집합에 속해 있다면:
          8. 간선 e를 T에 추가
          9. u와 v의 집합을 유니온 연산으로 병합
  
  10. return T  // 최소 신장 트리를 반환

 

코드 예시(java)

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Edge {
    int src, dest, weight;

    // 간선의 시작점, 끝점, 가중치를 초기화하는 생성자
    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }
}

class Graph {
    int V, E; // V: 정점의 수, E: 간선의 수
    List<Edge> edges; // 간선 리스트

    // 그래프를 초기화하는 생성자
    Graph(int v, int e) {
        V = v;
        E = e;
        edges = new ArrayList<>();
    }

    // 간선을 그래프에 추가하는 메서드
    void addEdge(int src, int dest, int weight) {
        edges.add(new Edge(src, dest, weight));
    }

    // 유니온-파인드 자료 구조를 사용한 부모 노드 찾기 (Find 연산)
    int find(int parent[], int i) {
        if (parent[i] == i)
            return i;
        return find(parent, parent[i]);
    }

    // 두 집합을 합치는 메서드 (Union 연산)
    void union(int parent[], int rank[], int x, int y) {
        int rootX = find(parent, x);
        int rootY = find(parent, y);

        if (rank[rootX] < rank[rootY])
            parent[rootX] = rootY;
        else if (rank[rootX] > rank[rootY])
            parent[rootY] = rootX;
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }

    // 크루스칼 알고리즘으로 최소 신장 트리를 찾는 메서드
    void kruskalMST() {
        // 결과 간선 리스트를 저장할 리스트
        List<Edge> result = new ArrayList<>();

        // 간선들을 가중치 순으로 정렬
        Collections.sort(edges, Comparator.comparingInt(o -> o.weight));

        // 부모와 랭크 배열을 초기화
        int parent[] = new int[V];
        int rank[] = new int[V];
        for (int i = 0; i < V; i++) {
            parent[i] = i;
            rank[i] = 0;
        }

        int e = 0; // 결과 간선의 수
        int i = 0; // 정렬된 간선의 인덱스
        while (e < V - 1) {
            // 현재 간선을 가져옴
            Edge nextEdge = edges.get(i++);
            int x = find(parent, nextEdge.src);
            int y = find(parent, nextEdge.dest);

            // 사이클이 발생하지 않는 경우만 간선을 추가
            if (x != y) {
                result.add(nextEdge);
                union(parent, rank, x, y);
                e++;
            }
        }

        // 최소 신장 트리 출력
        System.out.println("크루스칼 알고리즘으로 찾은 최소 신장 트리:");
        for (Edge edge : result) {
            System.out.println(edge.src + " -- " + edge.dest + " == " + edge.weight);
        }
    }
}

// 실행 예제
public class KruskalAlgorithm {
    public static void main(String[] args) {
        int V = 6; // 정점의 수
        int E = 8; // 간선의 수
        Graph graph = new Graph(V, E);

        // 그래프에 간선 추가
        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 2, 4);
        graph.addEdge(1, 2, 2);
        graph.addEdge(1, 3, 5);
        graph.addEdge(2, 3, 8);
        graph.addEdge(2, 4, 10);
        graph.addEdge(3, 4, 6);
        graph.addEdge(3, 5, 7);

        // 크루스칼 알고리즘 실행
        graph.kruskalMST();
    }
}

 

코드 예시(python)

class Edge:
    def __init__(self, src, dest, weight):
        self.src = src
        self.dest = dest
        self.weight = weight

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.edges = []

    def add_edge(self, src, dest, weight):
        self.edges.append(Edge(src, dest, weight))

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        rootX = self.find(parent, x)
        rootY = self.find(parent, y)

        if rank[rootX] < rank[rootY]:
            parent[rootX] = rootY
        elif rank[rootX] > rank[rootY]:
            parent[rootY] = rootX
        else:
            parent[rootY] = rootX
            rank[rootX] += 1

    def kruskal_mst(self):
        # 결과 간선 리스트
        result = []

        # 간선을 가중치 순으로 정렬
        self.edges.sort(key=lambda edge: edge.weight)

        # 부모와 랭크 배열 초기화
        parent = []
        rank = []
        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        e = 0  # 결과 간선의 수
        i = 0  # 정렬된 간선의 인덱스
        while e < self.V - 1:
            # 가장 가중치가 작은 간선 선택
            next_edge = self.edges[i]
            i += 1
            x = self.find(parent, next_edge.src)
            y = self.find(parent, next_edge.dest)

            # 사이클이 발생하지 않는 경우만 간선을 추가
            if x != y:
                result.append(next_edge)
                self.union(parent, rank, x, y)
                e += 1

        # 최소 신장 트리 출력
        print("크루스칼 알고리즘으로 찾은 최소 신장 트리:")
        for edge in result:
            print(f"{edge.src} -- {edge.dest} == {edge.weight}")

# 실행 예제
if __name__ == "__main__":
    V = 6  # 정점의 수
    graph = Graph(V)

    # 그래프에 간선 추가
    graph.add_edge(0, 1, 4)
    graph.add_edge(0, 2, 4)
    graph.add_edge(1, 2, 2)
    graph.add_edge(1, 3, 5)
    graph.add_edge(2, 3, 8)
    graph.add_edge(2, 4, 10)
    graph.add_edge(3, 4, 6)
    graph.add_edge(3, 5, 7)

    # 크루스칼 알고리즘 실행
    graph.kruskal_mst()

 

추천 문제

• 백준 1197 최소 스패닝 트리 
• 백준 1922 네트워크 연결
• 백준 1647 도시 분할 계획 
• 백준 4386 별자리 만들기
• 백준 17472 다리 만들기 2
• 백준 2887 행성 터널