크루스칼 알고리즘(kruskal Algorithm), 최소 신장 트리(MST) c++ 구현

우리는 흔히 알고리즘 문제를 풀다보면 적은 비용으로 연결! 하는 문제를 자주 접하게 되는데요.

 

자주는 보지는 않지만 가끔씩 보면 까먹기 마련입니다. 저도 까먹고 풀다가 어..? 크루스칼 알고리즘인데 하는 생각이 들어서 이번에 다시 기억하고자 포스팅을 하려합니다.

 

크루스칼 알고리즘 (Kruskal Algorithm) -> 최소신장트리(MST) 구하기 위해 사용

앞서 위에서 말씀 드린듯이 적은 비용으로 연결하는 것이 핵심입니다.

 

무방향으로 연결된 노드와 간선이 주어졌을때 우리는 간선의 가중치(비용)에 대해서 모든 노드가 연결이 되어야 하는데 가중치(비용)이 최소화 되는것을 찾을때 사용하게 되는 알고리즘입니다.

 

최소 신장 트리(MST)가 뭐야?

 

신장 부분 그래프 (Spanning tree)에서 사용된 간선들의 가중치의 합이 최소인 트리를 일컫습니다.

다시 말해 노드와 간선에 대한 가중치가  주어졌을때 가중치(비용)를 고려하여 최소의 비용을 얻고자 하자는 것입니다.

 

최소 신장 트리(MST) 기본 특징

1. 간선의 가중치의 합이 최소

2. n개의 정점을 가지는 그래프는 반드시 n - 1개의 간선을 사용해야한다.

3. 2번을 만족하려면 결국 사이클이 포함되서는 안된다.

아! 결국 MST를 구현하기 위해 크루스칼 알고리즘을 사용하는 것이구나!

 

다시 본론으로 돌아와서 크루스칼알고리즘에 대해 알아보도록 하겠습니다.

 

크루스칼 알고리즘

앞서 말씀드렸듯이 최소 신장 트리를 구하기 위해 사용하는 알고리즘으로 그리디 알고리즘의 한 알고리즘입니다.

과정

1. 간선의 가중치를 오름차순으로 정렬한다. 2. 오름차순으로 정렬된 간선들을 탐색하며 해당 간선을 신장 트리에 포함할 때     1) 사이클이 발생한 경우 신장 트리에 포함하지 않고 넘어간다.    2) 사이클이 발생하지 않는 경우 신장 트리에 포함한다. 3. 모든 정점을 연결할 때까지 2번 과정을 계속 반복한다.

 

사실 말로만 보면 이해가 안되니 간단 과정에 대한 설명을 계속 보시면서 그림설명을 보시죠.

 

위의 그림을 보시게 되면 

 

1. 가중치(값) 을 기준으로 정렬을 하였습니다.

2. 1-2 / 1-5 는 사이클이 발생하지 않다가 2-5에서 그림과 같이 사이클이 발생하므로 이탈(제외) 시키고 넘어갑니다.

 

2번의 과정을 반복하면 최종적으로 1-2 / 1-5 / 2-3 / 4-5/ 가 연결된 모습을 이해하실 수 있습니다.

 

 

이해가 되셨나요? 잠깐만요!

 

이렇게만 이해하고 넘어가면 까먹기 쉽상입니다.

 

이 알고리즘에 대해 이해를 하였으니 제가 방금 풀었던 문제에 대해서 같이 풀어보는 시간을 가져보시는걸 추천드립니다.

https://bendeng-life.tistory.com/141

[프로그래머스 섬 연결하기] c++ (풀이,코드, 크루스칼 알고리즘)

 

부족한 글 읽어주셔서 감사합니다. 😀