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

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

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

2、求边稠密的图的最小生成树。2.给出Prim算法的正确性证明。正确性证明：设由算法生成的MST为T1，假设存在T2，为与T1具有相同边数最多的实际MST，则w(T1)>=w(T2)。假定e2=xy为在T2中且不在T1中的且具有最小权值的边。记在T1中，从根结点A到x的路径为Px1x2…xs(x1=A,xs=x)，从A到的y路径为Py1y2…yt(y1=A,yt=y)。不妨假定在算法执行过程A先到达x，再到达y。因为y是通过yt-1yt进入的T1，所以w(yt-1yt)<=w(xy),否则xy先进入T1。设在路径Px1x2…xs和

3、Py1y2…yt上且不在T2中权值最小的边e1，将e1加入T2中构成回路。在回路中找一条在T2中但不在T1中的边e3删除之，得T2’若:(1)w(e1)w(e3),因为w(e1)<=w(yt-1yt)<=w(xy),所以w(e3)

4、正确的.Prim算法正确性证明数学归纳法：当n=1时，显然成立。假设n=k时，用prim算法构建的是最小生成树。当n=k+1时，设最后加入最小生成树的点是v。在这个n+1个结点的树中任意添加一条边。分两种情况。1.添加的这条边中任意一个顶点都不是v。相当于在去掉了结点v的又k个结点的生成树中添加一条边，根据MST性质，这条边一定是产生回路中权值最大的边。再添加上顶点v，依旧是之前的回路，所以添加的边依旧是现在回路中最长的边。所以当n=k+1时成立2..现在只需要证明，当添加的边其中有一个顶点是v的情形成立即可。假设其余k个结点

5、为uk（k=1,2,3….)其中W(U1v)最小。任意连接Uk(k=2,3…..),一定会出现一条回路。因为采用的是Prim算法，切V结点是最后一个加入进来的，因此回路中不存在大于W(U1V）或者大于W(UkV)的边，并且W(UkV)>W(U1V）,所以加入的UkV是回路中权值最大的边，符合MST性质，因此，这种情形下，n=k+1成立综上所述，prim算法正确。3..写出一个怎样找到一个图中的割点的算法描述。由于上述算法是一个遍历的过程，因此求关键点的事假复杂度为O(n+e).4.n个节点的二叉树有多少棵？给出证明。可以分析，

6、当n=1时，只有1个根节点，则只能组成1种形态的二叉树，令n个节点可组成的二叉树数量表示为h(n)，则h(1)=1;h(0)=1;       当n=2时，1个根节点固定，还有2-1个节点。这一个节点可以分成（1,0），（0,1）两组。即左边放1个，右边放0个；或者左边放0个，右边放1个。即：h(2)=h(0)*h(1)+h(1)*h(0)=2，则能组成2种形态的二叉树。      当n=3时，1个根节点固定，还有2个节点。这2个节点可以分成（2,0），（1,1），（0,2）3组。即h(3)=h(0)*h(2)+h(1)*h(

7、1)+h(2)*h(0)=5，则能组成5种形态的二叉树。 以此类推，当n>=2时，可组成的二叉树数量为h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0)种，即符合Catalan数的定义，可直接利用通项公式得出结果。 令h(1)＝1,h(0)=1，catalan数（卡特兰数）满足递归式：　　h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)h(0)(其中n>=2)　　该递推关系的解为：h(n)=C(2n,n)/(n+1)(n=1,2,3,...)5.给出利用DFS

8、进行拓扑排序算法描述，并给出时间复杂度分析把图中节点的状态分成三种。white代表节点还未被搜索到，gray代表节点已被搜索到但还未被处理完，black代表节点已被处理完。数组topo[]来记录每个顶点的编号。把图中所有的节点的状态初始化为white，topoNum=n，从顶