공부하는 식빵맘 👱‍♀️

공부하는 식빵맘 👱‍♀️

반갑습니다 :)

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

Date:     Updated:

카테고리:

태그:

🌜 신장 트리 Spanning Tree

  • 어떤 하나의 그래프 中에서 1️⃣ 모든 정점을 포함하되 2️⃣ 최소로 연결 되도록 일부 간선들을 선택하여 만든 트리. 단, 3️⃣ 사이클이 생성되선 안된다. 어떤 그래프로 신장 트리를 만들 때 사이클을 만드는 간선은 선택하지 않는다.
    • 최소 연결
      • 👉 간선의 수가 가장 적다.
        • 정점의 수가 n개 일 때, Spanning Tree의 간선 수는 언제나 n - 1개.
      • 👉 사이클이 발생해선 안된다. 사이클이 있다는 것 자체가 최소로 연결되지 않았다는 뜻이므로!
        • 1 - 2 - 3 으로 연결 되어 있다면 1 과 3 은 직접적으로 연결되있는건 아니더라도 연결된 것으로 본다. 통행이 가능해지므로. 따라서 사이클을 형성하도록 1 - 3 을 연결시킬 필요가 없는 것이다.
  • DFS, BFS 를 사용하여 그래프에서 신장 트리를 찾을 수 있다.
  • 한 그래프에서 스패닝 트리가 여러개 있을 수 있다.

참고 블로그 https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html


🌜 최소 비용 신장 트리 Minimum Spanning Tree

가장 적은 비용으로 모든 노드를 연결하고자 할 때

모두 연결하되 최소 비용으로 연결하는 그런 문제들은 MST를 만들어야 하는 케이스라고 보면 된다. 크루스칼 혹은 프림 알고리즘으로 MST를 만들면 된다.

  • 그래프 내의 모든 정점들을 포함하되 최소로 연결되며 최소 비용으로 포함하는 트리. 👉 가중치의 합이 최소.
    • 신장 트리 특징
      • 1️⃣ 반드시 n-1개의 간선만을 사용 한다.
      • 2️⃣ 사이클을 가져선 안된다.
    • 최소 비용 신장 트리만의 특징
      • 3️⃣ 간선의 가중치의 합이 최소여야 한다.

최소 비용 신장 트리로 만든다는 것은, 그래프에서, 모든 정점이 연결되어 있게 하되, 간선을 n-1개를 선택하여(최소로 연결), 선택된 간선들의 가중치의 합이 최소이도록 간선을 선택한다는 것이다. 단 사이클을 만들지 않도록 선택해야 한다.

  • 어떤 그래프에서 MST 만드는 방법 2 가지
    1. 크루스칼 알고리즘 👉 간선 선택
      • 간선이 적은 그래프를 MST로 만들 때 적합
      • 사이클 검사가 필요하다. (간선을 선택하므로 트리가 여러개 생길 수 있음. 사이클이 생기지 않도록 선택애야 함.)
    2. 프림 알고리즘 👉 정점 선택
      • 간선이 많은 그래프를 MST로 만들 때 적합
      • 시작 정점을 정해두고 시작한다.
      • 사이클 검사가 필요하지 않다. (인접한 정점들 중에서 선택해 나가므로 트리는 시작 정점에서 발생했던 단 하나의 트리만 유지되며 정점들을 선택해 나감으로써 하나의 트리를 확장해나가는 식이다. 따라서 이 과정에선 사이클이 생길 일이 없다.)

참고 블로그 https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html


💛 크루스칼 알고리즘 Kruskal

간선을 선택해나감.

✨ 무조건 가장 비용이 작은 간선부터 선택해 나간다는 점에서 Greedy한 알고리즘이다. 단, 선택한 간선의 두 정점이 연결되 있지 않는 경우에만 해당 간선을 선택한다. 즉, 사이클을 이루지 않도록.

MST 집합은 공백에서 시작한다.

  1. 가중치 순서대로 간선들을 오름차순 정렬한다.
  2. 오름 차순 정렬된 간선들을 차례대로 살펴보며 두 정점이 아직 연결되 있지 않는, 즉 사이클을 형성하지 않는 간선이면 선택한다. 형성한다면 그 간선은 무시하고 다음 차례로 넘어 간다.
    • 정점들의 부모가 같다면(즉, 같은 그룹이라 서로 통행이 가능하다면) 사이클이 형성되는 것이고, 부모가 같지 않다면(즉, 서로 통행이 불가능 하다면) 사이클이 형성되지 않는것이다.
    • Kruskal 알고리즘이 Union-Find 알고리즘과도 연관이 있는 이유. Union-Find 포스트
  3. 선택한 간선을 MST 집합에 Union 시킨다.
    • 2~3 과정을 선택한 간선의 수가 n-1개가 될 때까지 반복한다.

