大连理工大学算法分析与设计算法

《大连理工大学算法分析与设计算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1.写出Prim算法描述，并给出时间复杂度的分析。算法描述：假设N=(V,E),TE是N最小生成树边的集合。算法从U={uO}(uOEV),TE={}开始，重复执行下述操作：在所有uGV,veV-U的边(u,v)GE中，找一条代价最小的边(uO,vO)并入集合TE,同时vO并入U,直到U=V为止。此时TE中必有n・l条边,则T=(V,TE)为最小生成树吋间复杂度：算有2个内循环，其一是选择具有最小代价的边，频度为ml;其二是重新选择最小代价的边，频度为n,因此prim算法的时间复杂度为O(n2).与图中的边数无关，因此适合于求边稠密的图的最

2、力电成树。2.给出Prim算法的正确性证明。正确性证明：设由算法生成的MST为T1,假设存在T2,为与T1具冇相同边数最多的实际MST,则w(Tl)>=w(T2)o假定e2=xy为在T2中且不在T1中的且具有最小权值的边。记在T1中，从根结点A到x的路径为Pxlx2---xs(xl=A,xs=x),从A到的y路径为Pyly2---yt(yl=A,yt=y)o不妨假定在算法执行过程A先到达x,再到达y。因为y是通过yt-lyt进入的T1,所以w(yt-lyt)<=w(xy)/?f则xy先进入T2。设在路径Pxlx2---xs和Pyly2---

3、yt上且不在T2中权值最小的边el,将el加入T2中构成回路。在回路中找一条在T2中但不在T1中的边e3删除Z,得T2'若:⑴w(el)vw(e3),则w(T2')vw(T2),与是T2一条最小生成树矛盾；(2)w(el)=w(e3),T2,与T2具有相同边数比T2与Tl具有相同边数多1,与T2是与T1具有相同边数最多的假定矛盾；(3)w(el)>w(e3),因为w(el)<=w(yt-lyt)<=w(xy),所以w(e3)

4、数学归纳法：当21时，显然成立。假设n二k吋，用prim算法构建的是最小生成树。当zk+l时，设最后加入最小生成树的点是V。在这个n+1个结点的树中任意添加一条边。分两种情况。1•添加的这条边屮任意一个顶点都不是V。和当于在去掉了结点v的又k个结点的生成树屮添加一条边，根据MST性质，这条边一定是产生回路中权值最大的边。再添加上顶点v,依IH是Z前的回路，所以添加的边依IH是现在回路中最长的边。所以当n=k+l吋成立2•.现在只需要证明，当添加的边其中有一个顶点是v的情形成立即可。假设其余k个结点为uk(k=123・・・.)具中W(Ulv)

5、最小。任意连接Uk(k=2,3-..)-*定会出现-条回路。因为采用的是Prim算法，切V结点是最后一个加入进来的，因此回路中不存在大于W(U1V)或者大于W(UkV)的边，并AW(UkV)>W(UlV)，所以加入的UkV是回路中权值最大的边，符合MST性质，因此,这种情形下,n二k+l成立综上所述，prim算法正确。3..写出一个怎样找到一个图中的割点的算法描述。图7.19连通图G(FK)I(E图7.20G的深度优先生成树(1)若生成树的根有两棵或两棵以上的子树，则此根顶点必为关节点。因为图中不存在联结不同子树中顶点的边，因此，若删去根顶

6、点，生成树便变成生成森林。如图7.20中的顶点A。(2)若生成树中某个非叶子顶点“其某棵子树的根和子树中的其他结点均没有指向。的祖先的回边，则。为关节点。因为,若删去s则其子树和图的其他部分被分割开来。如图7.20中的顶点B、D和G。若对图Graph=(VjEdge})f新定义遍历时的访问函数visited,并引入一个新的函数low,则由一次深度优先搜索遍历便可求得连通图中存在的所有关节点。定义visited[v]为深度优先搜索遍历连通图时访问顶点v的次序号;定义low(v)=Min

7、W是顶点V在深度优先生成树上的孩子结点,k是顶点v在深度优先生成树上由回边联结的祖先结点；(v,w)GEdge,(v,k)€Edge,若对于某个顶点s存在孩子结点s且low[w]上visited[v],则该顶点。必为关节点。因为当3是匕的孩子结点时,low[w]$visited[v]^明s及其子孙均无指向卫的祖先的回边。由于上述算法是一个遍历的过程，因此求关键点的爭假复杂度为O(n+e).4.n个节点的二叉树冇多少棵？给出证明。可以分析，当n=1Ht,只有1个根节点，则只能组成1种形态的二叉树，令n个节点nJ组成的二叉树数量表示为h(n),

8、则h(l)=l;h(0)=l;当n=2时，1个根节点固定，还冇24个节点。这一个节点可以分成(1,0),(0,1)两组。即左边放1个,右边放0个;或者左边放0个,右边放1个。即: