[Algorithm] 최소 스패닝 트리(Minimum Spanning Tree)
👻 최소 스패닝 트리
스패닝 트리(Spanning Tree)란, 간선의 수를 최소화하여 모든 정점을 연결한 트리를 의미한다. 이 중에서도 가장 적은 가중치를 가지는 스패닝 트리를 최소 스패닝 트리(Minimum Spanning Tree)라고 한다. 간선을 최소화 한다는 의미는 사이클(Cycle)이 생기지 않는다는 의미이다. 사이클이 있는 트리는 스패닝 트리에 속하지 않는다.
💡 스패닝 트리의 특성
- N개의 정점이 있을 때 간선은 N-1개이다.
- 사이클을 가지지 않는다.
👻 Kruskal 알고리즘
크루스칼 알고리즘(Kruskal Algorithm)은 최소 스패닝 트리를 만드는 데 사용되는 대표적인 알고리즘이다. 탐욕적인(Greedy) 방법을 이용한다는 특성이 있다. 탐욕법은 현재 위치에서 가장 최적인 답을 선택하여 결과를 도출해내는 방법이다. 그래프에서 가중치가 가장 적은 간선을 우선 순위로 두고 연결하며 최소 스패닝 트리를 만들게 된다.
해당 알고리즘은 이전 시간에 알아보았던 서로소 집합(Disjoint Set) 개념을 이용하여 쉽게 구현이 가능하다. 최소 스패닝 트리를 만들기 위해선 다음과 같은 과정을 거치게 되는데, 이 때 유니온-파인드(Union-Find) 알고리즘을 사용하여 간단하게 만들 수 있다. 유니온-파인드 알고리즘은 서로소 집합이 가지는 대표적인 특성이다.
💡 최소 스패닝 트리 만들기
- 간선의 정보(인접 노드와 가중치)를 담은 배열 생성 후 가중치 오름차순으로 정렬한다.
- 디스조인트 셋을 이용하여 그래프의 노드 수만큼 집합을 만든다.
- 이 때, 부모 노드는 각자 자기 자신을 가지고 있다.
- 간선 배열을 순회하며 Find 연산을 이용해 연결이 되어있는지 확인한다.
- 연결이 되어있다면, 즉 같은 루트 노드를 가지고 있다면 사이클이 발생하므로 병합하지 않는다.
- 연결이 되어있지 않다면 Union 연산을 실행한다.
🌱 구현 연습
위에서 본 순서대로 최소 스패닝 트리를 구현해보자.
- 간선의 정보(인접 노드와 가중치)를 담은 배열 생성 후 가중치 오름차순으로 정렬한다.
struct CostEdge
{
int cost;
int u;
int v;
bool operator<(CostEdge& other)
{
return cost < other.cost;
}
};
vector<CostEdge> edges;
for (int u = 0; u < adjacent.size(); u++)
{
for (int v = 0; v < adjacent[u].size(); v++)
{
// 중복 등록 방지
if (u > v)
continue;
int cost = adjacent[u][v];
if (cost == -1)
continue;
edges.push_back(CostEdge{ cost, u, v });
}
}
std::sort(edges.begin(), edges.end());
인접 노드와 가중치 정보를 담은 구조체 CostEdge를 만들어주고, 오퍼레이터 <까지 재정의 해주었다. 해당 대소 비교 연산자는 sort 함수를 사용할 때 사용될 것이다.
- 디스조인트 셋을 이용하여 그래프의 노드 수만큼 집합을 만든다.
DisjointSet sets(vertices.size());
DisjointSet은 이전 시간에 만들었던 클래스를 재활용하였고, 생성자 선언 시 값을 넣어주면 해당 개수만큼의 집합을 _parent = 자기 자신, _rank = 1로 초기화하여 생성해준다.
- 간선 배열을 순회하며 Find 연산을 이용해 연결이 되어있는지 확인한다.
for (CostEdge& edge : edges)
{
// 같은 그룹이면 스킵 (안 그러면 사이클 발생)
if (sets.Find(edge.u) == sets.Find(edge.v))
continue;
// 두 그룹 병합
sets.Merge(edge.u, edge.v);
selected.push_back(edge);
ret += edge.cost;
}
디스조인트 셋의 Find 연산을 이용해 최상위 노드를 비교한다. 일치한다면 같은 집합 내에 있다는 뜻이므로 병합을 생략하고 다음 간선으로 넘어간다. 다른 집합에 속해있는 각각의 그래프라면 병합을 실행한다. 디스조인트 셋 자체에서 만들어 낸 그래프는 높이가 변경되고 최적화 되어 서로 연결되는 노드가 다르겠지만, 해당 알고리즘을 사용하여 만드는 트리는 인접 노드의 정보가 바뀌지 않기 때문에 그대로 잘 연결될 것이다.
- 결과
이렇게 되면 크루스칼 알고리즘을 실행했을 때 가중치 합의 최솟값이 반환될 것이고 그래프는 최소 스패닝 트리의 형태를 띠게 될 것이다.
👻 글을 마치며
이번 시간에는 크루스칼 알고리즘과 최소 스패닝 트리에 대해 알아보았다. 저번 시간부터 이어진 개념인 디스조인트 셋을 포함하여 개념을 완벽하게 이해할 수 있었다. 약간의 의문이었던 점들도 끝내 구글링을 통해 답을 찾아내긴 하였으나 맞다 아니다라고 판단해 줄 사람이 없어 일단은 혼자 개념을 이해한 상태긴 하다. (독학은 이런 점이 불편하다. 😂) 그래도 뭐 여기저기 많이 찾아봤으니 아예 전혀 다르게 개념 이해를 한 것만 아니면 이대로 알고 지내도 괜찮지 않을까라는 생각이 든다. (나중에 피드백 할 기회가 생기면 그 때 다시 개념을 잡아도 되니 말이다!)
Leave a comment