최소 비용 신장 트리 - 크루스칼(Kruskal) 알고리즘.

크루스칼(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++)

 

 

유니온 파인드(Union - Find)

 

// 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;
}