1、最小生成树(MST树)
针对连通图；
(1)、现实意义：在n个城市之间建立通信网络，连通n个城市，只需要n-1条线路；

但是n个城市之间共有 n*(n-1)/2条路线，如何选择n-1条，使我们花费成本最小。

(2)、相同的一个图形结构，有可能产生出不同形状的生成树，但是我们要找的是不同形状生成树里面耗费最小的一棵树；

(3)、研究的问题：怎样从生成树里面找到花费代价最小的一颗，花费最小，成本最低；耗费代价最小的生成树我们就称之为：最小生成树(MST树)。

(4)、最小生成树是不能有环形的；通过不同的方法，最终所找到的最小生成树是相同的(在权值相同时，有可能不一样，但是权值最小是唯一的，肯定的)。

2、Kruskal算法思想

思想：每次找权值最小的边，与顶点关系不大(不关注顶点)；

从边的游离角度出发，每次都要找权值路径最小的边，(特别注意看所选的边是否购成回路)

模型分析：

3、Kruskal算法实现

这里找最小代价cost时，采用的是数组(调用系统快排)，当然用堆也可以。

均由C++代码实现(用的是邻接矩阵)：

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);//找到了最小边和costmarkSame(father,edge1[i].x,edge1[i].y);//标记为相同父节点;}}}

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

(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();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);}}}#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();return0;}

(3)、测试结果

测试图模型