生成广工数据结构课程设计最小生成树

广工首页时间:2021-04-07 阅读:()

课程设计

课程名称数据结构学院_专业班级学号__________________学生姓名

指导教师

______________

2015年7月2日

1.需求分析

题目最小生成树问题

若要在n个城市之间建设通讯网络只需要架设 n-1条线路即可。如何以最低的经济代价建设这个通讯网是一个网的最小生成树问题。

要求

1 利用克鲁斯卡尔算法求网的最小生成树。

2 实现并查集。以此表示构造生成树过程中的连通分量。3 以文本形式输出生成树中各条边以及他们的权值。输入的形式和输入值的范围十进制数 0—100。

输出的形式十进制数。

程序所能达到的功能遍历所有城市生成最小生成树。

测试数据

正确数据

城市个数3 3个城市的邻接矩阵 1,2,3;2,100,4;3,4,6

输出结果第1条路段为1――2,权值为2

第2条路段为1――3,权值为3

遍历所有城市得到最小生成树的代价为 5错误数据城市个数3;城市的邻接矩阵 -2,5,1;3,0,1;3,2,1

输出结果输入错误请重新输入

2■概要设计

数据类型定义如下typedef struct node

{int str; /*起点*/intend; /*终点*/int dis;/*距离*/

}n ode;node p[max],temp; /*p记录城市信息*/

int pre[100],rank[100];/*用于判断是否构成回路*/int n=0叩记录城市间权值*/

主程序流程如下

3■详细设计

(1) 克鲁斯卡尔算法思想基本描述

假设连通图N=(V, {E}) 贝冷最小生成树的初始状态为只有n顶点而无边的非连通图T=(V,{ }) 图中每个顶点自成一个连通分量。在E中选择代价最小的边若该边依附的顶点落在T中不同的连通分量上则将此边加入到T中,否则舍去此边而选择下一条代价最小的边。以此类推直至T中所有顶点都在同一个连通分量上为止。

(2) 克鲁斯卡尔算法设计a.设置计数器E初值为0,记录已选中的边数。将所有边从小到大排序 存于p[]中。b.从p[]中选择一条权值最小的边检查其加入到最小生成树中是否会构成回路若是 贝吐匕边不加入生成树否则加入到生成树中计数器E累加1 。c.从E中删除此最小边转b继续执行直到k=n-1,算法结束。

判断是否回路

设置集合S,其中存放已加入到生成树中的边所连接的顶点集合当一条新的边要加入到生成树中时检查此边所连接的两个顶点是否都已经在S中若是,则表示构成回路否则若有一个顶点不在S中或者两个顶点都不在S中则

不够成回路。

/*需要的函数声明*/int mai n( ) //主程序int me nu( ) //菜单函数void create( ) //输入城市信息函数vo id judge( ) //判断是否能够生成最小生成树函数void display( ) //打印输出void s et ( ) //初始化pre[],rank[]函数void find( ) //判断是否构成回路函数void Union( ) //将能构成最小生成树的边添加到一个集合void Krushal() 〃克鲁斯算法求最小生成树

/*菜单函数*/int menu() {

int m;p rintf(". . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2015年7月2日. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .\n\n");p rintf(" 求最小生成树\n");prin tf("__________________________________________\n\n");p rintf(" 1输入城市之间的信息\n");prin tf(" 2判断是否能构成一个最小生成树\n");p rintf(" 3遍历所有城市生成最小生成树\n");prin tf(" 0退出\n");prin tf("__________________________________________\n\n");p rintf(" 请输入所选功能0-3\n");sea nf("%d",&m);if(m<0| |m>3)return 4;return m;

}

/*下面三个函数作用是检验当一条边添加进去是否会产生回路 */void set(int x)/*初始化*/

{p re[x]=x;ran k[x]=0;

}

/*找到这个点的祖先*/int fin d(i nt x)

{if(x!=p re[x])pre[x]=fin d(pre[x]);return pre[x];

/*将这两个数添加到一个集合里去*/void Union(i nt x,i nt y)

{x=find(x);

y=find(y);if(ran k[x]>=ran k[y])

{p re[y]=x;ran k[x]++;

}els e pre[y]=x;

}