算法设计之Kruskal算法的设计(共5页).doc

精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
实验三 Kruskal算法的设计
[实按成本值的非降次序分类.
void Kruskal(EDGE *es, int m, NODE *set, int n, EDGE *st)
功能: 对有n个节点, m条边的连通网, 应用Kruskal算法生成最小生成树, 最小生成树的边存储在数组st中.
void Output(EDGE *st, int n)
功能: 输出最小生成树的各条边.
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
[实验步骤]
设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止;
待各功能子程序调试完毕, 去掉测试程序, 将你的程序整理成功能模块存盘备用.
[实验报告要求]
阐述实验目的和实验内容;
阐述Kruskal算法的原理方法;
提交实验程序的功能模块;
提供测试数据和相应的最小生成树.
[思考与练习]
设计由连通网初始边集数组生成最小堆的算法;
设计输出堆顶元素, 并将剩余元素调整成最小堆的算法;
针对连通网初始边集最小堆表示, 设计Kruskal算法;
采用成本邻接矩阵表示连通网时, 在剩余边中如何实现最小成本边的查找?
采用成本邻接矩阵表示连通网时, 用C语言实现Prim算法.
Kruskal算法：
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
typedef struct node //边结构
{
int u; //边的起点
int v; //边的终点
int dist; //边的长度
}node;
node edge[10000]; //定义一万条边
int n;//n表示程序中边的总数
int use[10000]; //该数组用于标记某条边是否被选入最小生成树
int pre[10000]; //定义一个并查集数组
void init_pre() //初始化并查集数组
{
int i;
for(i=0;i<n;i++)
pre[i]=i;
}
int find(int x) //查找x元素所属集合的根
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
{
int r=x;
while(pre[r]!=r)
{
r=pre[r];
}
return r;
}
void Union(int a,int b) //合并a,b两元素到一个集合
{
pre[a]=b;
}
void Kruskal()
{
int i,f1,f2