[Algorithm C#] 최소 신장 트리 MST ( 크루스칼, 프림 )

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

그래프에서 모든 정점을 최소 비용으로 연결하는 것

- n개의 정점을 잇는 간선의 수는 n-1개 ( 사이클을 가져서는 안됨 )

 -> 사이클 ex) A -> B / B -> C / C -> A

- 간선의 가중치의 합이 최소여야 함

 

이미지 출처) 프로그래머스 - 섬 연결하기 문제

1. 크루스칼 알고리즘 (Kruskal Algorithm)

가장 비용이 적은 간선부터 선택해 나가는 알고리즘 (간선 선택 기반 알고리즘)

- 간선을 기준으로 선택하기 때문에  간선이 적은 그래프(희소 그래프)에 유리

- 가중치를 기준으로 정렬된 간선들을 Union-Find 알고리즘을 사용해 연결하는 방식

 

동작 방식

1. 간선들을 가중치를 기준으로 오름차순 정렬

2. 가중치가 적은 간선부터 차례로 연결되어 있는지 체크하여 연결 수행 (Union-Find 알고리즘)

3. 연결한 간선의 수가 (정점의 수 - 1)개가 될 때까지 2번을 반복 실행

 

Union-Find 알고리즘이란?

서로소 집합(Disjoint-set)을 표현하는 그래프 알고리즘

- Union : 두 노드(원소)가 같은 그래프(집합)에 속하도록 병합

- Find : 두 노드(원소)가 서로 같은 그래프(집합)에 속하는지 판별

 

주석참조 ( Union-Find 알고리즘 코드 / 크루스칼 알고리즘에 대한 예제는 글 하단 링크 )

        // 인수로 넘긴 정점의 루트를 반환
        public static int GetRoot(int[] parents, int x)
        {
            if (parents[x] == x)
                return x;
            
            // 재귀 호출 시에 부모들의 루트도 같이 업데이트
            return parents[x] = GetRoot(parents, parents[x]);
        }

        // 두 정점을 같은 그룹으로 병합 (같은 부모를 가지게 함)
        public static void Union(int[] parents, int x, int y)
        {
            x = GetRoot(parents, x);
            y = GetRoot(parents, y);
            
            // 루트 정점의 번호가 낮은 번호로 병합
            if (x < y) parents[y] = x;
            else parents[x] = y;
        }

        // 두 정점이 같은 그룹에 있는지 확인 (같은 부모?)
        public static bool Find(int[] parents, int x, int y)
        {
            x = GetRoot(parents, x);
            y = GetRoot(parents, y);

            return x == y;
        }

        public static void Main()
        {
            int n = 5; // 정점의 개수

            int[] parents = new int[n]; // 부모의 인덱스를 가리키는 노드배열

            // 자기 자신을 가리키도록 세팅
            for(int i = 0; i < parents.Length; i++)
                parents[i] = i;

            ...
            
            // parents의 모든 인덱스 값이 0이 되면 모든 정점을 이은 것
        }

2. 프림 알고리즘 (Prim Algorithm)

임의의 시작 정점부터 이어지는 정점을 선택해 나가는 알고리즘 (정점 선택 기반 알고리즘)

- 정점을 기준으로 선택하기 때문에 간선이 많은 그래프(밀집 그래프)에 유리

- 임의의 정점부터 시작하여 하나의 집합을 이루며 인접한 정점과 연결하여 확장하는 방식

 

+ 인접한 정점 : 연결된 정점 그룹과 간선으로 연결된 정점

 

동작 방식

1. 임의의 정점을 시작점으로 선택

2. 인접한 정점과 연결되는 간선 중에 가장 가중치가 적게 드는 정점을 연결

3. 모든 정점에 방문했거나, 연결한 간선의 수가 (정점의 수 - 1)개가 될 때까지 2번을 반복실행

3. 크루스칼, 프림 알고리즘 예제 ( 프로그래머스 Lv3. 섬 연결하기 )

https://godgjwnsgur7.tistory.com/228

[프로그래머스 C#] Lv.3 섬 연결하기