淮阴工学院
数据结构课程设计报告
选题名称: 无向图应用问题
系（院）: 计算机工程学院
专 业: 计算机科学与技术
班 级: 网络1111
姓 名: 1111311105
指导教师: 周海岩 单劲松
学年学期: 20## ~ 20## 学年 第 1 学期
2012 年 12 月 20 日
设计任务书
摘要：
本课程设计是设计的关于无向图应用问题的课程。通过此课程，我们可以解决n个城市间设计通信网络，使其造价最低。以及当其造价最低的时候我们应该怎样设计。本课程实际是通过应用Prim算法来求最小生成树。将n个城市和各边的权值建立成邻接矩阵，再应用Prim算法就能完成。
关键词：Prim算法；邻接矩阵；最小生成树；无向图
目 录
1需求分析... 13
1需求分析... 13
1.1课程设计题目·· 13
1.2课程设计任务·· 13
1.3课程设计思想·· 13
2概要设计... 13
2.1本课程设计的总体结构·· 13
3详细设计和实现... 13
3.1源代码·· 13
3.2算法流程图·· 13
3.3模块的功能描述·· 13
3.4算法原理·· 13
3.5程序运行截图·· 13
总 结... 13
致 谢... 13
参 考 文 献... 13
1需求分析
1.1课程设计题目
无向图应用问题
1.2课程设计任务
如果以无向网表示n个城市之间通信网络的建设计划，顶点表示城市，边上的权表示该线路的造价，设计一个方案，使这个通讯网的总造价最低。
1.3课程设计思想
本课程设计主要应用如何生成最小生成树，以及Prim算法。
2概要设计
2.1本课程设计的总体结构
本课程设计的总体结构分为4个部分。
2.1.1第1部分
设定了城市数目为5，并且设定了每条边的权值。
2.1.2第2部分
设计了一个Prim函数。并且通过Prim算法来求最小生成树。而Prim算法的具体实现步骤：
1：初始化：U={u 0},TE={f}。此步骤设立一个只有结点u 0的结点集U和一个空的边集TE作为最小生成树的初始形态，在随后的算法执行中，这个形态会不断的发生变化，直到得到最小生成树为止。
2：在所有u∈U,v∈V－U的边（u,v）∈E中，找一条权最小的边（u 0,v 0），将此边加进集合TE中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边，要求这条边满足以下条件：首先边的两个顶点要分别在顶点集合U和V－U中，其次边的权要最小。找到这条边以后，把这条边放到边集TE中，并把这条边上不在U中的那个顶点加入到U中。这一步骤在算法中应执行多次，每执行一次，集合TE和U都将发生变化，分别增加一条边和一个顶点，因此，TE和U是两个动态的集合，这一点在理解算法时要密切注意。
3：如果U=V，则算法结束；否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当U=V时，步骤2共执行了n－1次（设n为图中顶点的数目），TE中也增加了n－1条边，这n－1条边就是需要求出的最小生成树的边。
2.1.3第3部分
设计了一个creatlist函数。该函数可以用来得出当是最小生成树的时候的排列顺序。
2.1.4第4部分
设计了一个main()函数。该函数用来对整个课程设计进行运行。它调用了Prim算法和creatlist函数。对5个城市的通信网络建立邻接矩阵然后对运用Prim算法，再调用creatlist()函数，将最小生成树时的排列进行输出。
3详细设计和实现
3.1源代码
# include <stdio.h>
# include <iostream>
# define n 5
# define max 1000.0
typedef struct node
{
int no;
float wgt;
struct node *next;
}edgenode;
typedef struct
{
char vtx;
edgenode *link;
}vexnode;
float gali [n][n] = {{0,2,12,10,max},{2,0,8,max,9},{12,8,0,6,3},{10,max,6,0,7},{max,9,3,7,0}};
typedef vexnode Graph[n];
Graph G;
void prim(vexnode G[],int k)
{
int v2link[n], vset[n],parent[n],w[n];
edgenode *ptr ;
int x, s, ecount, i, y, z, f;
s=-1;
x=k;
vset[k]=-1;
v2link[n]=-1;
ecount=0;
for(i=0;i<n;i++)
if(i!=k)
vset[i]=3;
while(ecount<n-1)
{
ptr=G[x].link;
while(ptr!=NULL)
{
y=ptr->no;
if((vset[y]==2)&&(ptr->wgt<w[y]))
{
parent[y]=x;
w[y]=ptr->wgt;
}
if(vset[y]==3)
{
vset[y]=2;
v2link[y]=s;
s=y;
parent[y] = x;
w[y]=ptr->wgt;
}
ptr = ptr->next;
}
if(s==-1)
break;
z=x=s;
y=v2link[x];
f=-1;
while(y!=-1)
{
if(w[y]<w[x])
{
x=y;
f=z;
}
z=y;
y=v2link[y];
}
if(f==-1)
s=v2link[x];
else
v2link[f]=v2link[x];
vset[x]=1;
ecount++;
}
printf("\nroot%c:\t", G[k].vtx);
for(i=0;i<n;i++)
{
if(i!=k)
{
printf("%c",G[i].vtx);
f=parent[i];
printf("%c\t", G[f].vtx);
}
}
}
void creatlist(vexnode ga[])
{
int i,j;
edgenode *se;
for(i=0; i<n; i++)
{
ga[i].vtx='a'+i;
for(j=0;j<n;j++)
{
if((gali[i][j]<max)&&(gali[i][j]!=0))
{
se=(edgenode*)malloc(sizeof(*se));
se->no=j;
se->next=ga[i].link;
se->wgt=gali[i][j];
ga[i].link=se;
}
}
}
}
main()
{
int i;
edgenode *ve;
creatlist(G);
for(i=0;i<n;i++)
{
printf("\n v%c=link:",G[i].vtx);
ve=G[i].link;
while(ve!=NULL)
{
printf("%d w=%.2f\t",ve->no,ve->wgt); ve=ve->next;
}
}
prim(G,4);
return 0;
}
3.2算法流程图
3.3模块的功能描述
Prim算法的功能描述：Prim算法是用来求出最小生成树。
Creatlist()函数的功能描述：creatlist()函数可以将Prim算法求出来的最小生成树进行输出。
Main()函数的功能描述：main()函数是该程序的主函数，它先对Prim算法进行调用，将5个城市及其边的权值进行最小生成树的生成，然后再调用了creatliast()函数，运用creatlist()函数，将Prim算法求出的最小生成树输出。
3.4算法原理
Prim算法的基本思想：假设G =（V，E）是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。算法开始时，首先从V中任取一个顶点（假定取V0），将它并入U中，此时U={V0}，然后只要U是V的真子集，就从那些其一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短（即权值最小）边，假定为（i,j），其中Vi∈U,Vj∈(V-U),并把该边（i,j）和顶点j分别并入T的边集TE和顶点集U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后就把所有n个顶点都并入到生成树T的顶点集中，此时U=V，TE中含有n-1条边，T就是最后得到的最小生成树。可以看出，在普利姆算法中，是采用逐步增加U中的顶点，常称为“加点法”。为了实现这个算法在本设计中需要设置一个辅助数组closedge[ ]，以记录从U到V-U具有最小代价的边。当辅助数组中存在两个或两个以上的最小代价的边时，此时最小生成树的形态就不唯一，此时可以在程序中采用递归的算法思想求出每个最小生成树。
而在Prim算法中需要解决2个问题
①在无向网中，当出现从一个顶点到其它顶点时，若其边上的权值相等，则可能从某一起点出发时会得出不同的最小生成树，但最小生成树的权必定都相等，此时我们应该怎样将所有的最小生成树求解出来； ②每次如何从生成树T中到T外的所有边中，找出一条最短边。例如，在第k次（1≤k≤n-1）前，生成树T中已有k个顶点和k-1条边，此时T中到T外的所有边数为k(n-k)，当然它也包括两顶点间没有直接边相联，其权值被看做常量INFINIT的边在内，从如此多的边中查找最短边，其时间复杂度为O(k(n-k))，显然是很费时的，是否有一种好的方法能够降低查找最短边的时间复杂度。
而针对这2个问题其解决方法如下：
针对①中出现的问题可以通过在算法中实现，详情请看PRIM算法的基本思想；
针对②中出现的问题，通过对PRIM算法的分析，可以使查找最短边的时间复杂度降低到O(n-k)。具体方法是假定在进行第k次前已经保留着从T中到T外的每一顶点（共n-k个顶点）的各一条最短边，进行第k次时，首先从这n-k条最短边中，找出一条最最短的边，它就是从T中到T外的所有边中的最短边，假设为（i,j），此步需进行n-k次比较；然后把边（i,j）和顶点j分别并入T中的边集TE和顶点集U中，此时T外只有n-(k+1)个顶点，对于其中的每个顶点t，若（j,t）边上的权值小于已保留的从原T中到顶点t的最短边的权值，则用（j,t）修改之，使从T中到T外顶点t的最短边为（j,t），否则原有最短边保持不变，这样，就把第k次后从T中到T外每一顶点t的各一条最短边都保留下来了，为进行第k+1次运算做好了准备，此步需进行n-k-1次比较。所以，利用此方法求第k次的最短边共需比较2(n-k)-1次，即时间复杂度为O(n-k)。
3.5程序运行截图
总 结
在这次课程设计中，感觉自己学到了不少知识，以往在上机实验过程中，书上总有相关的代码可以让我们参考，但是在这次课程设计中，是要独立的设计出一个真正的程序，在开始的时候我们使用了上学期C++所学到的关于文本输入输出的程序，但是在和同伴的讨论过程中，发现仅仅只是输入输出流的应用，并没有数据结构中的知识，所以我们就否定了原来的程序，重新做了这个程序，在这个程序中使用了链表存储相关信息，在编写程序中，动手能力得到了很大的提高，同时对链表的知识得到了很大的巩固。在编写过程中，遇到了很多的问题，比如开始的时候算法不正确，后来的编写程序中对程序函数不能正确认识，但是在后来查阅资料和与同伴讨论中，很多的问题都得到了良好的解决。总之，这次的课程设计对我来说是受益匪浅。
对于此次数据结构课程设计来说，我觉的我最大的收获就是学会了如何使用最小生成树以及Prim算法的基本原理及其应用。让我理解了Prim算法是不断迭代进行的。此算法的精妙之处在于对求权值最小的边这一问题的分解（也正是由于这种分解，而导致了算法理解上的困难）。按照常规的思路，这一问题应该这样解决：分别从集合V－U和U中取一顶点，从邻接矩阵中找到这两个顶点行成的边的权值，设V－U中有m个顶点，U中有n个顶点，则需要找到m*n个权值，在这m*n个权值中，再查找权最小的边。循环每执行一次，这一过程都应重复一次，相对来说计算量比较大。而本算法则利用了变量tree中第k+1到第n－1号元素来存放到上一循环为止的一些比较结果，如以第k+1号元素为例，其存放的是集合U中某一顶点到顶点tree.en的边，这条边是到该点的所有边中权值最小的边，所以，求权最小的边这一问题，通过比较第k+1号到第n－1号元素的权的大小就可以解决，每次循环只用比较n－k－2次即可，从而大大减小了计算量。
致 谢
本次课程设计中，我得到了很多来自他方的帮助，在这里我要谢谢所有帮助过我的老师学生。
首先，我要谢谢淮阴工学院计算机工程系提供给实验室给我提供的方便环境！其次，要谢谢这次课程设计的辅导老师周海岩老师给予我的帮助，没有他的悉心指导我也不能这么顺利的完成本次的课程设计，在这里衷心的对他们表示深深的谢意，谢谢！
同时也要感谢学校提供了优越的硬件设备可以让我们能够顺利的完成课程设计。
参 考 文 献
1. 殷人昆．数据结构（用面向对象方法与C++语言描述）（第2版）.清华大学出版社．2007，6
2. 朱金付．c++程序设计.清华大学出版社，2009，7
3. 慧南．结构．C++语言描述.人民邮电出版社，2005
4. 周云静．数据结构习题解析与上机指导．冶金工业出版社，2004
5. 苏仕华．数据结构课程设计．机械工业出版社，2005
李春葆，金晶．数据结构教程．清华大学出版社，2006
课程设计成绩表
