根据书中的提示,本人编写kruskal(习惯写法)如下:(这个算法绝对正确!请仔细理解,为简单起见算法中去掉图的输入函数,用grah[6][6]保存具有代表性的演示图)

#include <stdio.h> #include <string.h> #include <conio.h> #define max_size 100 #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b))

typedef struct krus { int node1; int node2; int vex; }krus;

typedef struct PTNode { int data; int parent; }PTNode;

typedef struct PTree { PTNode nodes[max_size]; int n; }PTree;

typedef PTree MFSet;

int initptree(MFSet* p) { int i; (*p).n=6; for(i=0;i<6;++i) { (*p).nodes[i].data=i; (*p).nodes[i].parent=-1; } }

int find_mfset(MFSet s,int i) { int j;

for(j=i;s.nodes[j].parent>0;j=s.nodes[j].parent); return j; }

int mix_mfset(MFSet* s,int i,int j) { (*s).nodes[i].parent=j; return 1; }

int fix_mfset(MFSet* s,int i) { int j,k,t; if(i<1||i>(*s).n) return -1; for(j=i;(*s).nodes[j].parent>0;j=(*s).nodes[j].parent); for(k=i;k!=j;k=t) { t=(*s).nodes[k].parent; (*s).nodes[k].parent=j; } return j; }

int kruskal(void) { int grah[6][6]={{-1, 6, 1, 5,-1,-1}, { 6,-1, 5,-1, 3,-1}, { 1, 5,-1, 5, 6, 4}, { 5,-1, 5,-1,-1, 2}, {-1, 3, 6,-1,-1, 6}, {-1,-1, 4, 2, 6,-1}}; krus ve[10],vetemp; MFSet tree; int i,j,k=0,temp=1,nodex,nodey,nodevex,gen1,gen2,js=0;

for(i=0;i<6;++i) { for(j=temp;j<6;++j) { if(grah[i][j]!=-1) { ve[k].node1=i; ve[k].node2=j; ve[k].vex=grah[i][j]; ++k; } } ++temp; }

initptree(&tree);

for(i=9;i>0;--i) { for(j=0;j<i;j++) { if(ve[j].vex>ve[j+1].vex) { vetemp=ve[j]; ve[j]=ve[j+1]; ve[j+1]=vetemp; } } }

for(i=0;i<10&&js<5;++i) { nodex=ve[i].node1; nodey=ve[i].node2; nodevex=ve[i].vex; gen1=find_mfset(tree,nodex); gen2=find_mfset(tree,nodey); if(gen1!=gen2) { ++js; mix_mfset(&tree,gen1,gen2); printf("%d gen:%d, %d gen:%d\n",nodex,gen1,nodey,gen2); printf("the %d:%d->%d is %d\n",i,nodex,nodey,nodevex); } } } int main(void) { clrscr(); kruskal(); return 0; }

算法思想是:根据kruskal本人的要求:),将图的顶点与边分开.将边从小到大排序,每次取一最小边,并将其添在这两个顶点上(添加后不产生回路).具体最法为:采用离散数学中的集合运算.图的每个顶点为一个集合(集合中只有一个元素的集合).然后每读一个边就把这两个顶点所在的集合进行并集运算.这样如果有n个集合,读入一个边就是n-1个集合了.如果边的两个顶点同属于一个集合则,舍弃这条边读下一条边.一直到只有一个集合算法结束.对于集合运算参考<<数据结构>>(c语言版),严蔚敏,吴伟民 142页介绍!