MCST=최소비용신장트리 - Kruskal 알고리즘 [모든노드최소비용연결트리-사이클없음]

MCST [Minimum Cost Spanning Tree]

신장트리(Spanning Tree) : 모든 정점(노드)을 방문하는 트리

트리 : 사이클이 없는 그래프를 말한다

그런데 간선에 비용이 있다 => 모든 정점을 방문하면서도 간선의 비용의 합이 최소인 트리를 신장트리라 한다

MCST = Minimum cost spanning tree

최소비용 신장트리로 알려진 알고리즘 들에는

1. 우선순위 탐색

2. Kruskal

3. Sollin

4. Prim

etc...

[1,2 가 성능이 좋다]

---

크루스칼 알고리즘 - 최소비용 신장트리( 사이클 없이 모든 노드를 연결하기 )

모든 노드를 사이클 없이 가장 적은 비용의 가선으로 연결 하는 알고리즘

[집합 Union-Find 알고리즘이 도입됨]

노드를 집합으로 보고 집합의 포함이 되어 있는지로 판별하면서 간선을 연결 한다

*모든 노드와 간선은 연결되어 있는 상황이고

*간선에는 비용이 있다

간선의 비용이 가장 적은 간선에 연결된 두개의 노드를 각각의 집합으로 만든다

그다음 순서의 간선을 선택 한다음 두개의 노드 모두가 기존 집합(각 한그룹에 두개가 모두)에 포함되어 있는 상태라면

경로가 사이클이 생김으로 간선을 연결하지 않는다, 기존 집합에 포함 하지도 않음(이미 조재 함으로)

자세한 내용은 C++ 알고리즘 참고