课程设计---克鲁斯卡尔算法求最小生成树(共14页).doc

精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业

课程设计报告
课程名称：数据结 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是否在同一个集合，如果在同一个集合则返回假，否则按秩合并这两个集合并返回真。
}
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
：
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）；
初始条件：图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是无向的，则还增添 对称弧<v，w>。
DeleteArc（&G，v，w）；
初始条件：图G存在，v和w是G中两个顶点。
操作结果：在G中删除弧<v，w>，若G是无向的，则还删除对称弧<v，w>。
DFSTravrese（G，Visit（））；
初始条件：图G存在，Visit是顶点的应用函数。
操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数 Visit一次且仅一次。一旦Visit（）失败，则操作失败。
精选优质文档-----倾情为你奉上
精选优质文档-----倾情为你奉上
专心---专注---专业
专心---专注---专业
精选优质文档-----倾情为你奉上
专心---专注---专业
BFSTravrese（G，Visit（））；
初始条件：图G存在，Visit是顶点的应用函数。
操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit（）失败，则操作失败。
}ADT Graph
树 的定义如下：
ADT Tree{
数