크루스칼 알고리즘 (Kruskal Algorithm)

👉 크루스칼 알고리즘은 MST(최소 스패닝 트리) 찾는 알고리즘들 중 하나입니다. (나머지 하나는 Prim 알고리즘)

 

💡 MST란?

그래프의 연결성을 그대로 유지하는 가장 '저렴한' 그래프를 찾는 문제

 

크루스칼 알고리즘은 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤,

스패닝 트리에 하나씩 추가해 가는 방식으로 동작합니다.

하지만, 가중치가 작다고 해서 무조건 간선을 트리에 더하는 것이 아닌, 사이클이 생기는 간선을 고려해 제외 해줍니다.

 

👉 동작하는 과정

 

위 그래프를 보면 가중치가 1인 간선, 2인 간선, 3.. 순서대로 선택해 가고 있습니다.

 

이때 4번째에서 5번째를 보면 가중치가 3인 간선들이 남아 있는데도 불구하고,

4인 (c,d) 간선이 추가됩니다. 그 이유는 3인 간선들이 추가되면 트리에 사이클이 생기기 때문입니다.

트리에 사이클이 생긴다면, MST를 만족하지 못합니다.

 

📄 구현

크루스칼 알고리즘은 간선의 목록을 얻어서 가중치 순서대로 정렬한 뒤, 순회하며 이들을 스패닝 트리에 추가합니다.

이때 간선을 추가했을 때 사이클이 이루는지 여부를 판단하는 것이 중요합니다.

 

이를 위해 깊이 우선 탐색을 하며 역박향 간선을 찾는 해결책도 있지만, 복잡도가 높게 나오기 때문에,

간선의 양 끝 점이 같은 컴포넌트에 속해 있는 것을 고려해 상호 배타적 집합 자료 구조를 사용 할 수 있습니다.

 

💡 상호배타적 집합 자료 구조란?

참고 : https://withseungryu.tistory.com/40?category=753127

Union-Find, Disjoint Set (유니온-파인드, 상호 배타적 집합)

 

👉 구현 코드

const int MAX_V = 100; //문제에 따라 다릅니다.

int V; //정점의 개수

vector<pair<int, int>> adj[MAX_V]; // 그래프의 인접 리스트 (연결된 정점 번호, 간선 가중치)

struct OptimizedDisjointSet {
	vector<int> parent, rank; 
	OptimizedDisjointSet(int n) : parent(n), rank(n, 1) {
		for (int i = 0; i < n; ++i)
			parent[i] = i;
	}

	int find(int u) {
		if (u == parent[u]) return u;
		return parent[u] = find(parent[u]); 
	}

	void merge(int u, int v) {
		u = find(u); v = find(v);
		if (u == v) return;
		if (rank[u] > rank[v]) swap(u, v);
		parent[u] = v;
		if (rank[u] == rank[v]) ++rank[v];
	}
};


int kruskal(vector<pair<int, int>> selected) {
	int ret = 0;
	selected.clear();

	vector<pair<int, pair<int, int>>> edges; //(가중치, (정점1, 정점2))
	for(int u=0; u<V; ++u)
		for (int i = 0; i < adj[u].size(); ++i) {
			int v = adj[u][i].first, cost = adj[u][i].second;
			edges.push_back(make_pair(cost, make_pair(u, v)));
		}

	sort(edges.begin(), edges.end()); // 가중치 순으로 정렬
	
	OptimizedDisjointSet sets(V);

	for (int i = 0; i < edges.size(); ++i) {
		int cost = edges[i].first;
		int u = edges[i].second.first, v = edges[i].second.second;
		
		if (sets.find(u) == sets.find(v)) continue; //이미 u와 v가 연결되어있을경우

		sets.merge(u, v);
		selected.push_back(make_pair(u, v));
		ret += cost;
		
	}
	return ret;
}

 

💡 시간복잡도 : O(E* logE)

 

궁금하신 것이 있으시면 언제든지 댓글 달아주세요!