克鲁斯卡尔算法

.

课程设计报告

课程名称：数据结构课程设计

设计题目：克鲁斯卡尔算法求最小生成树

系别：计算机系

专业：软件技术

学生姓名：学号:

日期:2013年1月5日-2013年1月11日

.

目录

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主程序………………………………………………………………………3

2.4抽象数据类型图的定义…………………………………………………4

2.5抽象数据类型树的定义…………………………………………………6

3.详细设计……………………………………………………………………………8

3.1程序…………………………………………………………………………8

4.调试与操作说明……………………………………………………………………11

4.1测试结果……………………………………………………………………11

4.2调试分析……………………………………………………………………12

5.课程设计总结与体会………………………………………………………………12

5.1总结…………………………………………………………………………12

5.2体会…………………………………………………………………………12

6.致谢…………………………………………………………………………………13

7.参考文献……………………………………………………………………………13

.

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软硬件运行环境及开发工具：VC

2.概要设计

2.1流程图

.

图1流程图

2.2抽象数据类型MFSet的定义：

ADTMFSet{

数据对象：若设S是MFSet型的集合，则它由n(n>0)个子集Si（i=1,2...,n）构成，

每个子集的成员代表在这个子集中的城市。

数据关系：S1US2US3U...USn=S,Si包含于S（i=1,2,...n）

Init(n):初始化集合，构造n个集合，每个集合都是单成员，根是其本身。rank数

组初始化0

Find(x):查找x所在集合的代表元素。即查找根，确定x所在的集合，并路径压缩。

Merge(x,y):检查x与y是否在同一个集合，如果在同一个集合则返回假，否则按秩合

并这两个集合并返回真。

}

开始

定义数据类型

定义图

定位

定义图中的顶点数和边

数

Kruskal算法

主程序

.

2.3主程序：

intmain()

{

初始化；

while(条件)

{

接受命令;

处理命令;

}

return0;

}

2.4抽象数据类型图的定义如下：

