최소 신장 트리(Minimum Spanning Tree), 크루스칼(Kruskal) 알고리즘, 프림(Prim) 알고리즘

신장 트리

• 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미
• 트리의 조건 : 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않아야 함  

출처 : https://www.youtube.com/watch?v=Gj7s-Nrt1xE

사이클(cycle)이란 ?

• 그래프에서 시작 노드에서 출발해서 다른 노드를 거쳐 다시 시작 노드로 돌아갈 수 있는 경로가 존재한다면, 이는 하나의 사이클이 됩니다.

cycle 예시

최소 신장 트리 

최소한의 비용으로 신장 트리를 찾기 위한 방법

1, 2, 3번 지역에 도로를 2개 놓아 전체 지역을 연결시키도록 하는 경우에서는 1->2, 2->3을 연결하는 것이 가장 저렴하게 연결할 수 있는 방법입니다. 

즉, 최소 신장 트리는 말 그대로 최소한의 비용(가중치의 합이 최소==간선의 비용)으로 신장 트리를 찾아내는 알고리즘이고, 그리디 알고리즘으로 분류됩니다.

 

예시로는 크루스칼 알고리즘이 있습니다. 

 

크루스칼 알고리즘(임의의 간선 선택, 간선이 적은 경우) 과정

1. 간선 데이터를 비용에 따라 오름차순 정렬
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인합니다.
   1. 사이클이 발생하지 않는 경우, 최소 신장 트리에 포함시킵니다.
   2. 사이클이 발생하는 경우, 최소 신장 트리에 포함시키지 않습니다.
3. 모든 간선에 대해 2번의 과정 반복
4. 간선의 개수가 E개 일때, O(ElogE)의 시간 복잡도를 가집니다.
5. 가장 많은 시간을 요구하는 곳은 간선을 정렬하는 부분입니다. (E개의 데이터를 정렬하기 위한 시간 복잡도 : O(ElogE)
6. 간선이 적은 경우에 사용하기 적합한 알고리즘입니다. 

<코드>

#include <iostream>
#include <vector>

using namespace std;

int V, E; // 노드의 개수(V), 간선(union 연산)의 개수(E)
int parent[100001]; // 부모 테이블 초기화
vector<pair<int, pair<int,int>>> edges;
// 모든 간선을 담을 ㄷ리스트와, 최종 비용을 담을 변수
int result = 0;

// 특정 원소가 속한 집합을 찾기
int findParent(int x)
{
    // 루트 노드가 아니라면, 루트 노드를 찾을 때 까지 재귀적으로 호출
    if(x == parent[x]) return x;
    // 경로 압축
    return parent[x] = findParent(parent[x]); 
    
}
// 두 원소가 속한 집합을 합치기
void unionParent(int a, int b)
{
    a = findParent(a);
    b = findParent(b);
    if(a < b) parent[b] = a; 
    else parent[a] = b;
}

int main()
{
    cin>>V>>E;

    // 부모 테이블 초기화 
	for(int i = 1; i <= V; i++){
		parent[i] = i;
	}

    for(int i=0; i<E; i++)
    {
        int a, b, cost;
        cin >> a >> b >> cost;
        // 비용순으로 정렬하기 위해 튜플의 첫 번째 원소를 비용으로 설정
        edges.push_back({cost,{a,b}});
    }
    
    // 간선을 비용순으로 정렬
    sort(edges.begin(),edges.end());

    for(int i=0;i<edges.size();i++)
    {
        int cost = edges[i].first;
        int a = edges[i].second.first;
        int b = edges[i].second.second;
        // 사이클이 발생하지 않는 경우에만 집합에 포함
        if(findParent(a) != findParent(b))
        {
            unionParent(a, b);
            result += cost;
        }
    }
    cout<<result<<'\n';
}

 

프림 알고리즘(임의의 정점 선택, 간선이 많은 경우)

1. 그래프에서의 임의의 정점 선택
2. 정점으로부터 가중치가 낮은 간선을 선택하면서 정점을 추가해나가는 알고리즘 
3. 최소 신장 트리를 찾는 알고리즘
4. G(그래프)(V(노드), E(간선)), 평균 시간복잡도 O(ElogV), O(V^2, 최악경우)
5. 간선이 많은 경우에  사용하기 적합한 알고리즘입니다.

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

vector<pair<int, int>> G[10001];
priority_queue<pair<int, int>, vector<pair<int,int>>,greater<pair<int,int>>> pq;
int V, E;
int a,b,c;
long long ans;
bool visited[10001];
int main()
{
    
    cin>>V>>E;
    for(int i=0;i<E;i++)
    {
        cin>>a>>b>>c;
        G[a].push_back(make_pair(b,c));
        G[b].push_back(make_pair(a,c));
    }

    pq.push(make_pair(0,1));


    while(!pq.empty())
    {
        int w = pq.top().first;
        int node =pq.top().second;
        pq.pop();

        if(visited[node]) continue;
        visited[node] = true;

        ans += w;

        for (int i = 0; i < G[node].size(); i++) { //현재 정점에서 이동 할 수 있는 방문하지 않은 정점 푸쉬 
			
			pq.push(make_pair(G[node][i].second, G[node][i].first));
			
		}
    }
    cout<<ans<<'\n';
}

<비슷한 유형의 문제>

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

 

 

<참고 자료>

https://www.youtube.com/watch?v=Gj7s-Nrt1xE