目录1.需求分析 (2)1.1 设计题目 (2)1.2 设计任务及要求 (2)1.3课程设计思想 (2)1.4 程序运行流程 (2)1.5软硬件运行环境及开发工具 (2)2.概要设计 (2)2.1流程图 (2)2.2抽象数据类型MFSet的定义 (3)2.3主程序 (4)2.4抽象数据类型图的定义 (4)2.5抽象数据类型树的定义 (5)3.详细设计 (7)3.1程序 (7)4.调试与操作说明 (10)4.1测试结果 (10)4.2调试分析 (11)5.课程设计总结与体会 (11)5.1总结 (11)5.2体会 (11)6. 致谢 (12)7. 参考文献 (12)1.需求分析1.1 设计题目：最小生成树1.2 设计任务及要求：任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。
1.3 课程设计思想：Kruskal算法采用了最短边策略(设G=(V,E)是一个无向连通网，令T=(U，TE)是G的最小生成树。
最短边策略从TE={}开始，每一次贪心选择都是在边集E中选择最短边(u,v)，如果边(u,v)加入集合TE中不产生回路，则将边(u,v)加入边集TE中，并将它在集合E中删去。
)，它使生成树以一种任意的方式生长，先让森林中的树木随意生长，每生长一次就将两棵树合并，最后合并成一棵树。
1.4程序运行流程:1)提示输入顶点数目；2)接受输入，按照项目要求产生边权值的随机矩阵；然后求解最小生成树；3)输出最小生成树并且退出；1.5 软硬件运行环境及开发工具：VC2.概要设计2.1流程图开始定义数据类型定义图定义树定义图的顶点数和边数Kruskal算法主程序图1流程图2.2抽象数据类型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 数组初始化0Find(x):查找x所在集合的代表元素。
即查找根，确定x所在的集合，并路径压缩。
Merge(x, y):检查x与y是否在同一个集合，如果在同一个集合则返回假，否则按秩合并这两个集合并返回真。
}2.3主程序：int main(){初始化；while (条件){接受命令;处理命令;}return 0;}2.4抽象数据类型图的定义如下：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 Graph2.5抽象数据类型树的定义如下：ADT Tree{数据对象D:D是具有相同特性数据元素的集合。
数据关系R：若D为空集，则称为空树；若D仅含一个元素数据，则R为空集，否则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H 下无前驱；（2）若D-{root}≠Φ，则存在D-{root}的一个划分D1，D2，…，D m（m>0），对任意j≠k（1≤j,k≤m）有D j∩D k=Φ，且对任意的I（1≤i≤m），惟一存在数据元素x i∈D i有<root，x i>∈H；（3）对应于D-{root}的划分，H-{<root，x1>，…，<roor，x m>}有惟一的一个划分H1，H2，…，H m（m＞0），对任意j≠k(1≤j，k≤m)有H j∩H k=Φ，且对任意I（1≤i≤m），H i是D i上的二元关系，（D i，{H i}）是一棵符合本定义的树，称为跟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_e，value）；初始条件：树T存在，cur_e是T中某个结点。
操作结果：结点cur_e赋值为value。
Parent（T，cur_e）；初始条件：树T存在，cur_e是T中某个结点。
操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。
LeftChild（T，cur_e）；初始条件：树T存在，cur_e是T中某个结点。
操作结果：若cur_e是T的非叶子结点，则返回它的最左子，否则返回“空”。
RightSibling（T，cur_e）；初始条件：树T存在，，cur_e是T中某个结点。
操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”。
InsertChild（&T，&p，I，c）；初始条件：树T存在，P指向T中某个结点，1≤i≤p所指向的结点度数+1，非空树c与T不相交。
操作结果：插入c为T中p指结点的第i棵子树。
DeleteChild（&T，&p，i）；初始条件：树T存在，p指向T中某个结点，1≤i≤p指结点的度。
操作结果：删除T中p所指结点的第i棵子树。
TraverseTree（T，Visit（））；初始条件：树T存在，Visit是对结点操作的应用函数。
操作结果：按某种次序对T的每个结点调用函数visit（）一次且至多一次。
一旦vista（）失败，则操作失败。
}ADT Tree3.详细设计3.1程序：如下#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_NAME 5#define MAX_VERTEX_NUM 30typedef char Vertex[MAX_NAME];/*顶点名字数组*/typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接矩阵*/typedef struct /*定义图*/{Vertex vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;}MGraph;int LocateVex(MGraph *G,Vertex u){int i;for(i=0;i<G->vexnum;++i)if(strcmp(G->vexs[i],u)==0)return i;return -1;}void CreateGraph(MGraph *G){int i,j,k,w;Vertex va,vb;printf("请输入无向网G的顶点数和边数(以空格作为间隔): \n");scanf("%d %d",&G->vexnum,&G->arcnum);printf("请输入%d个顶点的名字(小于%d个字符):\n",G->vexnum,MAX_NAME);for(i=0;i<G->vexnum;++i) /*构造顶点集*/scanf("%s",G->vexs[i]);for(i=0;i<G->vexnum;++i) /*初始化邻接矩阵*/for(j=0;j<G->vexnum;++j)G->arcs[i][j]=0x7fffffff;printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔):\n",G->arcnum);for(k=0;k<G->arcnum;++k){scanf("%s%s%d%*c",va,vb,&w);i=LocateVex(G,va);j=LocateVex(G,vb);G->arcs[i][j]=G->arcs[j][i]=w; /*对称*/}}void kruskal(MGraph G){FILE *fpt;fpt = fopen("9.txt","w");/*打开文档，写入*/fprintf(fpt,"最小生成树的各条边为:\n");int i,j;int k=0,a=0,b=0,min=G.arcs[a][b],min_out;printf("最小生成树的各条边为:\n");while(k<G.vexnum-1){for(i=0;i<G.vexnum;++i)for(j=i+1;j<G.vexnum;++j)if(G.arcs[i][j]<min){min=G.arcs[i][j];a=i;b=j;}min_out=min;min=G.arcs[a][b]=0x7fffffff;printf("%s-%s-%d\n",G.vexs[a],G.vexs[b],min_out);fprintf(fpt,"%s-%s-%d\n",G.vexs[a],G.vexs[b],min_out);k++;}fclose(fpt);}void main(){MGraph g;CreateGraph(&g);kruskal(g);}4. 调试与操作说明4.1测试结果：如下图图2测试结果1图3测试结果24.2调试分析本程序利用克鲁斯卡尔算法求最小生成树数据结构清晰因而调试比较顺利。