ADTGraph{

数据对象V：V是具有相同特性的数据元素的集合，成为顶点集。

数据关系R：

R={VR}

VR={|v，w∈V且P（v，w），表示从v到w的弧，谓词

P（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中添加弧，若G是无向的，则还增添对称弧

w>。

DeleteArc（&G，v，w）；

初始条件：图G存在，v和w是G中两个顶点。

操作结果：在G中删除弧，若G是无向的，则还删除对称弧。

DFSTravrese（G，Visit（））；

初始条件：图G存在，Visit是顶点的应用函数。

操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit一

.

次且仅一次。一旦Visit（）失败，则操作失败。

BFSTravrese（G，Visit（））；

初始条件：图G存在，Visit是顶点的应用函数。

操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次

且仅一次。一旦Visit（）失败，则操作失败。

}ADTGraph

2.5抽象数据类型树的定义如下：

ADTTree{

数据对象D:D是具有相同特性数据元素的集合。

数据关系R：若D为空集，则称为空树；若D仅含一个元素数据，则R为空集，否

则R={H}，H是如下二元关系：

（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前

驱；

（2）若D-{root}≠，则存在D-{root}的一个划分D

1

，D

2

，…，D

m

（m>0），对任

意j≠k（1≤j,k≤m）有D

j

∩D

k

=，且对任意的I（1≤i≤m），惟一存在数据元素x

i

∈D

i

有

i

>∈H；

（3）对应于D-{root}的划分，H-{

1

>，…，

m

>}有惟一的一个划

分H

1

，H

2

，…，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（）失败，则操作失败。

}ADTTree

3.详细设计

3.1程序：如下

#include

#include

#include

#defineMAX_NAME5

#defineMAX_VERTEX_NUM20

typedefcharVertex[MAX_NAME];/*顶点名字串*/

typedefintAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/

typedefstruct/*定义图*/

{

Vertexvexs[MAX_VERTEX_NUM];

AdjMatrixarcs;

intvexnum,arcnum;

}MGraph;

typedefstruct

{

Vertexadjvex;/*当前点*/

intlowcost;/*代价*/

}minside[MAX_VERTEX_NUM];

intLocateVex(MGraph*G,Vertexu)

.

{

inti;

for(i=0;ivexnum;++i)

if(strcmp(G->vexs[i],u)==0)

returni;

return-1;

}

voidCreateGraph(MGraph*G)

{

inti,j,k,w;

Vertexva,vb;

printf("请输入无向网G的顶点数和边数(以空格为分隔)n");

scanf("%d%d",&G->vexnum,&G->arcnum);

printf("请输入%d个顶点的值(<%d个字符):n",G->vexnum,MAX_NAME);

for(i=0;ivexnum;++i)/*构造顶点集*/

scanf("%s",G->vexs[i]);

for(i=0;ivexnum;++i)/*初始化邻接矩阵*/

for(j=0;jvexnum;++j)

G->arcs[i][j]=0x7fffffff;

printf("请输入%d条边的顶点1顶点2权值(以空格作为间隔):n",G->arcnum);

for(k=0;karcnum;++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;/*对称*/

}

}

voidkruskal(MGraphG)

.

{

intset[MAX_VERTEX_NUM],i,j;

intk=0,a=0,b=0,min=[a][b];

for(i=0;i<;i++)

set[i]=i;

printf("最小代价生成树的各条边为:n");

while(k<-1)

{

for(i=0;i<;++i)

for(j=i+1;j<;++j)

if([i][j]

{

min=[i][j];

a=i;

b=j;

}

min=[a][b]=0x7fffffff;

if(set[a]!=set[b])

{

printf("%s-%sn",[a],[b]);

k++;

for(i=0;i<;i++)

if(set[i]==set[b])

set[i]=set[a];

}

}

}

voidmain()

{

.

MGraphg;

CreateGraph(&g);

kruskal(g);

system("PAUSE");

getch();

}

4.调试与操作说明

4.1测试结果：如下图

图2测试结果1

.

图3测试结果2

4.2调试分析

本程序利用克鲁斯卡尔算法求最小生成树数据结构清晰因而条是比较顺利。在调试过

程中主要是参数的传递比较不容易掌握。本程序的关键部分是如何确定一条边的两个端点

是否属于同一连通分支，合并两个连通分支。

5.课程设计总结与体会

5.1总结：

克鲁斯卡尔算法中的核心思想就是逐个在边的集合中找到最小的边，如果满足条件

就将其构造，最后生成一个最小生成树。它首先是一系列的顶点集合，并没有边，然后

我们从邻接矩阵中寻找最小的边，看看它是否和现有的边连接成一个环，如果连接成环，

则舍弃，另外取其它的边。如果不连接成环，则接受这个边，并把其纳入集合中。

5.2体会：

（1）通过求最小生成树，进一步掌握了图的含义，掌握了克鲁斯卡尔算法的基

本思想及流程。知道了克鲁斯卡尔算法与普里姆算法的区别与联系。通过本次课程设计，

锻炼了我们的实际操作能力，培养了我们严密的思维和严谨的态度。

（2）在编程序过程中虽然遇到了很多问题，但也使我学到了很多东西，在编制程序过

程中我学到了在编程的开始需要总体设计一下自己的程序需要哪些大的模块，并想好所

.

要用到的知识计算法，在编程过程中，特别是要画图时需要找出坐标，并研究各坐标各

结点之间连线的规律，通过几句判断语句来实现多条连线问题，在编程过好还要反复调

试程序，找出其中的漏洞并加以改正，在此次编程过程中就存在这样的问题，在经过反

复修改后，终于可将漏洞扫除，正确的输出结果。

6.致谢

在编著过程中，感谢那些帮助我的同学，有了他们，我的课程设计才能顺利进行下去。

感谢同学在我的设计过程中提出的宝贵意见，如果没有他们的帮助，我在设计过程

中出现的一些错误可能无法迅速查出解决，他们的帮助为我节省了宝贵的时间。

衷心感谢！

7.参考文献

[1]李素若.《数据结构》.北京：化学工业出版社，2009.

[2]严蔚敏，吴伟民.数据结构(C语言版)[M].北京：清华大学出版社,2007

[3]谭浩强.C程序设计(第三版).北京:清华大学出版社,2005

[4]任正云.C语言程序设计.北京:中国水利水电出版社,2009

[5]徐翠霞崔玲玲.《数据结构》.北京：中国电力出版社：2006.