Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.1 kB
1
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll V,e;
ll graph[1001][1001];
int minKey(ll key[], bool mstSet[])
{
	int min = INT_MAX, min_index;

	for (int v = 0; v < V; v++)
		if (mstSet[v] == false && key[v] < min)
			min = key[v], min_index = v;

	return min_index;
}


void prims()
{
	ll parent[V];
	
	ll key[V];
	bool mstSet[V];

	
	for (int i = 0; i < V; i++)
		key[i] = INT_MAX, mstSet[i] = false;
	key[0] = 0;
	parent[0] = -1;

	for (int count = 0; count < V - 1; count++)
	{
		int u = minKey(key, mstSet);
		mstSet[u] = true;
		for (int v = 0; v < V; v++)
			if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
				parent[v] = u, key[v] = graph[u][v];
	}
    	cout<<"Edge \tWeight\n";
		
	for (int i = 1; i < V; i++)
	
		cout<<parent[i]<<" - "<<i<<" \t"<<graph[i][parent[i]]<<" \n";
}

int main()
{
    
    cin>>V>>e;
   
    for(ll i=0;i<e;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        graph[u-1][v-1]=w;
        graph[v-1][u-1]=w;
    }
	prims();

	return 0;
}