There are two methods Prim's algorithm and Kruskal's algorithm can be seen as examples of applying greedy algorithm design strategies.

Prim's Algorithm--select the point with the shortest distance between the adjacent points of all vertices in the set S (not belonging to S) to join the set S

Kruskal's Algorithm--select the shortest edge each time that does not form a loop

They all use the following minimum spanning tree properties: if there is only one edge with the minimum weight on the way, then this edge is included in any minimum spanning tree.

Let G=(V,E) be a connected weighted graph, and U be a proper subset of V. If (u,v) belongs to E, and vertex u belongs to U, and vertex v belongs to V-U, and among all such edges, (u,v) has the smallest weight c[u][v], then there must be a A minimum spanning tree with (u,v) as one of its edges. This property is also sometimes referred to as the MST property.

the

Prim's Algorithm--select the point with the shortest distance between the adjacent points of all vertices in the set S (not belonging to S) to join the set S

Each step of Prim's algorithm adds an edge to a growing tree that starts with a single vertex and then adds V−1 edges. Always add the cutting edge with the smallest weight of the cut formed by the growing tree and the part of the tree other than the growing tree.

Description: First, there is only one vertex S={1} in S, then, as long as S! =V means that the points have not been taken yet, greedily select the edge (i,j) with the smallest distance S that satisfies the condition, add the vertex j that is not in the S set to the S set, and loop until the end of S=V

​

What are the conditions? -- Select the one with the shortest distance between the adjacent points of all vertices in the set S

The process of selecting edges according to the Prim algorithm is shown in the figure on the following page

​​

 

Kruskal's Algorithm--select the shortest edge each time that does not form a loop

First, the n vertices of G are regarded as n isolated connected branches. Sort all edges from small to large.

Then start from the first edge, view each edge in the order of increasing edge weight, and connect two different connected branches as follows: When viewing the k th edge (v,w), if the endpoint v and When w is the vertices in the current two different connected branches T1 and T2 respectively, use the edge (v,w) to connect T1 and T2 into a connected branch, and then continue to check the k+1 th edge; if the endpoint v and If w is in the current same connected branch, then directly check the k+1 th edge.

This process continues until only one connected branch remains.  

​ 

  pseudocode

Code Prim

//Minimum Spanning Tree Prim's Algorithm 
/*Add the shortest side that can be reached each time 
closest[j]is the adjacent vertex of j in S,
First find out the vertex j with the smallest value of c[j][closest[j]] (ie lowcost[j]) in V-S,
Then select the side (j,closest[j]) according to the array closest, and then add j to S,
Finally, modify the closest and lowcost 
*/
#include<iostream>
#include<fstream>
#include<string.h>
#define INF 0x3f3f3f
using namespace std;

ifstream fin("4d6.txt");
int n,m;//n vertices, m edges
int c[100][100];
int s[1000];//s[i]=1 means that vertex i has been picked out and is in the spanning tree 
int closest[1000];//closest[j] is the adjacent vertex of j in S
int lowcost[1000];//lowcost[j] is c[j][closest[j]] 
void Prim(){
	for(int i=2;i<=n;i++){//initialization 
		lowcost[i]=c[1][i];
		closest[i]=1;
		s[i]=0; 
	}
	s[1]=1; 
	for(int i=1;i<n;i++){
		int t=INF;
		int j=1;//start from the first node 
		for(int k=2;k<=n;k++){
			if(lowcost[k]<t && !s[k]){
				t = lowcost[k]; 
				j=k;
			}
		}
		cout<<"("<<closest[j]<<","<<j<<")= "<<lowcost[j]<<endl;
		s[j]=1;
		for(int k=2;k<=n;k++){
			if(c[j][k]<lowcost[k] && !s[k]){
				lowcost[k] = c[j][k];
				closest[k]=j;		
			}
		}
	}
}
int main(){
	//cin>>n>>m;
    fin>>n >> m;
	int i,j;
	int x,y,z;
	for(i=0;i<=n;i++) //initialization 
		for(j=0;j<=n;j++)
			c[i][j]=INF;
	for(i=0;i<m;i++){
		fin>>x>>y>>z;
		c[x][y]=z;
		c[y][x]=z;
	} 
	cout<<"Prim:The order of joining is:\n";	
	Prim();
	return 0;
}

Code kruskal

//Minimum Spanning Tree Kruskal
//The edge with the smallest weight in each selection 
#include<iostream>
#include<string.h>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("4d6.txt");
int n,m;//n vertices, m edges
int s[1000];//And check s[i]=1 means that the parent node of vertex i is 1, that is, i and 1 are in a set
struct edge{
	int u,v,w;//The weight from vertex u to vertex v is w (undirected graph) 
}g[1000];
bool comp(edge a,edge b){
	return a.w < b.w;
}
void Init(){
	for(int i=0;i<m;i++){
		s[i]=i;//Initialization, now each is king, and he is a collection
	}
} 
int Find(int x){//query root node
	if(s[x]==x)
		return x;
	else{
		s[x]=Find(s[x]);  //By the way, the parent node is also set as the root node, and the path is compressed
		return s[x];
	}	
}
void Merge(int x,int y){//Merge, merge y into x, that is, set the parent node of y to x
	s[Find(y)] = Find(x);
}
void Kruskal(){
	int x,y;
	for(int i=0;i<m;i++){
		x = g[i].u;
		y = g[i].v;
		if(Find(x) != Find(y)){
			cout<<"("<<x<<","<<y<<")= "<<g[i].w<<endl;
			Merge(x,y);
		}
	}
}
int main(){
	fin>>n>>m;
	int i;
	int x,y,z;
	for(i=0;i<m;i++){
		fin>>x>>y>>z;
		g[i].u=x;
		g[i].v=y;
		g[i].w=z;
	} 
	sort(g,g+m,comp);
	Init();
	cout<<"The order in which they are added is:\n";
	Kruskal();
	return 0;
}

test sample

 6  10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6