반응형
크루스칼(Kruskal) 알고리즘
크루스칼 알고리즘이란?
- 최소 비용 신장 트리(MST)를 찾는 알고리즘
* MST란?
Spanning Tree(신장) 중 가중치의 합이 가장 작은 것.
Spanning Tree는 모든 노드가 최소의 간선으로 연결된 그래프이다.
(노드 N일 때 N-1개의 간선으로 구성된다.)
- 탐욕법(Greedy)을 기반으로 간선을 추가해 가면서 MST를 찾는 것이다.
- 유니온 파인드 사용 시 시간 복잡도는 O(ElogE)이다.
(정렬 시 O(ElogE), E는 간선의 개수)
크루스칼 알고리즘 실행 과정
- 1. 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다.
- 2. 정렬된 간선들을 순서대로 살펴보면서 사이클이 만들어지지 않는 다면 간선을 선택한다.
(사이클이 형성되는지는 유니온 파인드를 사용하여 판단한다.)
- 3. N-1개의 간선을 선택했으면 종료한다.
- 초기 상태
- 가장 작은 값인 1 선택.
- 그 다음로 작은 2 선택
- 그 다음으로 작은 4를 선택할 경우 사이클을 이루게 된다.
그래서 그 다음으로 작은 5를 선택한다.
크루스칼 코드(C++)
// edges 벡터는 <가중치, <정점1, 정점2 >>
// nodeN은 노드의 개수
void kruskal(vector<pair<int, pair<int, int>>> edges,int nodeN)
{
int sumWeight = 0;
// 유니온 파인드 초기화
initUnion(nodeN);
sort(edges.begin(), edges.end());
for (auto e : edges)
{
// 같은 부모를 가지고 있는가 => 두 정점이 연결되어 있는가
// 두 정점이 연결되어 있지 않는 경우
if (!isSameParent(e.second.first, e.second.second))
{
sumWeight += e.first;
// 두 정점의 부모를 같게 설정 => 두 정점을 연결
unionParent(e.second.first, e.second.second);
cout << e.second.first+1 << " , "
<< e.second.second+1 << "연결 " << endl;
}
}
cout << "신장 트리 최소 연결 비용 : " << sumWeight << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<pair<int, pair<int, int>>> v{
{2,{0,1}},
{4,{0,2}},
{1,{1,2}},
{6,{0,3}},
{5,{2,3}},
{7,{1,3}}
};
kruskal(v, 4);
return 0;
}
반응형
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
다이나믹 프로그래밍(Dynamic Programming, DP) (0) | 2020.11.24 |
---|---|
최소 비용 신장 트리 - 프림(Prim) 알고리즘 (0) | 2020.11.23 |
최단 경로 알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘 (0) | 2020.11.23 |
최단 거리 알고리즘 - 벨만-포드(Bellman-Ford) 알고리즘 (0) | 2020.11.23 |
최단 경로 탐색 알고리즘 - 다익스트라(Dijkstra) (0) | 2020.07.16 |
댓글