最小生成树(C语言实现)
http://dl.iteye.com/upload/attachment/496388/5300ec02-00e2-3c43-9f8c-96eb05cc1f2b.jpg求这个网的最小生成树
/* * 普里姆算法和克鲁斯卡尔算法求最小生成树 * 采用邻接矩阵存储 * */#include<stdio.h>#define MAX_VERTEX_NUM 20//图的定义typedef struct {int vertexNum;int edgeNum;char vertex;int arc;}Graph,*PGraph;//辅助数组元素typedef struct {int from;int to;int weight;int flag;}ArrayNode; //构造无向网void createdGraph(PGraph g){int i,j; g->vertexNum=6;g->edgeNum=10; for(i=0;i<g->vertexNum;i++)g->vertex='A'+i;for(i=0;i<g->vertexNum;i++)for(j=0;j<g->vertexNum;j++) g->arc=0;g->arc=6;g->arc=1;g->arc=5;g->arc=6;g->arc=5;g->arc=3;g->arc=1;g->arc=5;g->arc=5;g->arc=6;g->arc=4;g->arc=5;g->arc=5;g->arc=2;g->arc=3;g->arc=6;g->arc=6;g->arc=4;g->arc=2;g->arc=6;}//初始化最小生成树void initTree(PGraph tree){int i,j; tree->vertexNum=6;tree->edgeNum=5;for(i=0;i<tree->vertexNum;i++)tree->vertex='0';for(i=0;i<tree->vertexNum;i++)for(j=0;j<tree->vertexNum;j++) tree->arc=0;}//普里姆算法求最小生成树void prim(PGraph g,PGraph tree){int i,j,k;int index;//指向权值最小的边 ArrayNodeedgeArray; //辅助数组 int length=0; //数组长度int n=1;//统计数组已加入多少个顶点//初始状态把第一个顶点加入树中tree->vertex='A';printf("%-3c",tree->vertex); i=0; while(1){ //寻找与顶点i相接且这条边的另一个顶点不在树中的边,存入edgeArray数组中for(j=0;j<g->vertexNum;j++){if(g->arc > 0){//判断这条边的另一个顶点在不在树中for(k=0;k<tree->vertexNum;k++){if(tree->vertex == g->vertex)break;}if(k == tree->vertexNum){ edgeArray.from=i; edgeArray.to=j; edgeArray.weight=g->arc; edgeArray.flag=0; length++;}}}//从数组中选择权值最小的边index=-1;for(j=0;j<length;j++){if(index == -1 && edgeArray.flag == 0)index=j; if(edgeArray.flag==0 && edgeArray.weight < edgeArray.weight)index=j;}//在树中加入一个顶点，且把这条权值最小的边加入树中tree->vertex.to]='A'+edgeArray.to; edgeArray.flag=1;tree->arc.from].to]=edgeArray.weight;tree->arc.to].from]=edgeArray.weight;//当这个顶点加入树中时，与这个顶点相邻的边不可加入树中for(k=0;k<length;k++){if(edgeArray.to == edgeArray.to)edgeArray.flag=1;}i=edgeArray.to;printf("%-3c",tree->vertex);n++;//当有g->vertexNum个顶点时，最小生成树构造完成if(n==g->vertexNum)break;}}//判断两个顶点是否连通（广度优先搜索）int connected(PGraph tree,int from,int to){int i,j,k;int vertex;//看成队列int front,rear;if(from==to)return 1;front=rear=0;//把第一个顶点存入数组vertex=from;//遍历treewhile(front<=rear){i=vertex; for(j=0;j<tree->vertexNum;j++)if(tree->arc>0){if(j==to)return 1;//判断此顶点是否在队列中for(k=0;k<rear;k++)if(vertex == j)break;if(k==rear) vertex=j;}front++;}return 0;}//克鲁斯卡尔算法求最小生成树void kruskal(PGraph g,PGraph tree){ ArrayNodeedgeArray; //辅助数组 int length=0;int i,j,k,index,n;//顶点先加入树中for(i=0;i<tree->vertexNum;i++)tree->vertex=i+'A';//1.把所有的边有序(从小到大)的插入edgeArray数组中for(i=0;i<g->vertexNum;i++)for(j=0;j<g->vertexNum;j++){if(i<j && g->arc>0){//寻找插入的位置indexfor(k=0;k<length;k++){ if(edgeArray.weight > g->arc)break;}index=k; //移位for(k=length;k>index;k--) edgeArray=edgeArray;//插入length++;edgeArray.flag=0;edgeArray.from=i;edgeArray.to=j;edgeArray.weight=g->arc;}}//2.从小到大取出n-1条边构造最小生成树n=0;while(n < g->vertexNum-1){//从小到大取一条符合要求的边for(k=0;k<length;k++)if(edgeArray.flag==0 && connected(tree,edgeArray.from,edgeArray.to)==0){break;}//把这条边加入树中tree->arc.from].to]=edgeArray.weight;tree->arc.to].from]=edgeArray.weight; edgeArray.flag=1;printf("%-3d",edgeArray.weight);n++;}}void main(){Graph graph;Graph tree;createdGraph(&graph);initTree(&tree);printf("普里姆算法树中顶点加入的顺序:\n");prim(&graph,&tree);printf("\n");initTree(&tree);printf("克鲁斯卡尔算法树中边加入的顺序:\n");kruskal(&graph,&tree);printf("\n");}
页:
[1]