最小生成树问题毕业论文

欧几里德算算法gcd(a,b)=ax+by：int ext_gcd(int a,int b,int& x,int& y){ int t,ret; if (!b){ x=1,y=0; return a; } ret=ext_gcd(b,a%b,x,y); t=x,x=y,y=t-a/b*y; return ret;}最小生成树（Prim算法）：//无向图最小生成树,prim算法,邻接阵形式,复杂度O(n^2)//返回最小生成树的长度,传入图的大小n和邻接阵mat,不相邻点边权inf//可更改边权的类型,pre[]返回树的构造,用父结点表示,根节点(第一个)pre值为-1//必须保证图的连通的!#define MAXN 200#define inf 1000000000typedef double elem_t;elem_t prim(int n,elem_t mat[][MAXN],int* pre){ elem_t min[MAXN],ret=0; int v[MAXN],i,j,k; for (i=0;i

后目的、意义、价值、实施环境及时间

当连通图中各边权值不相等时，最小生成树唯一；当有相等的权值时最小生成树可能唯一可能不唯一，具体情况具体分析。

去看Winter Camp 2006 王栋的论文可以做到n log n

#include<>#include<>#define INFINITY 100000//相当于无穷大#define MAX_VERTEX_NUM 20//最多能有多少个点//邻接矩阵图typedef struct{char vexs[MAX_VERTEX_NUM];int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int vexnum,arcnum;}MGraph;//保存路径起始点，终点，以及权值typedef struct{int adjvex;int endvex;int lowcost;}closedge[MAX_VERTEX_NUM];//创建邻接矩阵void CreateUDN(MGraph &G);//找到输入字符对应的数字int LocateVex(MGraph G,char v);//输出邻接矩阵图void PrintUDN(MGraph G);//找出最小生成树void MiniSpanTree_PRIM(MGraph G,closedge &minedge);//输出最小生成树的每条边的起点，终点和权值void PrintMinEdge(MGraph G,closedge minedge);int main(){MGraph G;closedge minedge;CreateUDN(G);printf("该图的邻接矩阵存储示意图如下：\n");PrintUDN(G);printf("\n");MiniSpanTree_PRIM(G,minedge);printf("该图生成树的边如下：\n");PrintMinEdge(G,minedge);printf("\n");return 0;}//创建邻接矩阵void CreateUDN(MGraph &G){int i,j;char vex1,vex2;//起点，终点字符int vex1Index,vex2Index;//字符对应的数字int weight;char ch;printf("请输入有多少个顶点，多少条边：\n");scanf("%d%d",&);printf("请输入顶点向量：\n");scanf("%s",);//初始化都为0for(i=0;i<;i++)for(j=0;j<;j++)[i][j]=0;//输入并赋值有路径的printf("请输入所有边的起点，终点和权值：\n");for(i=0;i<;i++){while((ch=getchar())!='\n'); //吸收换行符scanf("%c%c",&vex1,&vex2);scanf("%d",&weight);vex1Index=LocateVex(G,vex1);vex2Index=LocateVex(G,vex2);[vex1Index][vex2Index]=[vex2Index][vex1Index]=weight;}//剩下没路径的（当然不包括自己到自己）赋值无穷大for(i=0;i<;i++){for(j=0;j<;j++)if([i][j]==0&&i!=j){[i][j]=INFINITY;}}}//将输入的字符转换成对应的数字（A-0，B-1，...）int LocateVex(MGraph G,char v){int i;for(i=0;i<;i++)if(v==[i])return i;}//输出对应矩阵void PrintUDN(MGraph G){int i,j;for(i=0;i<=;i++){for(j=0;j<=;j++){if(i==0&&j==0)printf("\t");else if(i==0){printf("%c\t",[j-1]);}else if(j==0){printf("%c\t",[i-1]);}else{if([i-1][j-1]==INFINITY)printf("∞\t");elseprintf("%d\t",[i-1][j-1]);}}printf("\n");}}//生成最小生成树（实则就是记录最小路径的起点，终点，权值）void MiniSpanTree_PRIM(MGraph G,closedge &minedge){int i,j,k,z;int temp;int currentmin;//起始初始化k=0;for(j=1;j<;++j){minedge[j-1].adjvex=k;minedge[j-1].endvex=j;minedge[j-1].lowcost=[k][j];}//找最小路径for(i=0;i<;++i){//找第一个路径最短的可达点currentmin=minedge[i].lowcost;k=i;for(j=i+1;j<;j++){if(minedge[j].lowcost