C++ MST 크루스칼 + 프림 알고리즘 코드

이미지 출처) Minimum Spanning Tree - Kruskal - Algorithms for Competitive Programming (cp-algorithms.com)

 

정답) 1 + 2 + 3 + 4 + 7 = 17 순회하는 순서가 추가되는 노드 순서에 따라 상이할 수 있음.

 

입력 데이터

From 1 To 2 Value 2

Edge형 구조체에 담음, int from, to, val;

9
1 2 2
1 4 1
1 5 4
2 4 3
2 3 3
2 6 7
3 6 8
4 3 5
5 4 9
0 0 0

크루스칼 알고리즘

핵심 포인트) 모든 부모 노드들을 포함하고 있을 int형 벡터와 Edge형 벡터, 한 방향만 연결.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef struct
{
	int from, to, val;
} Edge;

class Kruskal 
{
private:
	vector<int> parent;
	int res = 0;
	vector<Edge> edge;

public:
	
	Kruskal() 
	{
		Run();
	}

	void Union(int u, int v) 
	{
		u = Find(u);
		v = Find(v);

		if (u == v) 
			return;

		parent[u] = v;
	}

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

		else 
			return parent[u] = Find(parent[u]);
	}

	void Run() 
	{
		int V, E = 0;

		cin >> V;
		parent.resize(V + 1);

		// 부모 초기화
		for (int i = 1; i <= V; i++)
			parent[i] = i;

		// 간선의 정보 입력
		while (true)
		{
			Edge e;
			cin >> e.from >> e.to >> e.val;

			if (e.from == 0 &&
				e.to   == 0 &&
				e.val  == 0)
				break;

			edge.push_back(e);
			E++;
		}

		// 간선을 가중치로 오름차순 정렬
		sort(edge.begin(), edge.end(), [&](Edge e1, Edge e2) -> bool
			{
				return e1.val < e2.val;
			});

		for (int i = 0; i < E; i++) 
		{
			// 두 정점이 사이클을 형성하지 않는다면
			if (Find(edge[i].from) != Find(edge[i].to)) 
			{
				// 가중치값 더해줌
				res += edge[i].val;
				//cout << edge[i].val << endl;

				// MST 형성
				Union(edge[i].from, edge[i].to);
			}
		}
		cout << res << "\n";
	}
};

int main()
{
	Kruskal kruskal;
}

프림 알고리즘

핵심 포인트) 크루스칼 알고리즘하고 다르게 2차원형인 벡터와 우선순위 큐 (내림차순 정렬)를 응용한다. 방문 여부 표시와 양방향 연결

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

using namespace std;

#define y first
#define x second

using IntPair = pair<int, int>;

class Prim 
{
private:
	vector<bool> vis;
	vector<vector<IntPair>> adj;

public:
	
	Prim() 
	{
		Run();
		RunPrim(1);
	}

	void Run()
	{
		int V;

		cin >> V;
		adj.resize(V + 1);
		vis.resize(V + 1);

		// 간선의 정보 입력
		while (true)
		{
			int from, to, val;

			cin >> from >> to >> val;

			if (from == 0 &&
				to == 0 &&
				val == 0)
				break;

			adj[from].push_back({ to, val });
			adj[to].push_back({ from, val });
		}
	}

	void RunPrim(int start) 
	{
		int res = 0;
		vis[start] = true;

		// 우선순위 큐
		priority_queue<IntPair, vector<IntPair>, greater<IntPair>> pq;

		// 시작정점의 간선들 삽입
		for (int i = 0; i < adj[start].size(); i++) 
		{
			IntPair node = adj[start][i];
			pq.push({ node.y, node.x });
		}

		while (!pq.empty()) 
		{
			int cur = pq.top().y;
			int cost = pq.top().x;
			pq.pop();

			if (!vis[cur]) 
			{
				vis[cur] = true;
				res += cost;

				for (int i = 0; i < adj[cur].size(); i++) 
				{
					IntPair node = adj[cur][i];
					pq.push({ node.y, node.x });
				}
			}
		}
		cout << res;
	}
};

int main()
{
	Prim prim;
}

 

해당 사이트에서 발췌한 후 수정.

SuperM :: [AL] 7. 최소 비용 신장 트리(MST) 알고리즘 (tistory.com)