크루스칼의 최소 스패닝 트리 알고리즘

크루스칼 알고리즘은 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가해 간다. 가중치가 작다고 해서 무조건

간선을 트리에 더하는 것은 아니다. 결과적으로 사이클이 생기는 간선은 고려에서 제외해야 한다.

간선을 트리에 추가했을 때 이미 추가한 간선들과 합쳐 사이클을 이루는지 여부를 판단하는 부분이 크루스칼 알고리즘의 핵심이다.

이는 상호 배타적 집합 자료 구조를 통해 구현한다.

코드 ( C ++ )

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

// DisjointSet은 상호 배타적 집합 구현

struct DisjointSet {

vector<int> parent, rank;

DisjointSet(int n) : parent(n), rank(n) {

for (int i = 0; i < n; ++i)

parent[i] = i;

}

int find(int x)

{

if (x == parent[x])

return x;

return parent[x] = find(parent[x]);

}

void merge(int u, int v)

{

u = find(u), v = find(v);

if (u == v) return;

if (rank[u] > rank[v]) swap(u, v);

parent[u] = v;

if (rank[u] == rank[v]) ++rank[v];

}

};

const int MAX = 100;

// 정점의 개수

int V;

// 그래프의 인접리스트, (연결된 정점 번호, 간선 가중치) 쌍을 담는다.

vector<pair<int, int>> adj[MAX];

// 주어진 그래프에 대해 최소 스패닝 트리에 포함된 간선의 목록을 selected 에

// 저장하고 , 가중치의 합을 반환한다.

int kruskal(vector<pair<int, int>>& selected) {

int ret = 0;

selected.clear();

// ( 가중치, (정점1, 정점2))의 목록을 얻는다.

vector<pair<int, pair<int, int>>> edges;

for(int u =0; u< V; ++u)

for (int i = 0; i < adj[u].size(); ++i) {

int v = adj[u][i].first, cost = adj[u][i].second;

edges.push_back(make_pair(cost, make_pair(u, v)));

}

// 가중치 순으로 정렬

sort(edges.begin(), edges.end());

// 처음엔 모든 정점이 서로 분리되어 있다.

DisjointSet sets(V);

for (int i = 0; i < edges.size(); ++i) {

// 간선 (u, v)를 검사한다.

int cost = edges[i].first;

int u = edges[i].second.first, v = edges[i].second.second;

// 이미 u와 v가 연결되어 있을 경우 무시한다.

if (sets.find(u) == sets.find(v)) continue;

// 이 둘을 합친다.

sets.merge(u, v);

selected.push_back(make_pair(u, v));

ret += cost;

}

return ret;

}

int main()

{

V = 7;

adj[0].push_back(make_pair(1, 5));

adj[0].push_back(make_pair(2, 1));

adj[1].push_back(make_pair(0, 5));

adj[1].push_back(make_pair(3, 1));

adj[1].push_back(make_pair(6, 3));

adj[1].push_back(make_pair(5, 3));

adj[2].push_back(make_pair(0, 1));

adj[2].push_back(make_pair(3, 4));

adj[3].push_back(make_pair(2, 4));

adj[3].push_back(make_pair(1, 1));

adj[3].push_back(make_pair(4, 5));

adj[3].push_back(make_pair(5, 3));

adj[4].push_back(make_pair(3, 5));

adj[5].push_back(make_pair(3, 3));

adj[5].push_back(make_pair(6, 2));

adj[5].push_back(make_pair(1, 3));

vector<pair<int, int>> selected;

int sum = kruskal(selected);

cout << sum << endl;

for (int i = 0; i < selected.size(); ++i) {

cout << i+1 << "번째 연결 " << selected[i].first << " " << selected[i].second;

cout << endl;

}

}

참고 문헌 : 알고리즘 해결 전략