티스토리 뷰
MST (Minimum Spanning Tree, 최소 신장 트리) 는 그래프에서 전체 가중치 합이 최소가 되도록 만든 트리입니다.
MST를 구하는 방식으로는 크루스칼 알고리즘, 프림 알고리즘이 있습니다.
크루스칼 알고리즘은 모든 edge를 정렬 후, 가중치 순으로 하나씩 이어보며, 사이클이 발생하면 다음 엣지를 대상으로 검사하는 방식입니다.
그러므로 복잡도는 정렬 시 사용되는 O(E log E) 입니다.
프림 알고리즘은 아무 노드를 시작점으로 해당 노드로부터 가장 가까운 노드를 이어나가는 것을 반복합니다.
이 때, 선택된 다음 노드와 연결된 노드와 시작점 노드 간의 거리를 업데이트하며, 다음 가까운 노드 선택 시 해당 거리를 기준으로 선택합니다.
프림 알고리즘의 경우, 가장 가까운 노드를 찾는다의 기준을 단순 탐색으로 할 지, 힙 구조를 이용할 지에 따라 복잡도가 달라집니다.
일반적으로는 힙 구조를 이용해 O(E log V) 의 복잡도를 가지며, 단순 탐색으로 가장 가까운 노드를 찾을 경우 O(V^2) 의 복잡도를 갖습니다.
완전 그래프와 같이 dense한 그래프가 아닌 경우, E << V^2 이므로 힙 구조를 사용하는 것이 일반적입니다.
다음과 같은 그래프가 주어져 있을 때 크루스칼 알고리즘과 프림 알고리즘으로 MST를 구하면 다음과 같습니다.
정답인 MST는 다음과 같습니다.
크루스칼 알고리즘 코드는 다음과 같습니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct edge{
int node1;
int node2;
int dist;
};
int find_parent(int node, int parent[])
{
if(node == parent[node])
return node;
parent[node] = find_parent(parent[node], parent);
return parent[node];
}
bool union_nodes(int node1, int node2, int parent[])
{
int parent1 = find_parent(node1, parent);
int parent2 = find_parent(node2, parent);
// 사이클 생성
if(parent1 == parent2) {
return true;
}
// 번호 작은 값이 부모
else if(parent1 > parent2) {
parent[parent1] = parent2;
}
else {
parent[parent2] = parent1;
}
return false;
}
bool compare(edge e1, edge e2)
{
// dist 오름차순 정렬용
if(e1.dist != e2.dist)
return e1.dist < e2.dist;
else {
if(e1.node1 == e2.node1)
return e1.node2 < e2.node2;
return e1.node1 < e2.node1;
}
}
void kruskal(vector<edge> &edges, vector<edge> &result, int &sum, int parent[])
{
// edge 길이 순 오름차순 정렬
sort(edges.begin(), edges.end(), compare);
for(auto e : edges) {
int node1 = e.node1;
int node2 = e.node2;
int dist = e.dist;
bool isCycle = union_nodes(node1, node2, parent);
if(isCycle == false) {
result.push_back(e);
sum += dist;
}
}
}
int main()
{
// 크루스칼 :
// 모든 엣지 대상으로 오름차순 정렬 후
// 엣지 순서대로 연결시키면서
// 사이클 발생하면 다음 엣지 체크
// 안 생기면 해당 엣지 추가
int graph[7][7] = {
{0, 29, -1, -1, -1, 10, -1},
{29, 0, 16, -1, -1, -1, 15},
{-1, 16, 0, 12, -1, -1, -1},
{-1, -1, 12, 0, 22, -1, 18},
{-1, -1, -1, 22, 0, 27, 25},
{10, -1, -1, -1, 27, 0, -1},
{-1, 15, -1, 18, 25, -1, 0}
};
vector<edge> edges;
int parent[7] = {0,1,2,3,4,5,6};
vector<edge> result;
int sum = 0;
for(int i = 0; i < 7; i++) {
for(int j = i + 1; j < 7; j++) {
if(graph[i][j] > 0) {
edge e = {i, j, graph[i][j]};
edges.push_back(e);
}
}
}
kruskal(edges, result, sum, parent);
cout << "MST total weights : " << sum << "\n";
cout << "MST edges : \n";
for(auto e : result) {
cout << e.node1 << " -> " << e.node2 << "\n";
}
}
프림 알고리즘 코드는 다음과 같습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 987654321
struct edge{
int node1;
int node2;
int dist;
};
void prim_basic(vector<edge> edges[], int distance[], bool visited[], int &sum, int nodeNum)
{
// 0번 노드부터 시작
distance[0] = 0;
visited[0] = true;
for(auto e : edges[0]) {
int nextNode = e.node2;
int dist = e.dist;
distance[nextNode] = dist;
}
// 전체 노드 대상 탐색
for(int i = 0; i < nodeNum - 1; i++) {
int minDist = INF;
int nextNode = -1;
// 현재 탐색 노드와 가장 가까운 노드 선택
for(int j = 0; j < nodeNum; j++) {
if(visited[j])
continue;
if(minDist > distance[j]) {
minDist = distance[j];
nextNode = j;
}
}
visited[nextNode] = true;
sum += minDist;
edge e = {i, nextNode, minDist};
// 선택된 다음 노드와 연결된 노드까지 거리 업데이트
for(auto e : edges[nextNode]) {
int linkedNode = e.node2;
int linkedDist = e.dist;
if(visited[linkedNode])
continue;
distance[linkedNode] = min(distance[linkedNode], linkedDist);
}
}
}
int main()
{
// 크루스칼 :
// 모든 엣지 대상으로 오름차순 정렬 후
// 엣지 순서대로 연결시키면서
// 사이클 발생하면 다음 엣지 체크
// 안 생기면 해당 엣지 추가
int graph[7][7] = {
{0, 29, -1, -1, -1, 10, -1},
{29, 0, 16, -1, -1, -1, 15},
{-1, 16, 0, 12, -1, -1, -1},
{-1, -1, 12, 0, 22, -1, 18},
{-1, -1, -1, 22, 0, 27, 25},
{10, -1, -1, -1, 27, 0, -1},
{-1, 15, -1, 18, 25, -1, 0}
};
vector<edge> edges[7];
for(int i = 0; i < 7; i++) {
for(int j = 0; j < 7; j++) {
if(graph[i][j] > 0) {
edge e1 = {i, j, graph[i][j]};
edges[i].push_back(e1);
edge e2 = {j, i, graph[j][i]};
edges[j].push_back(e2);
}
}
}
bool visited[7];
int distance[7];
for(int i = 0; i < 7; i++) {
visited[i] = false;
distance[i] = INF;
}
int sum = 0;
int nodeNum = 7;
prim_basic(edges, distance, visited, sum, nodeNum);
cout << "MST total weights : " << sum << "\n";
}
우선순위 큐를 이용한 프림 알고리즘은 다음과 같습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 987654321
struct edge{
int node1;
int node2;
int dist;
};
// priority queue 용 compare struct
struct compare{
// dist 기준 오름차순 정렬
bool operator()(const edge e1, edge e2) {
return e2.dist < e1.dist;
}
};
void prim_pq(vector<edge> edges[], int distance[], bool visited[], int &sum, int nodeNum)
{
priority_queue<edge, vector<edge>, compare> pq;
// 0번부터 시작
for(auto e : edges[0]) {
pq.push(e);
}
visited[0] = true;
while(!pq.empty()) {
int d = pq.top().dist;
int node = pq.top().node2;
pq.pop();
if(visited[node])
continue;
visited[node] = true;
sum += d;
for(auto e : edges[node]) {
int nextNode = e.node2;
if(visited[nextNode])
continue;
pq.push(e);
}
}
}
int main()
{
// 크루스칼 :
// 모든 엣지 대상으로 오름차순 정렬 후
// 엣지 순서대로 연결시키면서
// 사이클 발생하면 다음 엣지 체크
// 안 생기면 해당 엣지 추가
int graph[7][7] = {
{0, 29, -1, -1, -1, 10, -1},
{29, 0, 16, -1, -1, -1, 15},
{-1, 16, 0, 12, -1, -1, -1},
{-1, -1, 12, 0, 22, -1, 18},
{-1, -1, -1, 22, 0, 27, 25},
{10, -1, -1, -1, 27, 0, -1},
{-1, 15, -1, 18, 25, -1, 0}
};
vector<edge> edges[7];
for(int i = 0; i < 7; i++) {
for(int j = 0; j < 7; j++) {
if(graph[i][j] > 0) {
edge e1 = {i, j, graph[i][j]};
edges[i].push_back(e1);
edge e2 = {j, i, graph[j][i]};
edges[j].push_back(e2);
}
}
}
bool visited[7];
int distance[7];
for(int i = 0; i < 7; i++) {
visited[i] = false;
distance[i] = INF;
}
int sum = 0;
int nodeNum = 7;
prim_pq(edges, distance, visited, sum, nodeNum);
cout << "MST total weights : " << sum << "\n";
}
'알고리즘' 카테고리의 다른 글
| KD Tree 정리 (1) | 2024.05.01 |
|---|---|
| C++ vector, priority_queue 정렬 정리 (1) | 2024.04.21 |
| 유니온 파인드 정리 C++ (0) | 2024.04.21 |
| 벨만 포드 정리 C++ (2) | 2024.04.21 |
| 플로이드 워셜 C++ (0) | 2024.04.21 |
댓글