SnapTimes

News In A Snap!!

C++ Programs: Kruskal’s Algorithm

June 2, 2015

C++_Main

What is Kruskal’s Algorithm?

Kruskal’s algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

Code


//Kruskal's Algorithm

#include <iostream.h>

#include<conio.h>

int n, m, mincost, i, j;

struct Edge {

int u, v, wt;

};

int checkCycle (Edge e, int*);

int main() {

// Creating graph of n vertices & m edges

clrscr();

cout << "Enter the number of vertices in the graph: ";

cin >> n;

cout << "Enter the number of edges in the graph: ";

cin >> m;

int path[50+1];

struct Edge e[50];

struct Edge t;

for (i=0; i<m; i++) {

cout << "Enter 2 vertices and weight of edge " << i+1 << endl;

cout << "First vertex: ";

cin >> e[i].u;

cout << "Second vertex: ";

cin >> e[i].v;

cout << "Weight: ";

cin >> e[i].wt;

cout << endl;

}

// Sorting the edges in ascending order of weights

for (i=0; i<=m-1; i++) {

for (j=0; j<m-i-1; j++) {

if (e[j].wt > e[j+1].wt) {

t = e[j];

e[j] = e[j+1];

e[j+1] = t;

}

}

}

// Initializing the path array

for (i=1; i<=n; i++) {

path[i] = 0;

}

// Counts the number of edges selected in the tree

i = 0;

// Counts the number of edges selected or discarded

j = 0;

mincost = 0;

cout << endl;

while ((i!=n-1) && (j!=m)) {

cout << "Edge ("

<< e[j].u << ", " << e[j].v << ") "

<< "with weight " << e[j].wt << " ";

if (checkCycle(e[j], path)) {

mincost = mincost + e[j].wt;

i++;

cout << "is selected";

} else {

cout << "is discarded";

}

cout << endl;

j++;

}

if (i!=n-1) {

cout << "Minimum spanning tree cannot be formed ";

}

getch();

return 0;

}

int checkCycle (Edge e, int* path) {

int u = e.u, v = e.v;

while (path[u] > 0)

u = path[u];

while (path[v] > 0)

v = path[v];

if (u != v) {

path[u] = v;

return 1;

}

return 0;

}

Output

krushkal


SnapTimes.in | Get Tech Addicted...
About Us | Contact Us | ©2017