적은 숫자의 간선을 가지는 그래프라면 크루스칼 알고리즘으로 MST를 만드는게 적합하다. 크루스칼 알고리즘은 간선을 정렬하는 시간에 좌우되기 때문이다.

이해를 위한 그림

image

정점 2와 0은 현재 통행이 가능하도록 연결 되어 있는 같은 그룹이다.(트리 개념으로 치면 부모 정점이 같은 셈이다.) 그런 상태에서 0 - 2 간선을 추가하려고 하면 사이클이 발생하므로 선택하지 않는다.

✨모든 정점의 부모 정점이 같아진다면, 즉 모든 정점이 하나의 그룹에 속하면서 통행이 가능해진다면! 즉, 하나의 트리로 합쳐져 완성된다면! 작업을 종료한다.

코드

  • Union-Find 알고리즘을 사용한다.
    • union 👉 연결하기(merge)
      • 두 정점을 하나의 트리(같은 부모를 가진 같은 그룹)으로 합치고자 할 때
    • find 👉 연결 되어 있는지 확인
      • 같은 부모를 가지는지, 즉 같은 그룹인지를 확인하고자 할 때
      • 같은 부모라고 판단된다면 이 간선은 추가하면 안된다. 사이클을 형성하게 되기 때문에!

크루스칼 알고리즘 코드 참고 나동빈님 블로그 https://blog.naver.com/ndb796/221230994142

프로그래머스 섬 연결하기 풀이 코드.

#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;
}

parents에서 각 인덱스는 정점을 뜻하며 원소는 해당 정점의 부모 정점을 가리킨다. 정점이 4 개라면 초기값은 [0, 1, 2, 3]으로 자기 자신이 부모다. 최종적으로 [0, 0, 0, 0]이 되어 모든 정점의 부모 정점이 같아진다면, 즉 하나의 트리로 완성되었다면 종료한다. 0 과 2 정점이 이어진다면 [0, 1, 0, 3]이 될 것이도 1 과 3 이 이어진다면 [0, 1, 0, 1]이 될 것이고 1 과 0 이 이어진다면 최종적으로 [0, 0, 0, 0]이 될 것이다.

  1. int getRoot(vector<int>& parent, int x)
    • x 정점의 부모 정점을 리턴한다.
  2. void unionParent(vector<int>& parent, int a, int b)
    • 두 정점 a, b를 같은 부모를 가진 하나의 트리로 병합한다.
    • 더 작은 값의 부모로 통합한다.
  3. bool find(vector<int>& parent, int a, int b)
    • 두 정점 a, b가 같은 부모를 가졌는지를 확인한다.
    • True 라면 또 똑같은 a - b를 잇는 간선을 추가한다면 사이클이 형성된다.
sort(costs.begin(), costs.end(), compare);

비용순서대로 가장 최소비용을 가진 간선이 앞에 오게 오름차순 정렬.

    vector<int> parents(n);
    
    for(int i = 0; i < parents.size(); i++)
        parents[i] = i;

parents의 초기화는 자기 자신이 부모이게끔.

    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];
        }
    }
  • 부모가 같지 않을 때만 (같다면 이 두 정점을 추가하면 사이클이 형성되게 되므로 추가하면 안된다.)
    • 두 정점을 합치기
      • 기존에 이미 다른 트리에 속해 있다면 이제 그 트리와 합쳐질 것이고
      • 그런적 없었다면 자기 자신이 부모인 지금 상태에서 해당 트리로 연결될 것이다.
    • 비용 더해주기


💛 프림 알고리즘 Prim

시작 정점에서 출발하여 정점을 선택해나감.

✨ 프림 또한 Greedy하다. 시작 할 때 시작 정점만 MST 집합에 포함시키고 현재까지의 MST 집합에 포함된 정점들 중에서 인접한 정점들 中 가중치 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다. 크루스칼 알고리즘은 이미 선택 완료되어 MST 집합에 들어가 있는 ‘간선’들은 다시 고려하지 않았던 반면, 프림 알고리즘은 이미 선택 완료되어 MST 집합에 들어가 있는 ‘정점’들의 인접 정점들 중에서 최소 간선을 가지는 정점을 선택하게 된다.

