How to write a C Program to find MST(Minimum Spanning Tree) using Prim's Algorithm in C Programming Language ?
Solution:
/* * C Program to find MST(Minimum Spanning Tree) using Prim's Algorithm */ #include <iostream> using namespace std; int c = 0,temp1 = 0,temp = 0, MAX = 2222; struct node { int fr,to,cost; }p[2222]; int main() { int tamano, vertices, arcos, n1, n2, costo; cout << "Numero de nodos: " << endl; cin >> tamano; cin >> arcos; vertices = tamano-1; int a[tamano]; for (int i = 0; i < tamano; i++) { a[i] = 0; // CHANGE 0 por MAX } int b[tamano][tamano]; for(int k = 0; k < tamano; k++) { for (int i = 0; i < tamano; ++i) { b[k][i] = 0; } } cout << "Costo de arcos:" << endl; for(int k = 0; k < arcos; k++) { cin >> n1 >> n2 >> costo; b[n1][n2] = costo; b[n2][n1] = costo; } for(int k = 0; k < tamano; k++) { for (int i = 0; i < tamano; ++i) { cout << b[k][i] << " "; } cout << endl; } //Algoritmo: a[0] = 1; while (c < vertices) { int min = 999; for (int i = 0; i < tamano; i++) { if (a[i] == 1) { for (int j = 0; j < tamano; ) { if (b[i][j] >= min || b[i][j] == 0) { j++; } else if (b[i][j] < min) { min = b[i][j]; temp = i; temp1 = j; } } } } a[temp1] = 1; p[c].fr = temp; p[c].to = temp1; p[c].cost = min; c++; b[temp][temp1] = b[temp1][temp]=1000; } for (int k = 0; k < vertices; k++) { cout<<"source node:"<<p[k].fr<<endl; cout<<"destination node:"<<p[k].to<<endl; cout<<"weight of node"<<p[k].cost<<endl; } }
Learn More :
Find
- Find out the perfect number using c program
- Find g.c.d of two number using c program.
- Write a c program to find out NCR factor of given number
- How to Write a C program to find maximum between two numbers ?
- Write a C program to find maximum between three numbers ?
- C or C++ program to read marks of 4 subjects and find how many students are pass and fail with division
- C Program turnLEDOn to Drives Forward Until It Finds The Line
- Write overloaded function templates for finding the roots of the linear (a * x + b = 0) and square (a * x2 + b * x + c = 0) uravneniy.Zamechanie: in function to send coefficients of the equations.
- C Program to Find Random Number
- C Program To Find LCM and HCF Of Two Number Using Function - 2
- C Program to find LCM and HCF Of Two Number Using Recursion - 3
- C Program To Find LCM and HCF Of Two Number -1
- C Program To Find Length Of A String Including Blank Spaces, Tabs, And Other Special Characters
- C Program To Find Length Of String And Concatenate Two Strings
- C Program To Find Product Of Two No Using MACRO
- C Program To Find Reverse Of Any Digit Number
- C Program To Find Sum and Difference Of Two Matrices
- C Program To Find The Frequency Of A Number
- C Program To Find The Length, Reverse Of A String And To Check It Is Palindrome or Not
- C Program To Find The Maximum And Minimum Value In An Array
- C Program To Find Transpose Of A Matrix
- C Program To Find Union & Intersection Of Two Array
- C Program Finding the sum of Squares using Recursion
- C Program to Find NCR Of A Given Number Program
- C Program To Find Maximum Of Given Numbers
Minimum Spanning Tree
Prim
Algorithm
- C program generates a random number and uses an algorithm to generate 9 other numbers.
- C Program Fraction To Decimal
- C Program for distance vector algorithm to find suitable path for transmission
- C Program Bankers Algorithm Example
- C Program Dijkstra's Shortest Path Algorithm
- C Program to Implement Dijkstra's Algorithm