最小生成树
假设要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然各
考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。
在每两个城市之间都可设置一条线路，相应地都要付出一定的经济代价，n个城市之间，最多可能设置n（n-1)2条线路，那么，如何在这些可能的我路中选择n-1条，以使总的耗费最少呢？
可以用连通网来表示n个城市，以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。最合理的通信网应该是代价之和最小的生成树。在一个连通网的所有生成树，各边的代价之和最小的那棵生成树称为该连通网的最小代价生成树(MinimumCostSpanningTree)，简称为最小生成树。
Prim算法
普里姆算法的实现思路
假设一个无向网G以邻接矩阵形式存储，从顶点u出发构造G的最小生成树T，要求输出T的各条边。为实现这个算法需附设一个辅助数组closedge，以记录从U到V-U具有最小权值的边。对每个顶点vi属于V-U，在辅助数组中存在一个相应分量closedge[i-1]，它包括两个域：lowcost和adjvex。其中lowcost存储最小边上的权值，adjvex存储最小边在U中的那个顶点。显然，closedge[i-1].lowcost=Min{cost(u,vi)|u属于U}，其中cost(u，v)表示赋予边(u，v)的权。
Prim算法就是一直寻找“符合要求的”顶点，每次加入的顶点都可以使那一条边的权值是当前最小的，直到所有的顶点都被加入。
算法步骤
①首先将初始顶点u加入U中，对其余的每一个顶点vi，将closedge[j]均初始化为到u的边信息。
②循环n-1次，做如下处理：
从各组边closedge中选出最小边closedge[k]，输出此边；
将k加入U中；
更新剩余的每组最小边信息closedge[j]，对于V-U中的边，新增加了一条从k到j的边，如果新边的权值比closedge[j].lowcost小，则将closedge[j].lowcost更新为新边的权值。
【算法分析】
假设网中有n个顶点，则第一个进行初始化的循环语句的频度为n，第二个循环语句的频度为n-1。其中第二个有两个内循环：其一是在closedge[v].lowcost中求最小值，其频度为n-1；其二是重新选择具有最小权值的边，其频度为n。由此，普里姆算法的时间复杂度为0(n^2)，与网中的边数无关，因此适用于求稠密网的最小生成树
#####################################################################
首先选择一个顶点加入到U中，即加入到已选顶点集中，接下来进行n-1次循环，每次的操作都是一样的。
对于未选顶点集，每个顶点都有一个closedge数组分量，表示这个数组下标所对应的顶点（未选顶点集）与已选顶点集的顶点之间组成的边，其中权值最小的边的顶点（该顶点是已选顶点集中的顶点的序号，及此时最小的权值。
每次循环，让每个closedge得到最小的记录，并把这个顶点加入已选顶点集中，然后更新每组最小边信息，更新是最重要的一步，每一组都需要更新，就是未选顶点集中的每个顶点的相应closedge分量都要更新，为下一次循环做准备。
closedge的理解：closedge是一个Closedge类型的数组，数组的下标是未选的顶点集中的顶点，不同下标的数组空间中存储的是属于该顶点的信息（对应最小边信息）
知道了算法思路，接下来就是程序的编写了。把思路变为现实的代码需要注意很多技巧和细节。
//Prim算法 //加点法，需要附设一个辅助数组//顶点可以分为两组，一组是已选的，一组是未选的。如何把已选和未选体现在程序中，就需要你自己设置一个标记。显示出二者的区别。struct Closedge{VerTexType adjvex;//最小边在已选的顶点集中的那个顶点（已选的顶点的序号） 主要是记录，便于表示我们找到的那条边int now_vex;//数组下标所对应的顶点 未选的顶点集ArcType lowcost;// 最小边上的权值（已选的顶点和未选的顶点之间的边的权值，取最小。已选对标未选） }closedge[MVNum];//对于每一个未选的顶点都有一个自己的closedge分量，每个未选的closedge记录的信息都是通过观察已选的顶点得到的//对于已选的顶点，需要标明出该顶点已选，则令其lowcost为0int Min(Closedge closedge[],int n)比较权值即lowcost，得到顶点下标，该顶点是未选集中的//仅查找{int Min,Min_vex,Min_index;for(int i=0;i<n;i++){if(closedge[i].lowcost<min){Min=closedge[i].lowcost;// Min_vex=closedge[i].now_vex;Min_index=i;} }if(closedge[i].lowcost!=0) return Min_vex;//保证是未选顶点集中的}void MiniSpanTree_Prim(AMGraph G, VerTexType u){int i, j, k，count_U=0,count_V=0;VerTexType u0, v0;k = LocateVex(G, u);for (j = 0; j < G.vexnum; j++){int temp_vex=1;if (j != k)//初始化未选的顶点的closedge，closedge属于未选的顶点{//closedge[j] = { u,G.arcs[k][j] };// temp_vex++;// closedge[j].now_vex=temp_vex;closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j];}}closedge[k].lowcost = 0;//把已选的顶点加入已选顶点集中 如何让代码体现这个加入，只需要做一个标记即可count_U++;//已选加1count_V=G.vexnum-count_U;//未选//上述操作都是初始化，为接下来的工作做准备for (i = 1; i < G.vexnum; i++)//n-1次循环//选择n-1个顶点和n-1条边，上面已经选了一个顶点{k = Min(closedge,count_V);//得到当前权值最小的边//保证一致。。。u0 = closedge[k].adjvex;//u0为最小边的一个顶点，u0属于已选顶点集v0 = G.vexs[k];//v0为最小边的另一个顶点，我们所找到的符合要求的顶点，暂时未选........//vexs...cout << u0 << v0;//输出我们找到的这条边closedge[k].lowcost = 0;//把我们找到的这个符合要求的顶点加入到已选顶点集中count_U++;//已选加1count_V=G.vexnum-count_U;//未选for(j=0;j<G.vexnum;j++)//更新！！！！{if(G.arcs[k][j]<closedge[j].lowcost){closedge[j] = { G.vexs[k],G.arcs[k][j] };}}}}
完整代码（具体的实现和存储结构，数据类型有关）
#include<iostream>#include<new>using namespace std;typedef int Status;#define OK 1#define ERROR 0#define OVERFLOW -1#define MaxInt 32767 //不相通#define MVNum 100 //最大顶点个数typedef char VerTexType;typedef int ArcType;//权值类型//邻接矩阵，二维数组typedef struct{VerTexType vexs[MVNum];//顶点 行 列 存储ArcType arcs[MVNum][MVNum];//存储int vexnum, arcnum;//图的当前点数和边数:我们申请的是固定空间，不是动态申请。固定申请的空间我们不知道将会使用多少，那么此时通过当前记录就可以知道了。}AMGraph;//邻接表typedef struct{}OtherInfo;typedef struct ArcNode//边节点{int adjvex;//可以理解为这个边结点的顶点的序号，因为邻接表中顶点都存储在顶点数组中（表头数组）struct ArcNode* nextarc;OtherInfo info;//和边相关的信息}ArcNode;typedef struct VNode//表头结点{VerTexType data;//对比 通过对比关键字可以找到“整体”ArcNode* firstarc;}VNode, AdjList[MVNum];typedef struct//邻接表{AdjList vertices;//表头结点表int vexnum, arcnum;//图的当前点数和边数???什么作用？？？}ALGraph;#pragma once
#include"AMGraph.h"int LocateVex_UDN(AMGraph G, VerTexType u)//如存在，返回顶点在图中的位置 //监视哨的方式查找{//VerTexType vexs[MVNum]， vexnumint i;for (i = 0; i < G.vexnum; i++){if (G.vexs[i] == u) return i;}return 0;}Status CreateUDN(AMGraph& G){int i, j, k;VerTexType v1, v2;ArcType w;cout << "请输入当前的顶点数和边数" << endl;cin >> G.vexnum >> G.arcnum;//初始化顶点和边（权值）//有权值 有关系 有边for (i = 0; i < G.vexnum; i++){cout << "请输入第" << i + 1 << "个顶点的数据" << endl;cin >> G.vexs[i];}for (i = 0; i < G.vexnum; i++)//矩阵:矩阵的行和列是顶点个数{for (j = 0; j < G.vexnum; j++){G.arcs[i][j] = MaxInt;}}//构造矩阵 有多少条边构造多少次（初始化的时候已经给边赋初值了，//那么接下来我们只需要把”有关系的边“赋给正确的权值（覆盖初值即可），”没有关系的边“，就是不相通，不需要赋值，初始值就表明他们不相通for (k = 0; k < G.arcnum; ++k){cout << "请输入要创建的第" << k + 1 << "条边和它的权值" << endl;cin >> v1 >> v2 >> w;//i = LocateVex_UDN(G, v1);j = LocateVex_UDN(G, v2);G.arcs[i][j] = w;//图 1 ,网 wG.arcs[j][i] = G.arcs[i][j];//无向图 对称}return OK;}void PrintAMGraph(AMGraph G)//显示一个矩阵。。。（带权）{for (int i = 0; i < G.vexnum;i++){for(int j=0;j<G.vexnum;j++){cout << G.arcnum[i][j] << " ";}cout << endl;}}//邻接表创建int LocateVex_UDG(ALGraph G, VerTexType u)//如存在，返回顶点在图中的位置 在顶点中寻找比对 返回顶点的下标（无论是邻接表还是邻接矩阵，顶点都存储在数组中。。。）{//G.vertices[i].dataint i;for (i = 0; i < G.vexnum; i++){if (G.vertices[i].data == u) return i;}return 0;}Status CreateUDG(ALGraph& G){int i, j, k;VerTexType v1, v2;ArcNode* p1;ArcNode* p2;cout << "请输入当前的顶点数和边数" << endl;cin >> G.vexnum >> G.arcnum;//初始化for (i = 0; i < G.vexnum; i++){cout << "请输入第" << i + 1 << "个顶点的数据" << endl;cin >> G.vertices[i].data;G.vertices[i].firstarc = NULL;}//构造for (k = 0; k < G.arcnum; ++k){cout << "请输入要创建的第" << k + 1 << "条边" << endl;cin >> v1 >> v2;i = LocateVex_UDG(G, v1);j = LocateVex_UDG(G, v2);//两个顶点一条边 在顶点数组里面寻找。。表头数组vertices返回下标int//jp1 = new ArcNode;//新节点p1->adjvex = j;p1->nextarc = G.vertices[i].firstarc;//头插法G.vertices[i].firstarc = p1;//i 对称p2 = new ArcNode;p2->adjvex = i;p2->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc = p2;}return OK;}void PrintALGraph(ALGraph G)//显示一个数表。。。一行是一个单链表。。。{ArcNode* p;ArcNode* q;cout << "提示：接下来的每一行，第一个为顶点信息，后面的为该顶点的邻接点的信息" << endl;for(int i=0;i<G.vertices;i++){p = new ArcNode;p = G.vertices[i].firstarc;//第一个边结点cout << G.vertices[i].data << " ";while(NULL!=p){cout << G.vertices[p->adjvex].data << "(该边）的信息为" << p->info << " ";p = p->nextarc;}cout << endl;}}// int main()//如需要。。。// {//cout << "邻接矩阵的创建" << endl;//AMGraph G;//CreateUDN(G);//cout << "邻接矩阵创建完成，显示邻接矩阵：" << endl;//PrintAMGraph(G);//cout << "邻接表的创建" << endl;//ALGraph H;//CreateUDG(H);//cout << "邻接表创建完成，显示邻接表：" << endl;//PrintALGraph(H);//return 0;// }//最小生成树算法（Prim算法 Kruskal算法)//Prim算法 //加点法，需要附设一个辅助数组struct{VerTexType adjvex;ArcType lowcost;}closedge[MVNum];int Min(Closedge closedge[],int n)比较权值即lowcost，得到顶点下标，该顶点是未选集中的//仅查找{int Min,Min_vex,Min_index;for(int i=0;i<n;i++){if(closedge[i].lowcost<min){Min=closedge[i].lowcost;// Min_vex=closedge[i].now_vex;Min_index=i;} }if(closedge[i].lowcost!=0) return Min_vex;//保证是未选顶点集中的}void MiniSpanTree_Prim(AMGraph G, VerTexType u){int i, j, k;VerTexType u0, v0;k = LocateVex(G, u);for (j = 0; j < G.vexnum; j++){if (j != k) closedge[j] = { u,G.arcs[k][j] };closedge[k].lowcost = 0;for (i = 1; i < G.vexnum; i++){k = Min(closedge);u0 = closedge[k].adjvex;v0 = G.vexs[k];cout << u0 << v0;closedge[k].lowcost = 0;for(j=0;j<G.vexnum;j++){if(G.arcs[k][j]<closedge[j].lowcost){closedge[j] = { G.vexs[k],G.arcs[k][j] };}}}}}
Kruskal算法
克鲁斯卡尔算法的构造过程
假设连通网N=(V，E)，将N中的边按权值从小到大的顺序排列。
①初始状态为只有n个顶点而无边的非连通图T=(V，{})，图中每个顶点自成一个连通分量。
②在E中选择权值最小的边，若该边依附的顶点落在T中不同的连通分量上(不形成回路)，则将此边加入T中，否则舍去此边而选择下一条权值最小的边。
③重复②，直至T中所有顶点都在同一连通分量上为止。
【算法步骤】
①将数组Edge中的元素按权值从小到大排序。
②依次查看数组Edge中的边，循环执行以下操作：
依次从排好序的数组Edge中选出一条边(U1,U2)；
在Vexset中分别查找v1和v2所在的连通分量vs1和vs2进行判断：如果vs1和vs2不等，表明所选的两个顶点分属不同的连通分量，输出此边，并合并vs1，和vs2两个连通分量；
如果vs1和vs2相等，表明所选的两个顶点属于同一个连通分量，舍去此边而选择下一条权值最小的边。
个人思考
①慢慢把边都加入，随着程序的进行，边越加越多，被合并的越多，即被连通的顶点不止一个，而是集合。
②Vexset[i]：标识各个顶点所在的连通分量。初始时Vexset[i]=i，表示各个顶点自成一个连通分量。
这个数组非常重要，是程序的关键。数组下标代表不同顶点，不同下标的数组空间存储的值代表该顶点所在的连通分量。连通分量相同表明这些顶点相连通不相同则不连通。(此处、你要理解数组的含义，使用方法以及连通分量的概念)
//Kruskal算法//加边法int arcnum=100;struct KNode{VerTexType Head;//边的始点VerTexType Tail;//边的终点ArcType lowcost;}Edge[arcnum];int Vexset[MVNum];//标识各个顶点所属的连通分量 即表明谁与谁联通，谁与谁不连通void Sort(struct KNode a[], int n)//从小到大排序，这里采用了改进版的冒泡排序{int i, j，flag=1,m=n-1;//flag用来标记某一趟排序是否发生交换struct KNode temp;while((m>0)&&(flag==1)){flag=0;for (j = 1; j <=m; j++){if (a[j]>a[j + 1]){flag=1;temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}--m;}}}void MiniSpanTree_Kruskal(AMGraph G){int i,j,v1,v2,vs1,vs2;Sort(Edge,arcnum);//按权值从小到大排序for(i=0;i<G.vexnum;i++)//表示各个顶点自成一个连通分量{Vexset[i]=i;}for(i=0;i<G.arcnum;i++)//依次查看数组Edge中的边{//边v1=LocateVex(G,Edge[i].Head);//v1为边的始点Head的下标v2=LocateVex(G,Edge[i].Tail);//v1为边的终点Tail的下标//所在连通分量vs1=Vexset[v1];//获取边Edge[i]的始点所在的连通分量vs1vs2=Vexset[v2];//获取边Edge[i]的终点所在的连通分量vs2if(vs1!=vs2)//所加入的边起作用 边的两个顶点分属于不同的连通分量{cout<<Edge[i].Head<<Edge[i].Tail;//输出此边for(j=0;j<G.vexnum;j++)//合并vs1和vs2两个连通分量，即两个集合统一编号{if(Vexset[j]==vs2) Vexset[j]=vs1;//集合编号为vs2的都改为vs1}}}}
完整代码
#include<iostream>#include<new>using namespace std;typedef int Status;#define OK 1#define ERROR 0#define OVERFLOW -1#define MAXSIZE 100#define MaxInt 32767 //不相通#define MVNum 100 //最大顶点个数typedef char VerTexType;typedef int ArcType;//权值类型bool visited[MVNum];typedef int QElemType;typedef struct{QElemType data[MAXSIZE];int front; /*头指针*/int rear; /*尾指针，若队列不空，指向队列元素的下一个位置*/}SqQueue;SqQueue* Q;//链表 栈 队列 都是指针类型的？门牌号？不是房间吗？//邻接矩阵，二维数组typedef struct{VerTexType vexs[MVNum];//顶点 行 列 存储ArcType arcs[MVNum][MVNum];//存储int vexnum, arcnum;//图的当前点数和边数}AMGraph;//邻接表typedef struct{}OtherInfo;typedef struct ArcNode//边节点{int adjvex;struct ArcNode* nextarc;OtherInfo info;//和边相关的信息}ArcNode;typedef struct VNode//表头结点{VerTexType data;ArcNode* firstarc;}VNode, AdjList[MVNum];typedef struct//邻接表{AdjList vertices;//表头结点表int vexnum, arcnum;//图的当前点数和边数}ALGraph;int LocateVex_UDN(AMGraph G, VerTexType u)//如存在，返回顶点在图中的位置 //监视哨的方式查找{//VerTexType vexs[MVNum]， vexnumint i;for (i = 0; i < G.vexnum; i++){if (G.vexs[i] == u) return i;}return 0;}Status CreateUDN(AMGraph& G){int i, j, k;VerTexType v1, v2;ArcType w;cout << "请输入当前的顶点数和边数" << endl;cin >> G.vexnum >> G.arcnum;//初始化顶点和边（权值）//有权值 有关系 有边for (i = 0; i < G.vexnum; i++){cout << "请输入第" << i + 1 << "个顶点的数据" << endl;cin >> G.vexs[i];}for (i = 0; i < G.vexnum; i++)//矩阵:矩阵的行和列是顶点个数{for (j = 0; j < G.vexnum; j++){G.arcs[i][j] = MaxInt;}}//构造矩阵 有多少条边构造多少次（初始化的时候已经给边赋初值了，//那么接下来我们只需要把”有关系的边“赋给正确的权值（覆盖初值即可），”没有关系的边“，就是不相通，不需要赋值，初始值就表明他们不相通for (k = 0; k < G.arcnum; ++k){cout << "请输入要创建的第" << k + 1 << "条边和它的权值" << endl;cin >> v1 >> v2 >> w;//i = LocateVex_UDN(G, v1);j = LocateVex_UDN(G, v2);G.arcs[i][j] = w;//图 1 ,网 wG.arcs[j][i] = G.arcs[i][j];//无向图 对称}return OK;}void PrintAMGraph(AMGraph G)//显示一个矩阵。。。（带权）{for (int i = 0; i < G.vexnum;i++){for(int j=0;j<G.vexnum;j++){cout << G.arcnum[i][j] << " ";}cout << endl;}}//邻接表创建int LocateVex_UDG(ALGraph G, VerTexType u)//如存在，返回顶点在图中的位置 在顶点中寻找比对 返回顶点的下标（无论是邻接表还是邻接矩阵，顶点都存储在数组中。。。）{//G.vertices[i].dataint i;for (i = 0; i < G.vexnum; i++){if (G.vertices[i].data == u) return i;}return 0;}Status CreateUDG(ALGraph& G){int i, j, k;VerTexType v1, v2;ArcNode* p1;ArcNode* p2;cout << "请输入当前的顶点数和边数" << endl;cin >> G.vexnum >> G.arcnum;//初始化for (i = 0; i < G.vexnum; i++){cout << "请输入第" << i + 1 << "个顶点的数据" << endl;cin >> G.vertices[i].data;G.vertices[i].firstarc = NULL;}//构造for (k = 0; k < G.arcnum; ++k){cout << "请输入要创建的第" << k + 1 << "条边" << endl;cin >> v1 >> v2;i = LocateVex_UDG(G, v1);j = LocateVex_UDG(G, v2);//两个顶点一条边 在顶点数组里面寻找。。表头数组vertices返回下标int//jp1 = new ArcNode;//新节点p1->adjvex = j;p1->nextarc = G.vertices[i].firstarc;//头插法G.vertices[i].firstarc = p1;//i 对称p2 = new ArcNode;p2->adjvex = i;p2->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc = p2;}return OK;}void PrintALGraph(ALGraph G)//显示一个数表。。。一行是一个单链表。。。{ArcNode* p;ArcNode* q;cout << "提示：接下来的每一行，第一个为顶点信息，后面的为该顶点的邻接点的信息" << endl;for(int i=0;i<G.vertices;i++){p = new ArcNode;p = G.vertices[i].firstarc;//第一个边结点cout << G.vertices[i].data << " ";while(NULL!=p){cout << G.vertices[p->adjvex].data << "(该边）的信息为" << p->info << " ";p = p->nextarc;}cout << endl;}}// int main()//如需要。。。// {//cout << "邻接矩阵的创建" << endl;//AMGraph G;//CreateUDN(G);//cout << "邻接矩阵创建完成，显示邻接矩阵：" << endl;//PrintAMGraph(G);//cout << "邻接表的创建" << endl;//ALGraph H;//CreateUDG(H);//cout << "邻接表创建完成，显示邻接表：" << endl;//PrintALGraph(H);//return 0;// }//最小生成树算法（Prim算法 Kruskal算法)//Kruskal算法int arcnum=100;struct KNode{VerTexType Head;//边的始点VerTexType Tail;//边的终点ArcType lowcost;}Edge[arcnum];int Vexset[MVNum];void Sort(struct KNode a[], int n){int i, j;struct KNode temp;for (i = 0; i < n - 1; i++){for (j = 0; j < n - i - 1; j++){if (a[j]>a[j + 1]){temp = a[j];a[j] = a[j + 1];a[j + 1] = temp;}}}}void MiniSpanTree_Kruskal(AMGraph G){int i,j,v1,v2,vs1,vs2;Sort(Edge,arcnum);for(i=0;i<G.vexnum;i++){Vexset[i]=i;}for(i=0;i<G.arcnum;i++){v1=LocateVex(G,Edge[i].Head);v2=LocateVex(G,Edge[i].Tail);vs1=Vexset[v1];vs2=Vexset[v2];if(vs1!=vs2){cout<<Edge[i].Head<<Edge[i].Tail;for(j=0;j<G.vexnum;j++){if(Vexset[j]==vs2) Vexset[j]=vs1;}}}}
编者语
小新还在努力，如有不足请指出。