프림 알고리즘은 시작점을 정해놓고 시작점에서 가까운 정점들을 선택하면서 MST 를 만들어가기 때문에, 크루스칼 알고리즘과 다르게 사이클을 이루지 않는다. 정점을 선택하는 식이기 때문에 트리 하나를 처음부터 끝까지 유지하게 되므로 다시 거슬러 올라가 정점을 잇는 일은 있을 수 없다. 크루스칼 알고리즘은 최소 비용 간선을 선택하기 때문에 서브 트리가 여러개 생길 수 있고 어느 그룹(트리)에 속한 정점인지도 확인해야 하며 이 트리들을 합치는 과정도 필요하기에 사이클이 생길 수 있지만 프림 알고리즘은 인접한 정점을 선택하기 때문에 트리가 여러개 생기지 않고 처음부터 단 하나의 트리를 유지하고 확장하는 식이라서 프림 알고리즘 과정에선 사이클이 생기지 않는다. 👉 사이클 검사 및 합치는 과정인 Union-Find 과정이 필요 없음.

  1. 시작 정점 아무거나 선택하여 MST에 포함시킨다.
  2. 현재까지의 MST 집합에 포함되어 있는 이전에 선택 완료 되었던 정점들의 인접 정점(MST에 포함되어 있지 않은)들 中 최소 가중치 간선을 가진 정점을 선택하여 MST에 포함한다.
    • 이 과정이 프림 알고리즘의 성능을 결정한다. 따라서 정점이 아주 많은 그래프라면 그냥 크루스칼 알고리즘을 선택하여 MST를 만드는게 더 나을 것이다.
    • visited - unvisitied 사이의 인접 정점들의 가중치를 Min Heap 우선순위큐에 저장하여 빼올 수도 있다. 이러면 시간 복잡도는 \(O(n^2)\) 보단 작게 된다.
    • 2 번의 과정을 n-1개 간선을 가질 때까지 반복. 혹은 2 번의 과정을 MST가 n개의 정점을 모두 포함할 때가지 반복.

이해를 위한 그림

image

코드

코드 참고 min:D’s님 블로그 https://mind-devlog.tistory.com/89 이 분의 풀이 코드 덕분에 프림 알고리즘을 이해할 수 있었다.

프로그래머스 섬 연결하기 풀이 코드.

#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;
}
  • 시작 정점을 미리 정하고 시작한다.
  • 정점을 선택해가며 하나의 트리를 확장하는 방식이므로
    • 방문한 정점들을 담는 visited, 아직 방문하지 않은 정점들을 담는 unvisited 벡터를 따로 둔다.
      • 최종적으론 unvisited이 비워지고 모든 정점이 visited에 속하게 된다.
      • 시작은 visited에 시작 정점만 속하고 unvisited엔 나머지 정점들
	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];
	}

graph[i][j] 값은 i 정점과 j 정점 사이의 가중치(비용) 값을 담는다.

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

	visited.push_back(0);
	for (int i = 1; i < n; i++)
		unvisited.push_back(i);
  • visited의 초기 상태는 [0]. 시작 정점을 0 정점으로 정해놓고 시작했다.
  • unvisited의 초기 상태는 [1, 2, 3]이 된다. 0을 제외한 나머지 정점들.
    • 따라서 i = 1부터 돌렸다.
	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;
	}
  • 첫 번째 for 문 👉 n - 1 번 돈다. 시작 정점 제외한 나머지 n - 1 개의 정점 선택 과정
    • i는 곧 현재까지 방문한 정점의 개수가 되기도 한다.
  • 두 번째 for 문 👉 visited 순회
    • visited엔 i개의 방문 정점이 들어있기 때문에 i까지만 검사하면 된다.
  • 세 번째 for 문 👉 unvisited 순회
    • 아직 방문하지 않은 나머지 n - i개의 정점이 들어 있다.
  • visited와 unvisited 사이에서 인접해 있는 정점들 중 가중치가 가장 작은 간선을 가진 정점을 선택해야 한다.
    • 인접해 있는 정점 👉 (graph[visited[j]][unvisited[k]] > 0
    • 더 작은걸 찾았다면 업데이트 👉 min > graph[visited[j]][unvisited[k]]
      • 최종적으로 결정된 min을 가진 unvisited 정점을 삭제하고 visited에 추가해야 하므로 min 업뎃할 때 min_index에 해당 unvisited 정점을 보관해두어 같이 업데이트
  • 결정되면
    • visited에 unvisited[min_index]을 추가한다.
    • unvisited[min_index]는 삭제한다.
    • 비용 합산


🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Algorithm 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)