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

克鲁斯卡尔算法求最小生成树.docx精品文档
精品文档
精品文档
目录
1.
需求分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯
2

目⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯
2

任及要，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（）失败，则操作失败。
}ADTGraph
树的定义如下：
ADTTree{
数据对象D:D是具有相同特性数据元素的集合。
数据关系R：若D为空集，则称为空树； 若D仅含一个元素数据，则R为空集，
否则R={H}，H是如下二元关系：
（1）在D中存在唯一的称为根的数据元素 root，它在关系H下无前驱；
精品文档
精品文档
精品文档
文案大全
精品文档
精品文档
精品文档
实用标准
（2）若D-{root}≠，存在D-{root}的一个划分D1，D2，⋯，Dm（m>0），任意j≠k（1≤j,k≤m）有Dj∩Dk=，且任意的I（1≤i≤m），惟一存在数据元素xi∈Di有<root，xi>∈H；
（3）于D-{root} 的划分，H-{<root，x1>，⋯，<roor，xm>}有惟一的一
个划分H1，H2，⋯，Hm（m＞0），任意j≠k(1≤j，k≤m)有Hj∩Hk= ，且任
意I（1≤i≤m），Hi是Di上的二元关系，（Di，{Hi}）是一棵符合本定的，称跟root的子。
基本操作P：
InitTree （&T）；
操作果：构造空 T。
DestoryTree（&T）；
初始条件：T存在。
操作果： T。
CreateTree（&T，definition ）；
初始条件：definition 出T的定。
操作果：按definition 构造T。
ClearTree（&T）；
初始条件：T存在。
操作果：将 T清空。
TreeEmptey（T）；
初始条件：T存在。
操作果：若T空，返回 TRUE，否FALSE。
TreeDepth（T）；
初始条件：T存在。
操作果：返回 T的深度。
Root（T）；
初始条件：T存在。
操作果：返回 T的跟。
Value（T，cur_e）；
初始条件：T存在，cur_e是T中某个点。
操作果：返回 cur_e的。
Assign（T，cur