[알고리즘 이론] 그리디 알고리즘 - 크루스칼, 프림(최소 신장 트리)

그리디 알고리즘 - 크루스칼, 프림(최소 신장 트리)

---

그리디 알고리즘의 최소 신장 트리 알고리즘인
크루스칼과 프림 알고리즘에 대해서 공부한 내용 정리 입니다 !
 
1. 최소 신장 트리
2. 크루스칼 알고리즘
3. 프림 알고리즘

---

1. 최소 신장 트리

그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분의 가중치 합이 최소인 트리
하나의 그래프에서 여러 개의 트리가 나올 수 있다.
 

2. 크루스칼 알고리즘

가중치가 가장 작은 선분이 사이클을 만들지 않을 때만 욕심내어 그 선분을 추가시킨다.
n개의 트리들이 점차 합쳐져서 1개의 신장 트리가 된다.
 

 
위의 그래프에 크루스칼 알고리즘을 적용해보겠다.
 
먼저, 선분의 가중치가 작은 순서대로 정렬한다.
다음으로 가장 첫 번째 선분을 고른 후, 사이클을 형성하는지 체크하고 추가시킨다.
위의 과정을 반복하면 최소 신장 트리를 구할 수 있다.
 

import java.util.*;

class Edge {
    char start;
    char end;
    int weight;

    public Edge(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }
}

class Main {
    public static int find(int[] parent, int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent, parent[x]);
    }

    public static void union(int[] parent, int x, int y) {
        int rootX = find(parent, x);
        int rootY = find(parent, y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }

    public static boolean isCycle(int[] parent, Edge edge) {
        int startParent = find(parent, edge.start - 'a');
        int endParent = find(parent, edge.end - 'a');
        if (startParent == endParent) {
            return true;
        }
        union(parent, startParent, endParent);
        return false;
    }

    public static void main(String[] args) {
        int[] parent = new int[6];
        for (int i = 0; i < 6; i++) {
            parent[i] = i;
        }

        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge('b', 'c', 1));
        edges.add(new Edge('c', 'f', 1));
        edges.add(new Edge('b', 'f', 2));
        edges.add(new Edge('a', 'd', 2));
        edges.add(new Edge('d', 'e', 3));
        edges.add(new Edge('a', 'e', 4));
        edges.add(new Edge('b', 'd', 4));
        edges.add(new Edge('d', 'f', 7));
        edges.add(new Edge('a', 'b', 8));
        edges.add(new Edge('e', 'f', 9));

        List<Edge> selectedEdges = new ArrayList<>();
        for (Edge edge : edges) {
            if (!isCycle(parent, edge)) {
                selectedEdges.add(edge);
            }
        }

        for (Edge edge : selectedEdges) {
            System.out.println("Selected edge: " + edge.start + " -> " + edge.end + ", weight: " + edge.weight);
        }
    }
}

 
최종 코드는 이렇게 작성할 수 있다.
알고리즘 수업시간에는 모든 코드를 c로 작성해본 경험이 있기 때문에 이번에는 java로 작성했다.
 
지금의 코드에서는 가중치를 오름차순으로 정리해서 삽입해서 문제가 없지만,
다른 문제를 풀 때는 가중치 정렬 코드를 추가하는 것이 필요하다.

 

3. 프림 알고리즘

프림 알고리즘(그리디+동적 계획)은 임의의 점 하나를 선택한 후, (n-1)개의 선분을 하나 씩 추가시켜 트리를 만든다.
1개의 트리가 자라나서 신장 트리가 된다.
 

 
위의 그래프에 프림 알고리즘을 적용해보겠다.
 
먼저, 임의의 점 하나를 선택하여 배열에 넣는다.
배열에 속하지 않은 점에 대하여, 가중치가 최소인 점을 선택한다.
위의 과정을 반복하면 최소 신장 트리를 구할 수 있다.

---

정말 헷갈렸던 알고리즘 2가지를 공부했다.
다음 포스팅에서 만나요 !