最小生成树应用场景：
假设以下场景，有一块木板，板上钉上一些钉子，这些钉子可以由一些细绳连接起来。假设每个钉子可以通过一根或者多根细绳连接起来，那么一定存在这样得情况，即用最少的细绳把所有的钉子连接起来。
更为实际的场景，在某地分布着N个村庄，现在需要在N个村庄之间修路，每个村庄之间的距离不同，问怎么修最短的路把村庄连接起来。
选定一个开始的结点，在一个点集合中，其余点在另一个点集合中，然后找取与这个结点相连的权值最小最小的边，加入第一个点集合，之后再次找寻与这两个节点相邻的权值最小的边加入，循环往复，直到所有的点都存在于第一个点集合中。
注意在选择权值最小的边时，不能够形成回路！！！！
不然就不叫树了啊！！！！
//建立图的邻接矩阵储存结构#include <stdio.h>#include <string.h>#include <stdlib.h>#define M 20#define FINITY 5000 typedef struct {char vexs[M];int edges[M][M];int n,e; }Mgraph;typedef struct edgedata{int begin,end;int length;}edge;//c=0，表示建立无向图void creat(Mgraph *g,int c){FILE *f;f=fopen("test.txt","r");int i,j,k,w;if(f){fscanf(f,"%d%d",&g->n,&g->e);for(i=0;i<g->n;i++){fscanf(f,"%1s",&g->vexs[i]);}for(i=0;i<g->n;i++){for(j=0;j<g->n;j++){if(i==j)g->edges[i][j]=0;else g->edges[i][j]=FINITY;}}for(k=0;k<g->e;k++){fscanf(f,"%d%d%d",&i,&j,&w);g->edges[i][j]=w;if(c==0){g->edges[j][i]=w;}}fclose(f);}else{g->n=0;}}void getedge(Mgraph g,edge edges[]){int i,j,k=0;for(i=0;i<g.n;i++){for(j=0;j<i;j++){if(g.edges[i][j]!=0 && g.edges[i][j]<FINITY){edges[k].begin=i;edges[k].end=j;edges[k++].length=g.edges[i][j];}}}}void quicksort(edge edges[],int left ,int right){edge x;int i,j,flag=1;if(left<right){i=left;j=right;x=edges[i];while(i!=j){while(i<j && x.length<edges[j].length)j--;//找比x.length小的边if(i<j){edges[i]=edges[j];i++;}while(i<j && x.length>edges[i].length) i++;if(i<j){edges[j]=edges[i];j--;}}edges[i]=x;quicksort(edges,left,i-1);quicksort(edges,i+1,right);}}void kruskal(Mgraph g){printf("kruskal算法：\n");int i,j,k=0,ltfl;int cnvx[M];edge edges[M*M];edge tree[M];getedge(g,edges);quicksort(edges,0,g.e-1);for(i=0;i<g.n-1;i++)cnvx[i]=i;for(i=0;i<g.n-1;i++){while(cnvx[edges[k].begin]==cnvx[edges[k].end])k++;tree[i]=edges[k];ltfl=cnvx[edges[k].end];for(j=0;j<g.n;j++){if(cnvx[j]==ltfl){cnvx[j]=cnvx[edges[k].begin];}}k++;}int w=0;printf("最小生成树是：\n");for(j=0;j<g.n-1;j++){printf("%c-%c %d\n",g.vexs[tree[j].begin],g.vexs[tree[j].end],tree[j].length);w+=tree[j].length;}printf("最小的权值为：%d\n\n",w);}void prim(Mgraph g,edge tree[]){printf("prim算法：\n");edge x;int w;int d,min,j,k,s,v;for(v=1;v<=g.n-1;v++){tree[v-1].begin=0;tree[v-1].end=v;tree[v-1].length=g.edges[0][v];}for(k=0;k<=g.n-3;k++){min=tree[k].length;s=k;for(j=k+1;j<=g.n-2;j++){if(tree[j].length<min){min=tree[j].length;s=j;}}v=tree[s].end;if(s!=k){x=tree[s];tree[s]=tree[k];tree[k]=x;}for(j=k+1;j<=g.n-2;j++){d=g.edges[v][tree[j].end];if(d<tree[j].length){tree[j].length=d;tree[j].begin=v;}}}w=0;for(j=0;j<=g.n-2;j++){printf("%c-%c %d\n",g.vexs[tree[j].begin],g.vexs[tree[j].end],tree[j].length);w+=tree[j].length;}printf("最小权值是：%d\n",w);}void print(Mgraph *g){int i,j;printf("一共有%d个边,%d个点。\n",g->e,g->n);printf("各个元素信息：\n");for(i=0;i<g->n;i++){printf("%c ",g->vexs[i]);} printf("\n");printf("对应的邻接矩阵：\n");for(i=0;i<g->n;i++){for(j=0;j<g->n;j++){printf("%-5d",g->edges[i][j]);}printf("\n");}}int main (){edge tree[M];Mgraph g;creat(&g,0);printf("\n");printf("输出：\n"); print(&g);kruskal(g);prim(g,tree);return 0;}
Kruskal算法
这串代码和上面的功能一样，只不过可以更清楚地看到变化的过程
void kruskal(Mgraph g){int i,j,k=0,ltfl;int cnvx[M];edge edges[M*M];//存放图的所有边edge tree[M];//存放最小生成树的信息getedge(g,edges);//获取各个边的信息printf("Before quicksort:\n");for(i=0;i<g.e;i++){printf("%d %d %d\n",edges[i].beg,edges[i].en,edges[i].length);}printf("\n");quick_sort(edges,0,g.e-1);//按照权值从小到大排序printf("After quicksort:\n");for(i=0;i<g.e;i++){printf("%d %d %d\n",edges[i].beg,edges[i].en,edges[i].length);}printf("\n");for(i=0;i<g.n;i++)cnvx[i]=i;//设置每个点的连通分量为其顶点序号for(i=0;i<g.n-1;i++)//最小生成树，必须使用且仅使用n-1条边来连接网络中的n个顶点{//edges[k].beg 和 edges[k].en已经在一个连通分量中，再添加这两个顶点的边的话，会构成回路while(cnvx[edges[k].beg]==cnvx[edges[k].en])k++;tree[i]=edges[k];ltfl=cnvx[edges[k].en];//记录选中边的终点的连通分量编号for(j=0;j<g.n;j++)//把两个连通分量变成一个连通分量if(cnvx[j]==ltfl)cnvx[j]=cnvx[edges[k].beg];printf("************\n");printf("i=%d k=%d ltfl=%d \n",i,k,ltfl);for(int p=0;p<g.n;p++)printf("cnvx[%d]=%d\n",p,cnvx[p]);k++;}for(j=0;j<g.n-1;j++){printf("%c %c %d\n",g.vex[tree[j].beg],g.vex[tree[j].en],tree[j].length);}}
