Prim - MST - Hackerrank Problem Solution

Prim - MST

Hackerrank Problem Solution

Prim MST - Hackerrank Solution

PROBLEM STATEMENT

Given an undirected weighted connected graph, find the MST in it. The MST is defined as a subgraph consisting of all the vertices in the graph and: • There is only one exclusive path from a vertex to every other vertex. • The subgraph is of minimum overall weight among all subgraphs. • No cycles are created. One specific vertex S is fixed as the starting point of finding the subgraph using Prim's Algorithm. Prim’s method has the following parameter(s):

v: an integer that represents the number of vertices in the graph e: a two-dimensional array where each element contains three integers, two nodes numbers that are connected and the weight of that edge.

Input Format

The first line has two integers n and m, the number of vertices and edges in the graph.

Each of the next ‘m’ lines contains three integers x, y and r, the end nodes of e[i], and the edge's weight.

Constraints

Output Format

Print a single integer denoting the total weight of the MST.

Sample Input 0

3 3
1    2    1
2    3    2
3    1    4

Sample Output 0

3

---

SOLUTION IN C

#include<stdio.h> #include<stdlib.h> struct Edge{ int source; int destination; int weight; }; int Find(int parent[],int i){ if(parent[i]==-1) return i; return Find(parent,parent[i]); } void Union(int parent[],int x,int y){ int xSet=Find(parent,x); int ySet=Find(parent,y); parent[xSet]=ySet; } void MakeSet(int parent[],int n){ int i; for(i=0;i<n;i++) parent[i]=-1; } void Print(int arr[],int parent[],int n){ int i; for(i=0;i<n;i++) printf("parent of %d is %d\n",i,parent[i]); printf("\n\n"); } int cmpFunction(const void* a,const void* b){ struct Edge* p=(struct Edge*)a; struct Edge* q=(struct Edge*)b; return p->weight-q->weight; } int main(){ int n,e,src,dest,weight,i,root,sum=0; scanf("%d%d",&n,&e); struct Edge edges[e]; int parent[n+1]; for(i=0;i<e;i++){ scanf("%d%d%d",&edges[i].source,&edges[i].destination,&edges[i].weight); } scanf("%d",&root); MakeSet(parent,n+1); qsort(edges,e,sizeof(struct Edge),cmpFunction); for(i=0;i<e;i++){ if(Find(parent,edges[i].source) == Find(parent,edges[i].destination)){ continue; } else{ sum+=edges[i].weight; Union(parent,edges[i].source,edges[i].destination); } } printf("%d\n",sum); return 0; }

Share Share Tweet Share Share Share

LIKE?

SHARE If you find this useful, please share with your friends and Community.
CODE TOGETHER..GROW TOGETHER.