文档介绍：一、问题分析和任务定义
在该部分中主要包括两个方面:问题分析和任务定义;
1 问题分析
本次课程设计是通过PRIM(普里姆)算法,实现通过任意给定网和起点,将该网所对应的所有生成树求解出来。
在实现该本设计功能之前,必须弄清以下三个问题:
关于图、网的一些基本概念
图图G由两个集合V和E组成,记为G=(V,E),其中V是顶点的有穷非空集合,E是V中顶点偶对的有穷集,这些顶点偶对称为边。通常,V(G)和E(G)分别表示图G的顶点集合和边集合。E(G)也可以为空集。则图G只有顶点而没有边。
无向图对于一个图G,若边集E(G)为无向边的集合,则称该图为无向图。
子图设有两个图G=(V,E)G’=(V’,),若V’是V的子集,即V’V ,且E’是E的子集,即E’E ,称G’是G的子图。
连通图若图G中任意两个顶点都连通,则称G为连通图。
权和网在一个图中,每条边可以标上具有某种含义的数值,该数值称为该边的权。把边上带权的图称为网。如图1所示。
理解生成树和最小生成树之间的区别和联系
生成树在一个连通图G中,如果取它的全部顶点和一部分边构成一个子图G’,即:V(G’)= V(G)和E(G’)E(G),若边集E(G’)中的边既将图中的所有顶点连通又不形成回路,则称子图G’是原图G的一棵生成树。
最小生成树图的生成树不是唯一的,把具有权最小的生成树称为图G的最小生成树,即生成树中每条边上的权值之和达到最小。如图1所示。
2
6
1
5
2
网
最小生成树
4
1
3
2
6
5
5
2
1
3
4
4
1
3
6
5
6
6
5
5
3
4
小生成树
理解PRIM(普里姆)算法的基本思想
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中的顶点,常称为“加点法”。为了实现这个算法在本设计中需要设置一个辅助数组cl
osedge[ ],以记录从U到V-U具有最小代价的边。当辅助数组中存在两个或两个以上的最小代价的边时,此时最小生成树的形态就不唯一,此时可以在程序中采用递归的算法思想求出每个最小生成树。
在PRIM算法中需要解决的两个问题
①在无向网中,当出现从一个顶点到其它顶点时,若其边上的权值相等,则可能从某一起点出发时会得出不同的最小生成树,但最小生成树的权必定都相等,此时我们应该怎样将所有的最小生成树求解出来;
②每次如何从生成树T中到T外的所有边中,找出一条最短边。例如,在第k次(1≤k≤n-1)前,生成树T中已有k个顶点和k-1条边,此时T中到T外的所有边数为k(n-k),当然它也包括两顶点间没有直接边相联,其权值被看做常量INFINIT的边在内,从如此多的边中查找最短边,其时间复杂度为O(k(n-k)),显然是很费时的,是否有一种好的方法能够降低查找最短边的时间复杂度。
上述问题的解决方法
针对①中出现的问题可以通过在算法中实现,详情请看PRIM算法的基本思想;
针对②中出现的问题,通过对PRIM算法的分析,可以使查找最短边的时间复杂度降低到O(n-k)。具体方法是假定在进行第k次前已经保留着从T中到T外的每一顶点(共n-k个顶点)的各一条最短边,进行第k次时,首先从这n-k条最短边中,找出一条最最短的边,它就是从T中到T外的所有边中的最短边,