기술면접 알고리즘 [Graph] : 크루스칼 (Kruskal - Minimum Spanning Tree)

기술면접과 코딩테스트 준비를 위해 꼭 알아야 할 기초 알고리즘 관련 개념들과 코드를 정리하고 있습니다.

각 주제들은 GeeksForGeeks 의 Top 10 algorithms in Interview Questions 글에서 발췌하였습니다.

---

크루스칼 알고리즘 (Kruskal - Minimum Spanning Tree) 

크루스칼 알고리즘은 프림 알고리즘과 비슷하게 최소 신장 트리를 구하는 알고리즘이다. 다만 원리는 조금 다르다.

먼저, 모든 Vertex 들을 별도의 집합으로 만든다. 그 후, 모든 엣지들을 우선순위 큐에 넣고, 최소 가중치를 가진 녀석들부터 꺼내 두 Vertex 를 이어준다. 이때, 같은 집합인 경우는 연결하지 않는다. 집합이 같은지를 판별하는 것은 Union-Find 를 이용해 검사한다.

크루스칼은 먼저 모든 간선을 우선순위 큐에 넣어야 하므로, E * log(E) 의 비용이 들고, 총 E 번을 꺼내어 연결을 해 주어야 하므로 E * log(E) 가 든다. 따라서 시간 복잡도는 O(E * log(E) ) 가 된다.

#include <iostream>
#include <vector>
#include <queue>

struct Edge {
	int from;
	int to;
	int weight;
};

struct compare {
	bool operator()(Edge a, Edge b) {
		return a.weight > b.weight;
	}
};

class Graph {

int V;
std::vector<int> parent;
std::vector<Edge> edge;

public:	

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

	void make_union(int a, int b) {
		int x = find(a);
		int y = find(b);

		parent[x] = y;
	}

	void addEdge(int i, int j, int w) {
		edge.push_back({i, j, w});
	}

	void kruskals_mst() {
		std::priority_queue<Edge, std::vector<Edge>, compare> q;

		// store all edges in priority queue
		for (auto e : edge) {
			q.push(e);
		}

		// Initialize all Vertices as single set
		for (int i = 0; i < V; ++i)
			parent[i] = i;

		int added = 0;

		Edge cur;
		while (!q.empty()) {
			cur = q.top();
			q.pop();

			if (find(cur.from) == find(cur.to)) {
				continue;
			}

			make_union(cur.from, cur.to);
			std::cout << cur.from << " -- " << cur.to << " == " << cur.weight << std::endl;
		}

	}

	Graph(int v) : V(v), parent(std::vector<int>(v)) {}

};

// Driver Code
int main()
{
    Graph g(4);
    g.addEdge(0, 1, 1);
    g.addEdge(1, 3, 3);
    g.addEdge(3, 2, 4);
    g.addEdge(2, 0, 2);
    g.addEdge(0, 3, 2);
    g.addEdge(1, 2, 3);
 
    g.kruskals_mst();
    return 0;
}