计算机科学与工程学院（ 院、系）网络工程 专业 071 班 组 计算机算法设计与分析 课
学号 200710224133 姓名121 实验日期 2010. 教师评定
1、实验目的：
通过简单的实际应用例子，了解和掌握最小生成树问题的要点和方法。
2、算法分析：
设计思想：
图的存储使用数组表示法，即邻接矩阵存储，结构体包含图的邻接矩阵，当前顶点数和弧数。图的初始化使用二重循环得到顶点和表的权值，邻接矩阵的打印使用二重for循环。然后把图各边的权值按从小到大排序；然后依次把最小边加入进来，即生成最小生成树。
克鲁斯卡尔算法：假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，按照构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至只有一棵树，也即子图中含有 n-1条边为止。
1、设定图的抽象数据类型:
ADT Graph{
数据对象V:V是具有相同特性的数据元素的集合,称为点集.
数据关系R:
R={VR}
VR={(v,w)|v,w属于V,(v,w)表示v和w之间存在的路径}
基本操作P:
CreatGraph(&G,V,VR)
初始条件:V是图的顶点集,VR是图中弧的集合.
操作结果:按V和VR是定义构造图G.
Sort(edge* ,MGraph *)
初始条件: 图G存在，各边权值已知；
操作结果:对权值进行排序；
Find(int *, int )
初始条件:前者为已存在的集合，后者为集合中的元素；
操作结果:查找函数，确定后者所属子集；
MiniSpanTree(MGraph *)
初始条件: 图G存在，各边权值已知；
操作结果:生成最小树；
Swapn(edge *, int, int)
初始条件: 图G存在，各边权值已知；
操作结果:交换某两个边的权值；
2 图的存储结构
typedef struct
{
int adj;
int weight;
}AdjMatrix[MAX][MAX];
typedef struct
{
AdjMatrix arc;
int vexnum, arcnum;
}MGraph;
typedef struct
{
int begin;
int end;
int weight;
}edge;
3 本程序包含的模块
}
1）初始化操作，结构体定义；
2）函数声明模块；
3）函数定义模块；
4）主程序模块
Main()
{
调用函数生成图；
判断图是否为空；（空则从新输入）
调用函数生成最小生成树；
退出；
3、程序代码：
#include #include #define M 20 #define MAX 20 typedef struct { int begin; int end; int weight; }edge; typedef struct { int adj; int weight; }AdjMatrix[MAX][MAX]; typedef struct { AdjMatrix arc; int vexnum, arcnum; }MGraph; void CreatGraph(MGraph *); void sort(edge* ,MGraph *); void MiniSpanTree(MGraph *); int Find(int *, int ); void Swapn(edge *, int, int); void CreatGraph(MGraph *G) { int i, j,n, m; printf("请输入边数和顶点数:"); scanf("%d %d",&G->arcnum,&G->vexnum); for (i = 1; i <= G->vexnum; i++) { for ( j = 1; j <= G->vexnum; j++) { G->arc[i][j].adj = G->arc[j][i].adj = 0; } } for ( i = 1; i <= G->arcnum; i++) { printf("\\n请输入有边的2个顶点"); scanf("%d %d",&n,&m); while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum) { printf("输入的数字不符合要求 请重新输入:"); scanf("%d%d",&n,&m); } G->arc[n][m].adj = G->arc[m][n].adj = 1; getchar(); printf("\\n请输入%d与%d之间的权值:", n, m); scanf("%d",&G->arc[n][m].weight); } printf("邻接矩阵为:\\n"); for ( i = 1; i <= G->vexnum; i++) { for ( j = 1; j <= G->vexnum; j++) { printf("%d ",G->arc[i][j].adj); } printf("\\n"); } } void sort(edge edges[],MGraph *G) { int i, j; for ( i = 1; i < G->arcnum; i++) { for ( j = i + 1; j <= G->arcnum; j++) { if (edges[i].weight > edges[j].weight) { Swapn(edges, i, j); } } } printf("权排序之后的为:\\n"); for (i = 1; i < G->arcnum; i++) { printf("<< %d, %d >> %d\\n", edges[i].begin, edges[i].end, edges[i].weight); } } void Swapn(edge *edges,int i, int j) { int temp; temp = edges[i].begin; edges[i].begin = edges[j].begin; edges[j].begin = temp; temp = edges[i].end; edges[i].end = edges[j].end; edges[j].end = temp; temp = edges[i].weight; edges[i].weight = edges[j].weight; edges[j].weight = temp; } void MiniSpanTree(MGraph *G) { int i, j, n, m; int k = 1; int parent[M]; edge edges[M]; for ( i = 1; i < G->vexnum; i++) { for (j = i + 1; j <= G->vexnum; j++) { if (G->arc[i][j].adj == 1) { edges[k].begin = i; edges[k].end = j; edges[k].weight = G->arc[i][j].weight; k++; } } } sort(edges, G); for (i = 1; i <= G->arcnum; i++) { parent[i] = 0; } printf("最小生成树为:\\n"); for (i = 1; i <= G->arcnum; i++) { n = Find(parent, edges[i].begin); m = Find(parent, edges[i].end); if (n != m) { parent[n] = m; printf("<< %d, %d >> %d\\n", edges[i].begin, edges[i].end, edges[i].weight); } } } int Find(int *parent, int f) { while ( parent[f] > 0) { f = parent[f]; } return f; } int main(void) { MGraph *G; G = (MGraph*)malloc(sizeof(MGraph)); if (G == NULL) { printf("memory allcation failed,goodbye"); exit(1); } CreatGraph(G); MiniSpanTree(G); system("pause"); return 0; } 4、时间复杂度分析： 由于在图的初始化以及邻接矩阵的打印时均使用了循环的嵌套，故其时间复杂度为 O（n2 ）的；其他操作的时间复杂度均为O（1）。 5、总结： 通过一个简单的实际例子，比较好地掌握了最小生成树的算法思想。下载本文
