克鲁斯卡尔算法求最小生成树.doc

数 据 结 构
上 机 报 告
姓名：张可心 学号：**********
一、题目描述：
Kruskal 算法是一种按照图中边的权值递增的顺序构造最小生成树的方法。其基本思想是：设无向连通网为G＝（V，E），令G 的最小生成树为T，其初态为T＝（V，{}），即开始时，最小生成树T 由图G 中的n 个顶点构成，顶点之间没有一条边，这样T 中各顶点各自构成一个连通分量。然后，按照边的权值由小到大的顺序，考察G 的边集E 中的各条边。若被考察的边的两个顶点属于T 的两个不同的连通分量，则将此边作为最小生成树的边加入到T 中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T 中的连通分量个数为1 时，此连通分量便为G 的一棵最小生成树。
(a)所示，按照Kruskal 所示。在构造过程中，按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。依据生成树的概念，n 个结点的生成树，有n－1 条边，故反复上述过程，直到选取了n－1 条边为止，就构成了一棵最小生成树。
二、目的：
本实验通过实现最小生成树的算法，使学生理解图的数据结构存储表示，并能理解最小生成树Kruskal 算法。通过练习，加强对算法的理解，提高编程能力。
三、内容：
（1）假定每对顶点表示图的一条边，每条边对应一个权值；
（2）输入每条边的顶点和权值；
（3）输入每条边后，计算出最小生成树；
（4）打印最小生成树边的顶点及权值。
四、数据结构及程序
#include <>
#define max 20
int arcvisited[36];
typedef struct acr
{
int pre;
int bak;
int weight;
}edg;
typedef struct ArcCell
{
int adj;
}ArcCell,AdjMatrix[6][6];
typedef struct
{
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph_L;
int find(int arcvisited[],int f)
{
while(arcvisited[f]>0)
f = arcvisited[f];
return f;
}
void kruscal_arc(MGraph_L G)
{
edg edgs[36]={10000};
int i,j,k=0;
int x,y,m,n;
int buf,edf;
for(i=0;i!= ;++i)
for(j=i;j!=;++j)
{
if([i][j].adj!=10000)
{
edgs[k].pre = i;
edgs[k].bak = j;
edgs[k].weight = [i][j].adj;
++k;
}
}
for(i=0;i != ;++i)
arcvisited[i]