Declaration: images and content based on www.bilibili.com/video/BV1yp…
Minimum spanning tree principle
Prim algorithm
The principle of
The realization of Prim algorithm
The core code
void MGraph::Prim(int start){ shortEdge shortEdge; // create shortEdge array for(int I =0; i<vertexNum; i++){ shortEdge[i].lowcost=arc[start][i]; ShortEdge [I]. Adjvex =start; } shortEdge[start]. Lowcost =0; For (int I =0; i<vertexNum-1; i++){ int k=minEdge(shortEdge,vertexNum); OutputSMT (k,shortEdge[k]); shortEdge[k].lowcost=0; For (int j=0; j<vertexNum; If (arc[k][j]<shortEdge[j].lowCost){shortEdge[j]. Lowcost =arc[k][j]; shortEdge[j].adjvex=k; }}}}Copy the codeInt minEdge(shortEdge shortEdge,int vertexNum){ //e is a temporary variable to record the subscript of the current small weight and the weight e.lowcost=INFINIT; e.adjvex=-1; int i; for(i=0; i<vertexNum; I ++){// The weight is not 0 (already in the set), not infinite (no path) if(shortEdge[I].lowcost! =0&&shortEdge[i].lowcost! =INFINIT&&e.lowcost>shortEdge[i].lowcost){ e.lowcost=shortEdge[i].lowcost; e.adjvex=i; } } return e.adjvex; }Copy the codeVoid outputSMT (int k, Edge, Edge) {/ / print the path and the weights of cout < < "(" < < Edge. Adjvex < < < < < <", "k") < < "Edge. Lowcost < < endl; }Copy the codeThe complete code
#include<iostream> #define MAXVEX 100 using namespace std; const int INFINIT=65535; int visit[MAXVEX]; typedef struct Edge{ int lowcost; int adjvex; }Edge,shortEdge[MAXVEX]; class MGraph { private: int *vertex; Int **arc; Int vertexNum,arcNum; Public: MGraph(int v[],int n,int e); ~MGraph(); void display(); void Prim(int start); }; MGraph::MGraph(int v[],int n,int e) {vertexNum=n; arcNum=e; vertex = new int[vertexNum]; Arc = new int*[vertexNum]; For (int I =0; i<vertexNum; i++) arc[i]=new int[vertexNum]; for(int i=0; i<vertexNum; I ++) {// Initialize vertex information vertex[I]=v[I]; } for(int i=0; i<vertexNum; For (int j=0; j<vertexNum; j++){ if(i==j) arc[i][j]=0; else arc[i][j]=INFINIT; } int vi,vj,w; for(int i=0; i<arcNum; I++){cout<<" please enter the two vertices of the edge and the weights of this edge "<<endl; cin>>vi>>vj>>w; Arc [vi][vj]=w; // arc[vj][vi]=w; } } void MGraph::display(){ for(int i=0; i<vertexNum; i++){ for(int j=0; j<vertexNum; J++) {if (arc [I] [j] = = INFINIT) cout < < "up" < < "\ t"; else cout<<arc[i][j]<<"\t"; } cout<<endl; } cout<<endl; for(int i=0; i<vertexNum; i++){ cout<<vertex[i]<<" "; } cout<<endl; } MGraph::~MGraph(){ delete []vertex; for(int i=0; i<vertexNum; i++) delete [] arc[i]; delete [] arc; } int minEdge(shortEdge shortEdge,int vertexNum){ //e is a temporary variable to record the subscript of the current small weight and the weight e.lowcost=INFINIT; e.adjvex=-1; int i; for(i=0; i<vertexNum; I ++){// The weight is not 0 (already in the set), not infinite (no path) if(shortEdge[I].lowcost! =0&&shortEdge[i].lowcost! =INFINIT&&e.lowcost>shortEdge[i].lowcost){ e.lowcost=shortEdge[i].lowcost; e.adjvex=i; } } return e.adjvex; } void outputSMT (int k, Edge, Edge) {/ / print the path and the weights of cout < < "(" < < Edge. Adjvex < < < < < <", "k") < < "Edge. Lowcost < < endl; } void MGraph::Prim(int start){ shortEdge shortEdge; // create shortEdge array for(int I =0; i<vertexNum; i++){ shortEdge[i].lowcost=arc[start][i]; ShortEdge [I]. Adjvex =start; } shortEdge[start]. Lowcost =0; For (int I =0; i<vertexNum-1; I <vectexNum-1 int k=minEdge(shortEdge,vertexNum); OutputSMT (k,shortEdge[k]); shortEdge[k].lowcost=0; For (int j=0; j<vertexNum; If (arc[k][j]<shortEdge[j].lowCost){shortEdge[j]. Lowcost =arc[k][j]; shortEdge[j].adjvex=k; }}}} int main(){int v[6]={0,1,2,3,4,5}; Cout <<" Please input the number of vertices and edges "<<endl; int m,n; cin>>m>>n; Cout <<" Please enter the starting point of the PRIm algorithm "<<endl; int k; cin>>k; MGraph mgraph(v,m,n); Cout <<" outputs adjacency matrix information and edge array information: "<<endl; mgraph.display(); Cout <<" minimum spanning tree output starting from "<<k<<" : "<< endl; mgraph.Prim(k); return 0; }Copy the code
Input:
6 and 9
3
0 1 34 0 2 46 0 19 1 4 12 2 3 17 25 25 3 5 25 34 38 4 5 26
Output:
Output adjacency matrix information and edge array information: 0 34 46 infinity 19 34 0 infinity 12 infinity 46 infinity 0 17 infinity 25 infinity 17 0 38 25 infinity 12 infinity 38 0 26 19 infinity 25 25 infinity 25 0
0 12 3 4 5 Minimum spanning tree of output starting from 3: (3,2) 17 (3,5) 25 (5,0) 19 (5,4) 26 (4,1) 12
Kruskal algorithm
The principle of
Implementation of Kruskal algorithm
The core code
void EdgeGraph::Kruskal(){ for(int i=0; i<vertexNum; I ++){//parent array initialization parent[I]=-1; } sortEdge(); Int vex1,vex2,num=0; for(int i=0; i<edgeNum; i++){ vex1=findRoot(edge[i].from); Vex2 =findRoot(edge[I].to); If (vex1! Vex2){vex2 (edge[I]) {vex2 (edge[I]) {vex2 (edge[I]); / / print the parent [vex2] = vex1; // merge spanning tree num++; if(num==vertexNum-1) return; // loop vetexNum-1 times, return}}}Copy the codeInt EdgeGraph::findRoot(int v){// Find the root int t=v; while(parent[t]>-1){ t=parent[t]; } return t; }Copy the codeThe complete code
#include<iostream> #define dataType int using namespace std; const int MaxVertex=10; const int MaxEdge=100; struct EdgeType{ int from,to; int weight; }; class EdgeGraph{ private: dataType vertex[MaxVertex]; EdgeType edge[MaxEdge]; int vertexNum,edgeNum; int parent[MaxVertex]; public: EdgeGraph(int n,int e,dataType v[]); int findRoot(int v); void Kruskal(); void outputMST(EdgeType edge); void sortEdge(); }; EdgeGraph::EdgeGraph(int n,int e,dataType v[]){ vertexNum=n; EdgeNum =e; For (int I =0; i<vertexNum; i++){ vertex[i]=v[i]; } int start,end,w; for(int i=0; i<e; I ++){cout<<" please enter "<< I +1<<" two adjacent points and weights of the edge "<<endl; cin>>start>>end>>w; edge[i].from=start; edge[i].to=end; edge[i].weight=w; } } void EdgeGraph::Kruskal(){ for(int i=0; i<vertexNum; I ++){//parent array initialization parent[I]=-1; } sortEdge(); Int vex1,vex2,num=0; for(int i=0; i<edgeNum; i++){ vex1=findRoot(edge[i].from); Vex2 =findRoot(edge[I].to); If (vex1! Vex2){vex2 (edge[I]) {vex2 (edge[I]) {vex2 (edge[I]); / / print the parent [vex2] = vex1; // merge spanning tree num++; if(num==vertexNum-1) return; }}} void EdgeGraph::sortEdge(){bool flag=true; While (flag){// Optimized version of bubble sort flag=false; for(int i=0; i<edgeNum-1; i++){ for(int j=i+1; j<edgeNum; j++){ if(edge[i].weight>edge[j].weight){ flag=true; EdgeType t=edge[i]; edge[i]=edge[j]; edge[j]=t; }}}}} int EdgeGraph::findRoot(int v){// Find the root int t=v; while(parent[t]>-1){ t=parent[t]; } return t; } void EdgeGraph::outputMST(EdgeType edge){ cout<<"("<<edge.from<<","<<edge.to<<") "<<edge.weight<<endl; } int main(){cout<<" please input the number of nodes and edges "<<endl; int n,e; cin>>n>>e; int v[MaxEdge]; Cout <<" Please enter "<<n<<" node information "<<endl; for(int i=0; i<n; i++) cin>>v[i]; EdgeGraph edgegraph(n,e,v); edgegraph.Kruskal(); return 0; }Copy the codeInput:
6 and 9
0, 1, 2, 3, 4, 5
12 3 3 17 0 5 19 25 25 3 5 25 4 5 26 0 1 34 34 38 0 2 46
Output:
(1,4) 12
(2,3) 17
(0,5) 19
(2,5) 25
(4,5) 26
