离散数学大作业.doc

离散数学大作业.doc离散数学大作业
最小生成树的编程实现：Kruskal算法
一、 程序代码：
# include<>
#define N 255
typedefstruct
{
intbegin,end;
int weight;
}graphedge;
intgetedge(graphedge edge[]);
void swap(int * pl,int * p2);
voidsortedge(graphedge edge[],int k);
int find(int father[],int e);
voidkruskal(graphedge edge[],int k);
int main(void)
{
int n; /*n为图的实际边树*/
graphedgeedgea[N]; /* 存储图的数组 */
/*将图的顶点、边和权输
n=getedge(edgea);
sortedge(edgea,n);
/*将图的边集数组按边权
值排序*/
kruskal(edgea,n);
/*求带权的最小生成树*/
return 0;
intgetedge(graphedge edge[])
/*建立图的数组，并返回图
的边数*/
intk,a,b;
int c;
printf（"请输入图的总边树:
\n");
scanf("%d",&k);
for(int i=l;i<=k;i++)
printf（"起点终点权="）;
scanf("%d %d %d",&a,&b,&c);
edge[i].begin=a;
edge[i].end=b;
edge[i].weight=c;
return (k);
/*交换函数*/
void swap(int* pl,int* p2)
int temp;
temp=*pl;
*pl=*p2;
*p2=temp;
}
void sortedge(graphedge edge[],int k) /*将所有的边按权
值排序*/
{
for(int i=l;i<k;i++)
for(int j=i+l;j<=k;j++)
if(edge[i].weight>edge[j].weight)
{
swap(&edge[i]. begin,&edge[j]. begin);
swap(&edge[i].end,&edge[j].end);
swap(&edge[i].weight,&edge[j].weight);
}
}
int find(int father[],int e) /*查找与起点连接的
int f=e;
while(father[f]>0)
f=father[f];
return (f);
}
void kruskal(graphedge edge[],int k) /*构造最小生成树的
Kruskal 算法*/
{
int father[N],