.png) | |
| 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.
