1 、Prim算法思想

思想：首先找到权值最小的一条边，由这两个顶点出发，分别去找权值最小的(不能有环的出现)；由各个顶点，每次都找权值最小的。

连贯的做法：从顶点的连续角度出发，每次从相应顶点出发，到权值最小的边进行连接。

模型如下：

2、Prim算法实现

lowCost[i]：表示以i为终点的边的最小权值，当lowCost[i] = 0；说明以i为终点的边的最小权值=0；也就是表示i点加入了mst数组；

mst[i]：表示对应lowCost[i]的起点，即说明边<mst[i], i>是mst的一条边；

每次进行一次比较，都要随之更改其lowCost和mst数组；

每并入一个顶点，都更改为0，并且修改相应的记录；都会从内部挑选最小的权值，直到最后所有的lowCost[i] = 0;

均由C++实现(邻接矩阵实现)：

template<typenameType,typenameE>voidGraphMtx<Type,E>::MinSpanTree_Prim(constType&v){intn=Graph<Type,E>::getCurVertex();int*lowCost=newint[n];//这两个数组是至关重要的int*mst=newint[n];intk=getVertexIndex(v);for(inti=0;i<n;i++){if(i!=k){lowCost[i]=edge[k][i];//i:表示最终顶点，lowCost[i]:表示起始到最终顶点的权值；mst[i]=k;//起始顶点}else{lowCost[i]=0;}}intmin;intminIndex;intbegin;intend;for(i=0;i<n-1;i++){min=MAX_COST;minIndex=-1;for(intj=0;j<n;j++){if(lowCost[j]!=0&&lowCost[j]<min){min=lowCost[j];//最小权值minIndex=j;//终点}}begin=mst[minIndex];//起点end=minIndex;//终点printf("%c-->%c:%d\n",getValue(begin),getValue(end),min);lowCost[minIndex]=0;//赋为0并入mst集合intcost;for(j=0;j<n;j++){//每次都重新更改lowCost和mst数组；cost=edge[minIndex][j];if(cost<lowCost[j]){lowCost[j]=cost;mst[j]=minIndex;}}}}

3、完整代码、测试代码、测试结果

(1)、完整代码

#ifndef_GRAPH_H_#define_GRAPH_H_#include<iostream>#include<queue>usingnamespacestd;#defineVERTEX_DEFAULT_SIZE10#defineMAX_COST0x7FFFFFFFtemplate<typenameType,typenameE>classGraph{public:boolisEmpty()const{returncurVertices==0;}boolisFull()const{if(curVertices>=maxVertices||curEdges>=curVertices*(curVertices-1)/2)returntrue;//图满有2种情况：(1)、当前顶点数超过了最大顶点数，存放顶点的空间已满returnfalse;//(2)、当前顶点数并没有满，但是当前顶点所能达到的边数已满}intgetCurVertex()const{returncurVertices;}intgetCurEdge()const{returncurEdges;}public:virtualboolinsertVertex(constType&v)=0;//插入顶点virtualboolinsertEdge(constType&v1,constType&v2,Ecost)=0;//插入边virtualboolremoveVertex(constType&v)=0;//删除顶点virtualboolremoveEdge(constType&v1,constType&v2)=0;//删除边virtualintgetFirstNeighbor(constType&v)=0;//得到第一个相邻顶点virtualintgetNextNeighbor(constType&v,constType&w)=0;//得到下一个相邻顶点public:virtualintgetVertexIndex(constType&v)const=0;//得到顶点下标virtualvoidshowGraph()const=0;//显示图virtualTypegetValue(intindex)const=0;public:virtualvoidDFS(constType&v)=0;virtualvoidBFS(constType&v)=0;protected:intmaxVertices;//最大顶点数intcurVertices;//当前顶点数intcurEdges;//当前边数};template<typenameType,typenameE>classGraphMtx:publicGraph<Type,E>{//邻接矩阵继承父类矩阵#definemaxVerticesGraph<Type,E>::maxVertices//因为是模板，所以用父类的数据或方法都得加上作用域限定符#definecurVerticesGraph<Type,E>::curVertices#definecurEdgesGraph<Type,E>::curEdgespublic:GraphMtx(intvertexSize=VERTEX_DEFAULT_SIZE){//初始化邻接矩阵maxVertices=vertexSize>VERTEX_DEFAULT_SIZE?vertexSize:VERTEX_DEFAULT_SIZE;vertexList=newType[maxVertices];//申请顶点空间for(inti=0;i<maxVertices;i++){//都初始化为0vertexList[i]=0;}edge=newint*[maxVertices];//申请边的行for(i=0;i<maxVertices;i++){//申请列空间edge[i]=newint[maxVertices];}for(i=0;i<maxVertices;i++){//赋初值为0for(intj=0;j<maxVertices;j++){if(i!=j){edge[i][j]=MAX_COST;//初始化时都赋为到其它边要花的代价为无穷大。}else{edge[i][j]=0;//初始化时自己到自己认为花费为0}}}curVertices=curEdges=0;//当前顶点和当前边数}GraphMtx(Type(*mt)[4],intsz){//通过已有矩阵的初始化inte=0;//统计边数maxVertices=sz>VERTEX_DEFAULT_SIZE?sz:VERTEX_DEFAULT_SIZE;vertexList=newType[maxVertices];//申请顶点空间for(inti=0;i<maxVertices;i++){//都初始化为0vertexList[i]=0;}edge=newint*[maxVertices];//申请边的行for(i=0;i<maxVertices;i++){//申请列空间edge[i]=newType[maxVertices];}for(i=0;i<maxVertices;i++){//赋初值为矩阵当中的值for(intj=0;j<maxVertices;j++){edge[i][j]=mt[i][j];if(edge[i][j]!=0){e++;//统计列的边数}}}curVertices=sz;curEdges=e/2;}~GraphMtx(){}public:boolinsertVertex(constType&v){if(curVertices>=maxVertices){returnfalse;}vertexList[curVertices++]=v;returntrue;}boolinsertEdge(constType&v1,constType&v2,Ecost){intmaxEdges=curVertices*(curVertices-1)/2;if(curEdges>=maxEdges){returnfalse;}intv=getVertexIndex(v1);intw=getVertexIndex(v2);if(v==-1||w==-1){cout<<"edgenoexit"<<endl;//要插入的顶点不存在，无法插入returnfalse;}if(edge[v][w]!=MAX_COST){//当前边已经存在，不能进行插入returnfalse;}edge[v][w]=edge[w][v]=cost;//因为是无向图，对称,权值赋为cost；returntrue;}//删除顶点的高效方法boolremoveVertex(constType&v){inti=getVertexIndex(v);if(i==-1){returnfalse;}vertexList[i]=vertexList[curVertices-1];intedgeCount=0;for(intk=0;k<curVertices;k++){if(edge[i][k]!=0){//统计删除那行的边数edgeCount++;}}//删除行for(intj=0;j<curVertices;j++){edge[i][j]=edge[curVertices-1][j];}//删除列for(j=0;j<curVertices;j++){edge[j][i]=edge[j][curVertices-1];}curVertices--;curEdges-=edgeCount;returntrue;}/*//删除顶点用的是数组一个一个移动的方法，效率太低。boolremoveVertex(constType&v){inti=getVertexIndex(v);if(i==-1){returnfalse;}for(intk=i;k<curVertices-1;++k){vertexList[k]=vertexList[k+1];}intedgeCount=0;for(intj=0;j<curVertices;++j){if(edge[i][j]!=0)edgeCount++;}for(intk=i;k<curVertices-1;++k){for(intj=0;j<curVertices;++j){edge[k][j]=edge[k+1][j];}}for(intk=i;k<curVertices-1;++k){for(intj=0;j<curVertices;++j){edge[j][k]=edge[j][k+1];}}curVertices--;curEdges-=edgeCount;returntrue;}*/boolremoveEdge(constType&v1,constType&v2){intv=getVertexIndex(v1);intw=getVertexIndex(v2);if(v==-1||w==-1){//判断要删除的边是否在当前顶点内returnfalse;//顶点不存在}if(edge[v][w]==0){//这个边根本不存在，没有必要删returnfalse;}edge[v][w]=edge[w][v]=0;//删除这个边赋值为0，代表不存在；curEdges--;returntrue;}intgetFirstNeighbor(constType&v){inti=getVertexIndex(v);if(i==-1){return-1;}for(intcol=0;col<curVertices;col++){if(edge[i][col]!=0){returncol;}}return-1;}intgetNextNeighbor(constType&v,constType&w){inti=getVertexIndex(v);intj=getVertexIndex(w);if(i==-1||j==-1){return-1;}for(intcol=j+1;col<curVertices;col++){if(edge[i][col]!=0){returncol;}}return-1;}public:voidshowGraph()const{if(curVertices==0){cout<<"NulGraph"<<endl;return;}for(inti=0;i<curVertices;i++){cout<<vertexList[i]<<"";}cout<<endl;for(i=0;i<curVertices;i++){for(intj=0;j<curVertices;j++){if(edge[i][j]!=MAX_COST){cout<<edge[i][j]<<"";}else{cout<<"@";}}cout<<vertexList[i]<<endl;}}intgetVertexIndex(constType&v)const{for(inti=0;i<curVertices;i++){if(vertexList[i]==v){returni;}}return-1;}public:TypegetValue(intindex)const{returnvertexList[index];}voidDFS(constType&v){intn=Graph<Type,E>::getCurVertex();bool*visit=newbool[n];for(inti=0;i<n;i++){visit[i]=false;}DFS(v,visit);delete[]visit;}voidBFS(constType&v){intn=Graph<Type,E>::getCurVertex();bool*visit=newbool[n];for(inti=0;i<n;i++){visit[i]=false;}cout<<v<<"-->";intindex=getVertexIndex(v);visit[index]=true;queue<int>q;//队列中存放的是顶点下标;q.push(index);intw;while(!q.empty()){index=q.front();q.pop();w=getFirstNeighbor(getValue(index));while(w!=-1){if(!visit[w]){cout<<getValue(w)<<"-->";visit[w]=true;q.push(w);}w=getNextNeighbor(getValue(index),getValue(w));}}delete[]visit;}public:voidMinSpanTree_Kruskal();voidMinSpanTree_Prim(constType&v);protected:voidDFS(constType&v,bool*visit){cout<<v<<"-->";intindex=getVertexIndex(v);visit[index]=true;intw=getFirstNeighbor(v);while(w!=-1){if(!visit[w]){DFS(getValue(w),visit);}w=getNextNeighbor(v,getValue(w));}}private:Type*vertexList;//存放顶点的数组int**edge;//存放边关系的矩阵};//////////////////////////////////////////////////////////////////////////////////////////////////////typedefstructMstEdge{intx;//rowinty;//colintcost;}MstEdge;intcmp(constvoid*a,constvoid*b){return(*(MstEdge*)a).cost-(*(MstEdge*)b).cost;}boolisSame(int*father,inti,intj){while(father[i]!=i){i=father[i];}while(father[j]!=j){j=father[j];}returni==j;}voidmarkSame(int*father,inti,intj){while(father[i]!=i){i=father[i];}while(father[j]!=j){j=father[j];}father[j]=i;}template<typenameType,typenameE>voidGraphMtx<Type,E>::MinSpanTree_Kruskal(){intn=Graph<Type,E>::getCurVertex();//由于要用到父类的保护数据或方法，有模板的存在，必须加上作用域限定符;MstEdge*edge1=newMstEdge[n*(n-1)/2];intk=0;for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){if(edge[i][j]!=MAX_COST){edge1[k].x=i;edge1[k].y=j;edge1[k].cost=edge[i][j];k++;}}}qsort(edge1,k,sizeof(MstEdge),cmp);int*father=newint[n];Typev1,v2;for(i=0;i<n;i++){father[i]=i;}for(i=0;i<n;i++){if(!isSame(father,edge1[i].x,edge1[i].y)){v1=getValue(edge1[i].x);v2=getValue(edge1[i].y);printf("%c-->%c:%d\n",v1,v2,edge1[i].cost);markSame(father,edge1[i].x,edge1[i].y);}}}template<typenameType,typenameE>voidGraphMtx<Type,E>::MinSpanTree_Prim(constType&v){intn=Graph<Type,E>::getCurVertex();int*lowCost=newint[n];int*mst=newint[n];intk=getVertexIndex(v);for(inti=0;i<n;i++){if(i!=k){lowCost[i]=edge[k][i];mst[i]=k;}else{lowCost[i]=0;}}intmin;intminIndex;intbegin;intend;for(i=0;i<n-1;i++){min=MAX_COST;minIndex=-1;for(intj=0;j<n;j++){if(lowCost[j]!=0&&lowCost[j]<min){min=lowCost[j];minIndex=j;}}begin=mst[minIndex];end=minIndex;printf("%c-->%c:%d\n",getValue(begin),getValue(end),min);lowCost[minIndex]=0;intcost;for(j=0;j<n;j++){cost=edge[minIndex][j];if(cost<lowCost[j]){lowCost[j]=cost;mst[j]=minIndex;}}}}#endif

(2)、测试代码

#include"Graph2.h"intmain(void){GraphMtx<char,int>gm;gm.insertVertex('A');//0gm.insertVertex('B');//1gm.insertVertex('C');//2gm.insertVertex('D');//3gm.insertVertex('E');//4gm.insertVertex('F');//5gm.insertEdge('A','B',6);gm.insertEdge('A','C',1);gm.insertEdge('A','D',5);gm.insertEdge('B','C',5);gm.insertEdge('B','E',3);gm.insertEdge('C','E',6);gm.insertEdge('C','D',5);gm.insertEdge('C','F',4);gm.insertEdge('D','F',2);gm.insertEdge('E','F',6);gm.showGraph();gm.MinSpanTree_Kruskal();cout<<"---------------------------------------------------------"<<endl;gm.MinSpanTree_Prim('A');return0;}

(3)、测试结果

测试图模型：