[Algorithm] 최소 스패닝 트리

스패닝 트리?

• 스패닝 트리(ST)는 최소한의 간선으로 모든 정점이 연결되어 있는 구조
• 단, 사이클이 생성되선 안된다.
• 어떤 그래프로 스패닝(신장) 트리를 만들 때 사이클을 만드는 간선은 선택하지 않는다.
• 최소 연결
  • 간선의 수가 가장 적다.
  • 정점의 수가 n개 일 때, 스패닝 트리의 간선의 수는 언제나 n - 1개이다.
  •  사이클이 발생해서는 안된다. 사이클이 있다는 것은 최소로 연결되지 않았다는 의미
  • 1 - 2 - 3으로 연결되어 있을 때 1과 3은 직접적으로 연결되어 있지 않더라도 연결되어 있다고 본다.
• DFS, BFS를 사용해여 그래프에서 스패닝 트리를 찾을 수 있다.
• 한 그래프에서 스패닝 트리는 여러개 존재할 수 있다.

최소 비용 스패닝 트리(MST)

• 가장 적은 비용으로 모든 노드를 연결하고자 할 때 사용
  • 가정 적은 비용이라는 뜻은 가중치의 합이 최소일 때
• 모두 연결하되 최소 비용으로 연결하는 문제는 모두 MST를 만들어야 하는 케이스
• 신장 트리의 모든 특징을 가지며, 가중치의 합이 최소라는 또다른 특징을 가진다.
• MST를 만드는 방법
  • 크루스칼 알고리즘 -> 간선 선택
  • 프림 알고리즘 -> 정점 선택

크루스칼 알고리즘

• 간선이 적은 그래프를 MST로 만들 때 적합
  • 가중치 순서로 정렬하는 과정이 있어 크루스칼은 간선의 수에 시간이 좌우된다.
• 간선을 선택하므로 트리가 여러개 생길 수 있다.
  • 사이클이 생기지 않도록 선택해야 하므로, 사이클 검사가 필요
• 무조건 가장 비용이 작은 간선부터 선택해 나가는 점에서 그리디한 알고리즘이다.
  • 단, 선택한 간선의 두 정점이 연결되어 있지 않는 경우에만 해당 간선을 선택한다.
  • 즉, 사이클이 형성되지 않도록 한다.
• MST 집합은 공백에서 시작한다.
  1. 가중치 순서대로 간선들을 오름차순 정렬
  2. 오름차순 정렬된 간선들을 순차적으로 탐색하여 두 정점이 아직 연결되어 있지 않는(사이클을 형성하지 않으면) 간선이면 선택, 사이클을 형성하는 간선이면 무시한다.
     • 정점들의 부모가 같으면(같은 그룹이라 서로 통행이 가능하면) 사이클을 형성하는 것
     • 부모가 같지 않다면(서로 통행이 불가능하면) 사이클을 형성하지 않는 것
  3. 선택한 간선을 MST 집합에 Union 시킨다.
     • 2 ~ 3 과정을 선택한 간선의 수가 n - 1개가 될때 까지 반복
• 모든 정점의 부모 정점이 같아진다면 (모든 정점이 하나의 그룹에 속하면서 통행이 가능하다면)
  • 하나의 트리를 형성한 것이므로 작업을 종료한다.

코드

• Union - Find 알고리즘을 사용
  • Union -> 연결하기
  • Find -> 부모 확인하기

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int getRoot(vector<int>& parent, int x)  // 인수로 넘긴 정점의 부모 정점을 알려줌
{
    if (parent[x] == x) return x;
    return parent[x] = getRoot(parent, parent[x]);
}

void unionParent(vector<int>& parent, int a, int b)  // 두 정점을 병합함. 부모가 같은, 같은 그룹으로.
{
    int par_a = getRoot(parent, a);
    int par_b = getRoot(parent, b);
    if(par_a < par_b) parent[par_b] = par_a;
    else parent[par_a] = par_b;
}

bool find(vector<int>& parent, int a, int b)  // 두 정점이 같은 부모를 가졌는지 확인
{
    int par_a = getRoot(parent, a);
    int par_b = getRoot(parent, b);
    if(par_a == par_b) return true;
    else return false;
}

