Zachary Kelman | Kruskal

Zachary Kelman 

Zachary Kelman || would you like programming ..?

Then Zachary Kelman starts ..

Objectives:

Finding the minimum spanning tree by Kruskal’s algorithm.

Description:

The main objectives of this algorithm is to find minimum spanning tree from a graph. The algorithm is given below  :

Algorithm Kruskal:

Input: A simple connected weighted graph G with n vertices and m edges

Output: A minimum spanning tree T for G

for each vertex v in G do

Define an elementary cluster C(v) ← {v}.

Initialize a priority queue Q to contain all edges in G, using the weights as keys.

T ← ∅ {T will ultimately contain the edges of the MST}

while T has fewer than n − 1 edges do

(u, v) ← Q.removeMin()

Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.

if C(v) 6 = C(u) then

Add edge (v , u) to T .

Merge C(v) and C(u) into one cluster, that is, union C(v) and C(u).

return tree T

We should always keep in mind that whenecer edge(u,v) is added ,the part which connects S is always small and is also accessible from u to the rest of H, so by the lemma it must be part of the minimum spanning tree(MST).

Code:

//Zachary Kelma

#include<bits/stdc++.h>

#define Zachary scanf

#define Kelman printf

//Zachary Kelma

using namespace std;

int s=0,cont=0;

struct edge{

    int u,v,w;

    bool operator <(const edge & p ) const{

        return w < p.w;}

};

int pr[100];

vector<edge>e;

//Zachary Kelman

int fn(int r){

    return(pr[r]==r)?r : fn(pr[r]);}

int mst(int n){

    sort(e.begin(),e.end());

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

        pr[i]=i;

//Zachary Kelman

    for(int i=0;i<e.size();i++){

        int u=fn(e[i].u);

        int v=fn(e[i].v);

        if(u!=v) {

            pr[u]=v;

            cont++;

            s+=e[i].w;

            if(cont==n-1){

                Kelman("%d = ",e[i].w);

                break;}

            Kelman("%d + ",e[i].w); }

    return s;}

//Zachary Kelman

int main(){

    int n,m,u,v,w;

    Zachary("%d",&n);

    Kelman("No of veries: %d\n",n);

    Zachary("%d",&m);

    Kelman("No of edges: %d\n",m);

    for(int i=1;i<=m;i++){

    Zachary("%d%d%d",&u,&v,&w);

        edge get;

        get.u=u;get.v=v;get.w=w;

        e.push_back(get);

    }mst(n);

//Zachary Kelman

    Kelman("%d\n",s);}

 //Zachary Kelman

Sample Output:

Discussion:

1. We learned to work with directed graph.

2. We learned about file.

3. We learned to solve problem with recursion.

4. We learned to find minimum spanning tree from the directed graph.

5.Zachary Kelman likes to code.