Prim MST

크루스칼 알고리즘은 간선에 집중하여 최소스패닝트리를 구하고,

프림 알고리즘은 노드에 집중해서 최소 스패닝 트리를 구할 수 있다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <queue>

using namespace std;

int ch[30],V,E;

bool check(){
	for(int i=1; i<=V; i++){
		if(ch[i]==0) return false;
	}
	return true;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i,a,b,c,ans=0;
	
	vector<pair<int,int> > v[30];
	
	scanf("%d %d",&V, &E);
	for(i=0; i<E; i++){
		scanf("%d %d %d",&a, &b, &c);
		v[a].push_back(make_pair(b,c));
		v[b].push_back(make_pair(a,c));
	}
	
	priority_queue<pair<int, int> > pQ;
	
	pQ.push(make_pair(0,1));
	
	
	while(1){
		auto cur = pQ.top();
		pQ.pop();
		int node = cur.second;
		if(ch[node]==1){
			continue;
		}
		
		ans+= -cur.first;
		ch[node] = 1;
		for(i=0; i<v[node].size(); i++){
			if(ch[v[node][i].first]==0){
				pQ.push(make_pair(-v[node][i].second, v[node][i].first));
				
			}
			
			
		}
		
		if(check()) break;
	}
	
	
	printf("%d ",ans);
	
	

	
}

 

 

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>

using namespace std;

int ch[30];
struct Edge{
	int e;
	int val;
	Edge(int a, int b){
		e=a;
		val=b;
	}
	bool operator<(const Edge &b)const{
		return val>b.val;
	}
};


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	priority_queue<Edge> Q;
	vector<pair<int,int> > map[30];
	int i,n,m,a,b,c,res=0;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d %d",&a, &b, &c);
		map[a].push_back(make_pair(b,c));
		map[b].push_back(make_pair(a,c));
	}
	Q.push(Edge(1,0));
	while(!Q.empty()){
		Edge tmp=Q.top();
		Q.pop();
		int v=tmp.e;
		int cost=tmp.val;
		
		if(ch[v]==0){
			res+=cost;
			ch[v]=1;
			for(i=0; i<map[v].size();i++){
				Q.push(Edge(map[v][i].first, map[v][i].second));
			}
		}		
	}
	
	printf("%d",res);
}