数据结构Kruskal算法 百度文库.doc

《数据结构与算法》课程设计报告 题目：Kruskal算法 三．测试数据 图中的A,B,C,D,E,F,G分别代表1,2,3 ,4 ,5 ,6 ,7七个城市，城市之间的连线代表在两城市间建立的连通网络，连线上的权重是在两城市间建立连通网络的花销。 四．算法思想 设有一个有n个顶点的连通网N={V,E},最初先构造一个只有n个顶点，没有边的非连通图T={V, E},图中每个顶点自成一个连通分量。当在E中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到T中；否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。 五．算法设计 程序流程图 算法用到的抽象数据类型定义： 1．ADT Graph{ 数据对象V：V={A,B,,C,D,E,F,G} 数据关系R：R={VR} VR={x,y|P(x,y)^(x,y属于V)} 基本操作： CreatGraph(MGraph *);//图的初始化// MiniSpanTree(MGraph *);//生成最小生成树//； sort(edge* ,MGraph *);//图中的数据按数据的权值进行排序// Swapn(edge *, int, int);//交换元素// Find(int *, int );//找出尾部元素// }ADT Graph 算法中函数编号及功能要求： ① 图的初始化 ② 对权值进行排序 ③ 交换权值以及队头队尾 ④ 得到最小生成树 ⑤ 找尾 函数之间的调用关系（子程序编号见上）： 主函数调用子程序①，④ 子程序②引用① 子程序②引用③ 子程序④引用②和⑤ 六．C语言实现的程序清单 #includestdio.h #includestdlib.h #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,m,n; 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(请输入有边的2个顶点:); scanf(%d %d,n,m); while(n 0 || n G-vexnum || m 0 || n G-vexnum) { printf(输入的数字不符合要求 请重新输入:/n); scanf(%d %d,n,m); } G-arc[n][m].adj = G-arc[m][n].adj = 1; getchar(); printf(请输入%d与%d之间的权值:, n, m); scanf(%d,G-arc[n][m].weight); } } 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,