[Algorithm] 최소 스패닝(신장) 트리(MST)

Develop My Life·2022년 4월 7일
0

Algorithm

목록 보기
4/6

Spanning 트리란?

  • Spanning Tree 또는 신장 트리라고 불린다.
  • 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프
  • 조건
    • 본래의 그래프의 모든 노드를 포함해야한다.
    • 모든 노드가 서로 연결
    • 트리의 속성을 만족시킴(사이클이 존재하지 않음)

Minimum Spanning Tree란?

  • MST라고 불리고 최소 신장 트리라고도 불린다.
  • 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소이 Spanning Tree를 지칭함

Minimum Spanning Tree Algorithm

Kruskal's algorithm(크루스칼 알고리즘)

  1. 모든 정점을 독립적인 집합으로 만든다.
  2. 모든 간선을 비용을 기준으로 오름차순 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
  3. 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다.(최소 신장 트리는 사이클이 없으므로, 사이클이 생기지 않도록 하는 것이다.)(사이클이 생기는지 여부를 확인한다.)
  4. 모든 노드가 연결될 때까지 반복한다.

    탐욕 알고리즘을 기반으로 당장의 최소 비용을 선택하여 최적의 솔루션을 찾는다.
    키 포인트는 사이클이 생기는 여부를 확인하는 것 알고리즘이다.

Union-Find 알고리즘

  • 사이클이 생기는 여부를 확인하는 알고리즘

  • Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘

  • 노드들 중에 연결된 노드를 찾거나, 노드들을 서로 연결할 때(합칠 때) 사용

  • Disjoint Set

    • 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
    • 공통 원소가 없는(서로소) 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조를 의미한다.
    • 서로소 집합 자료구조

    동작 순서

    1. 초기화 : N개의 원소가 개별 집합으로 이뤄지도록 초기화
    2. Union : 두 개별 집합을 하나의 집합으로 합침, 두 트리를 하나의 트리로 만든다.
    3. Find : 여러 노드가 존재할 때, 노 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해, 각 그룹의 최상단 원소(루트 노드)를 확인한다.(사이클을 확인하는 기능), 루트 노트가 같다면 이미 트리로 연결되어 있기 때문에 해당 두 노드는 서로 연결하면 사이클이 생긴다.

구현

  • Edge라는 class를 생성한다.
    • 멤버 변수로 1차원 node 배열을 만들고 distance 변수를 만든다. node[0]에는 시작 노드, node[1]에는 도착 노드가 저장되어 있으며 distance에는 두 노드 사이의 거리가 저장된다.
    • 멤버 함수로 객체 생성 함수와 operator < 연산자 오버로딩을 만든다. 이는 sort 함수를 사용하기 위해 distance를 기준으로 오름차순 정렬되도록 하기 위함이다.
  • int getParent(int parent[], int x) 함수를 만든다. 이는 재귀적으로 부모 노드를 확인하기 위한 것으로 부모 노드의 번호가 반환된다.
  • void unionParent(int parent[], int a, int b) 함수를 만든다. 이는 두 노드를 합치는 것으로 노드 번호가 작은 것이 부모 노드가 된다.
  • int findParent(int parent[], int a, int b) 함수를 만든다. 이는 같은 부모 노드를 가지는지 확인하는 함수이며 같은 부모 노드를 가진다면 1을 반환하고 다른 부모 노드를 가진다면 0을 반환한다.
  • 부모 노드 저장 배열을 선언하고 모두 자기 자신을 부모로 하도록 초기화한다.
  • sort를 이용하여 거리 순으로 Edge를 오름차순 정렬한다.
  • 거리가 짧은 것부터 같은 부모를 가지는지 확인하고 다른 부모를 가지는 경우 합쳐서 부모 노드를 갱신하고 최소 거리에 누적합 시킨다.

코드

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

using namespace std;

//부모 노드를 재귀적으로 파악한다.
int getParent(int parent[], int x) {
	if (parent[x] == x) return x;
	return parent[x] = getParent(parent, parent[x]);
}

//각 부모 노드를 합친다. 이때 작은 값을 부모 노드로 한다.
void unionParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a < b) parent[b] = a; //작은 값을 부모 노드로
	else parent[a] = b;
}

//같은 부모 노드를 가지는지 확인한다. 
//같은 부모 노드를 가진다면 이미 연결되어 있다는 것을 의미한다.
int findParent(int parent[], int a, int b) {
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a == b) return 1; //같은 부모 노드를 가진다면 1 반환
	else return 0; //다른 부모 노드를 가진다면 0 반환
}

//Edge class 선언
class Edge {
public:
	int node[2]; //0번에는 시작 노드, 1번에는 도착 노드
	int distance; //노드 사이의 거리
	Edge(int a, int b, int distance) { //객체 생성자
		this->node[0] = a;
		this->node[1] = b;
		this->distance = distance;
	}
	bool operator <(Edge& edge) { //< 연산자 오버로딩을 하여 distance를 기준으로 비교되도록 한다.
		return this->distance < edge.distance;
	}
};

int main()
{
	vector<Edge> v;
	int parent[10001];
	int V, E;
	cin >> V >> E;

	for (int i = 0; i < E; i++) {
		int A, B, C;
		cin >> A >> B >> C;
		v.push_back(Edge(A, B, C));
	}

	//부모 노드 저장 배열을 모두 자기 자신으로 초기화한다.
	for (int i = 1; i <= V; i++) {
		parent[i] = i;
	}
	

	sort(v.begin(), v.end()); //distance를 기준으로 모든 Edge를 오름차순 정렬한다.

	int sum = 0; //최소 거리 저장, 0으로 초기화
	for (int i = 0; i < v.size(); i++) { //거리가 작은 Edge부터 시작한다.
		if (!findParent(parent, v[i].node[0], v[i].node[1])) { //부모 노드가 다를 경우, 즉 사이클이 생기지 않는 경우
			sum += v[i].distance; //거리 누적 합
			unionParent(parent, v[i].node[0], v[i].node[1]); //두 노드 합치기 union
		}
	}
	
	cout << sum << '\n'; //최소 거리 출력


}

0개의 댓글