克鲁斯卡尔算法求最小生成树.docx

克鲁斯卡尔算法求最小生成树
目 录
???????????????????????
Kruskal 算法
主程序
图1流程图
抽象数据种类 MFSet 的定义：
ADT MFSet {
数据对象 ：若设 S 是 MFSet 型的会集，则它由 n(n>0) 个子集 Si（i = 1,2...,n ）
构成，每个子集的成员代表在这个子集中的城市。
数据关系 ： S1 U S2 U S3 U... U Sn = S, Si 包含于 S（i = 1,2,...n ）
Init (n): 初始化会集，构造 n 个会集，每个会集都是单成员， 根是其自己。 rank 数组初始化 0
Find(x): 查找 x 所在会集的代表元素。 即查找根， 确定 x 所在的会集， 并路径压
缩。
Merge(x, y): 检查 x 与 y 可否在同一个会集，若是在同一个会集则返回假，否则
按秩合并这两个会合并返回真。
}
文案大全
3/11
克鲁斯卡尔算法求最小生成树
合用标准
主程序：
int main()
{
初始化；
while ( 条件 )
{
接受命令 ;
办理命令 ;
}
return 0;
}
抽象数据种类 图 的定义以下：
ADT Graph{
数据对象 V：V 是拥有相同特色的数据元素的会集，成为极点集。
数据关系 R：R={VR} VR={<v,w>|v ， w∈ V 且 P（v，w）， <v ，w> 表示从 v 到 w 的弧，谓词 P（v，w）定义了弧 <v ，w>的意义或信息 } 基本操作 P：
CreateGraph （&G ，V，VR ）；
初始条件： V 是图的极点集， VR 是图中弧的会集。
操作结果：按 V 和的 VR 定义构造图 G 。
DestoryGraph （ &G ）；
初始条件：图 G 存在。
操作结果：销毁图 G。
LocateVex （ G， u）；
初始条件：图 G 存在， u 和 G 中是极点有相同特色。
操作结果：若 G 中存在极点 u，则返回该极点在图中地址；否则返回其他信
息。
GetVex （ G， v）；
初始条件：图 G 存在， v 是 G 中某个极点。
操作结果：返回 v 的值。
PutVex （ &G ，v，value ）；
初始条件：图 G 存在， v 是 G 中某个极点。
操作结果：对 V 赋值 value ，
FirstAdjVex （G ， v）；
文案大全
4/11
克鲁斯卡尔算法求最小生成树
合用标准
初始条件：图 G 存在， v 是 G 中某个极点。
操作结果：返回 v 的第一个毗邻极点。若极点在 G 中没有极点，
则返回“空”。
NextAdjVex （G，v，w）；
初始条件：图 G 存在， v 是 G 中某个极点， w 是 v 的毗邻极点。
操作结果：返回 v 的（有对于 w 的）下一个毗邻极点。若 w 是 v 的最后一个毗邻极点，则返回“空” 。
InsertVex （ &G ，v）；
初始条件：图 G 存在， v 和途中极点有相同特色。
操作结果：在图 G 中增添新极点 v。
DeleteVex （ &G ，v）；
初始条件：图 G 存在， v 是 G 中某个极点。
操作结果：删除 G 中极点 v 及其相关的弧。
InsertArc （ &G ， v，w）；
初始条件：图 G 存在， v 和 w 是 G 中两个极点。
操作结果：在 G 中增添弧 <v， w> ，若 G 是无向的，则还增添对称弧
DeleteArc