bool compare(vector<int> a, vector<int> b)
{
    return a[2] < b[2];
}

int solution(int n, vector<vector<int>> costs) {	
    int answer = 0;
    
	sort(costs.begin(), costs.end(), compare);
    
    vector<int> parents(n);
    
    for(int i = 0; i < parents.size(); i++)
        parents[i] = i;
    
    for(int i = 0; i < costs.size(); i++)
    {
        if(!find(parents, costs[i][0], costs[i][1]))
        {
            unionParent(parents, costs[i][0], costs[i][1]);
            answer += costs[i][2];
        }
    }

	return answer;
}

 

프림 알고리즘

• 간선이 많은 그래프를 MST로 만들 때 적합
• 시작 정점을 정해두고 시작
• 인접한 정점들 중에서 선택해 나가므로 트리는 시작 정점에서 발생했던 단 하나의 트리만 유지되며 정점들을 선택해 나감으로써 하나의 트리를 확장해 나가는 방식
  • 이 과정에서는 사이클이 형성될 일이 없다.
  • 별도의 사이클 검사가 필요하지 않음
• 그리디한 알고리즘을 가지고 있다.
• 시작할 때 시작 정점만 MST 집합에 포함시키고, 현재까지의 MST 집합에 포함된 정점들 중에서 인접한 정점들 중 가중치 최소 간선으로 연결된 정점을 선택하여 트리를 확장시킨다.
• 크루스칼 알고리즘은 이미 선택되어 MST 집합에 들어가 있는 간선들은 다시 고려하지 않았던 반면, 프림 알고리즘은 이미 선택되어 MST 집합에 들어가 있는 정점들의 인접 정점들 중에서 최소 간선을 가지는 정점을 선택하게 된다.
• 트리를 만드는 과정
  1. 시작 정점을 아무거나 선택하여 MST에 포함시킨다.
  2. 현재까지의 MST 집합에 포함되어 있는 이전에 선택한 정점들의 인접 정점(MST에 포함되지 않은)들 중 최소 가중치 간선을 가진 정점을 선택하여 MST에 포함시킨다.
     • 이 과정이 프림 알고리즘의 성능을 결정
     • 정점이 많은 그래프의 경우 크루스칼을 선택하여 MST를 만드는게 효과적
     • visited - unvisited 사이의 인접 정점들의 가중치를 Min Heap 우선순위 큐에 저장해서 빼올 수도 있다. 이 경우 시간복잡도는 O(n^2)보단 작게된다.
     • 2번의 과정을 간선의 수가 n - 1개가 될 때까지 반복, 혹은 2번의 과정을 MST가 n개의 정점을 모두 포함할 때까지 반복

코드

#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

int solution(int n, vector<vector<int>> costs) {
	int answer = 0;

	vector<vector<int>> graph(n, vector<int>(n));
	for (int i = 0; i < costs.size(); i++)
	{
		graph[costs[i][0]][costs[i][1]] = costs[i][2];
		graph[costs[i][1]][costs[i][0]] = costs[i][2];
	}

	vector<int> visited;
	vector<int> unvisited;

	visited.push_back(0);
	for (int i = 1; i < n; i++)
		unvisited.push_back(i);

	for (int i = 1; i < n; i++)
	{
		int min = INT_MAX;
		int min_index = 0;

		for (int j = 0; j < i; j++)
		{
			for (int k = 0; k < n - i; k++)
			{
				if (graph[visited[j]][unvisited[k]] > 0 && min > graph[visited[j]][unvisited[k]])
				{
					min = graph[visited[j]][unvisited[k]];
					min_index = k;
				}
			}
		}

		visited.push_back(unvisited[min_index]);
		unvisited.erase(unvisited.begin() + min_index);
		answer += min;
	}

	return answer;
}

 

 

 

 

 

 

 

출처

 

https://ansohxxn.github.io/algorithm/mst/

(C++) 최소 신장 트리 MST, 크루스칼 알고리즘, 프림 알고리즘