最小生成树实验报告(共6页).docx

精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
一、实验目的
1. 通过上机程序，进一步精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
一、实验目的
1. 通过上机程序，进一步加深对最小生成树的理解。
2. 掌握Kruskal算法。
3. 学会用程序解决离散数学中的问题。
4. 增强我们编写程序的能力。
二、实验内容
求带权无向联通平面图的最小生成树
三、实验环境
，而所设计的程序也在这个环境下通过了编译，运行和测试。
四、实验原理和实现过程
利用Kruskal算法求最小生成树，原理如下：
选取最小权边e1，置边数jß1.
i=n-1结束，否则转c。
设已经选择的边为e1,e2,……，ei,在G中选取不同于e1,e2,……ei的边，使｛e1,e2,……，ei,ei+1｝中无回路且ei+1是满足此条件的最小边。
ißi+1，转b。
根据这个，还有以下思路：
由G生成的最小生成树T所包含的边的集合
1．按非降序权重将E中的边排序
2．建立n个单元素集（每个顶点一个）
3．最小生成树的边集合T初始为空
4 .while |T|<n-1
(x,y)为E中的下一条边
6. if包含x的集合不是与包含y的集合不是同一个集合 then
(x,y)加入到T

if
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
while
五、实验源代码及分析
#include<>
struct Edge
{
int from, to, weight; //定义一个数据结构，存放点和边的关系以及边的权值
};
Edge edge[100], temp; //用定义的数据结构来定义一个数组和一个变量
int i, j, n, m;
int p[100];
int seek(int x) //用来找出当前端点所在集合编号
{
if(p[x]==x)
return x;
else
return p[x]=seek(p[x]);
}
Int Kruskal()
{
int x, y,k=0;
for(i=0;i<100;i++)
p[i]=i;
for(i=0;i<m;i++)
{
x=seek(edge[k].from); //找出当前边两个端点所在集合编号
y=seek(edge[k].to);
if(x!=