计算机算法资料课件

第二章 图与遍历算法基本概念和术语 二叉树与遍历算法 双连通与网络可靠性 对策树 图的基本概念和术语图是一个用（边）连结节点（顶点）的结构.三元素：顶点集、边集、关联关系 G=(V,E,I)术语：顶点与边关联、边的端点、顶点的度、简单图、完全图、偶图、k-部图、途径、迹、路、圈、连通Euler公式：哥尼斯堡七桥 Euler图图的邻接矩阵和关联矩阵图的邻接矩阵和关联矩阵图G=(V,E,I),邻接矩阵 关联矩阵 右边的图不是连通的，有两个连通分支。它含有两个圈，不是树。有7个顶点和7条边的图 上图的邻接矩阵与关联矩阵e5e6e7e46457e11e2e332树的性质树的性质定义定义 不含圈的连通图称为树树。对于连通图，适当去掉一些边后，会得到一个不含圈、而且包含所有顶点的连通图，它是一棵树，称为原图的生成树生成树。森林是由若干棵树构成的图。定理定理 如果G是具有n个顶点、m条边的图，则下列结论立：1.若G是树，则m=n-1；2.若G是连通图，而且满足m=n-1，则G是树；3.若G不包含圈，而且满足m=n-1，则G是树；4.若G是连通图，则m n-1;5.若G是由k棵树构成的森林，则m=n-k；6.若G有k个连通分支，而且满足m=n-k，则G是森林;7.若G有k个连通分支，则m n-k。有向图有向图有向图 ;有向边 ;出(入)度 ();Euler 公式有向途径、有向迹、有向路，有向圈，双向连通（强连通）邻接矩阵 关联矩阵 234561e1e2e3e4e5e6e7e8赋权图赋权图是将图的每个边都赋予一个权值，表示成本、效益值、容量、流量等。赋权图的邻接矩阵的 -元素为连结顶点 ，的权值。当顶点 ，没有边连结时，可根据问题需要，取 或 等。一个赋权图 上图的一个最优生成树2623166263723136831243567图的邻接链表 1234(a)(b)0 1 0 10 0 1 00 0 0 00 1 1 012341 2 3 4987652 4 0 Vertex 13 0 Vertex 2Vertex 3 Empty list2 3 0 Vertex 4(c)(d)VerticesEdges 5 7 0 8 2 6 4 0 3 0 2 9 3 0HEAD NEXT123456789图的遍历算法有根树如果指定树的一个顶点为根根，则这棵树称为有根树。在有根树中，邻接根的顶点称为根的儿子，而根称为这些儿子的父亲。递归地，对于不是根的顶点，除了它的父亲之外其它与之邻接的顶点都称为该顶点的儿子，该顶点也自然称为它的这些儿子的父亲。没有儿子的顶点称为叶顶点叶顶点。从根到每一个叶顶点都有一条唯一的路，这些路的最长者的长度称为该树的高度树的高度；顶点的高度是以它为根的子树的高度；顶点的深度深度是从根顶点到它的路的长度。深度相同的顶点称为同层的。有根树中，一个顶点的深度与高度的和不超过整个树的高度二叉树二叉树二叉树：每个顶点至多有两个儿子的有根树。完整二叉树：完整二叉树：叶顶点深度都相同，而且除了叶顶点以外，每个顶点都恰有两个儿子的二叉树。高度为 的完整二叉树恰有 个顶点，它的所有顶点按照从上到下、从左到右的顺序可以编号为 。完全二叉树：完全二叉树：从这样编号的完整二叉树中的某一位置开始，删掉后面编号的所有顶点及与之关联的边所得到的二叉树。一棵完整的二叉树JABCDEFGHIKMONLABCDEFGHI从一棵高为h-1的 完 整二叉树中删掉标号为2h-i，1ik的k个顶点一棵全二叉树有向树一棵有向树是满足下述条件的无圈有向图：1.有一个称为根的顶点，它不是任何有向边的头；2.除了根以外，其余每个顶点的入度均为1；3.从根到每个顶点有一条有向路。CDGAEFIHKB图 2-2-4 有向树二叉树的搜索：先根、中根、后根二叉树的中根次序遍历算法 InOder(T)/T是一棵二叉树，/T的每个顶点有三个信息 /段：Lson,Data,Rson if T0 then InOrder(Lson(T);Visit(T);InOrder(Rson(T);endifendInOrder BFDGECHIA124387659二叉树的中根次序遍历算法一般树上的搜索 BFDGECHIA154296738二叉树的后根次序遍历算法BFDGECHIANMKJL1234567891011131214树的先根次序遍历算法图的宽度优先搜索算法proc BFS(v)/宽度优先搜索G，从顶点v开始执行，数组Visited标记各 /顶点被访问的次序，其分量已经初始化为0。计数器count已经初始 /化为0。1.AddQ(v,Q)；/将Q初始化为只含有一个元素v的队列2.count:=count+1;Visited(v):=count;3.while Q非空 do4.u:=DelHead(Q);5.for 邻接于u的所有顶点w do6.if Visited(w)=0 then 7.AddQ(w,Q);/将w放于队列Q之尾8.count:=count+1;9.Visited(w):=count;10.endif11.endfor12.endwhile13.endBFSET:=;ET:=ET union (u,w);EGFCADBH B C 0 A D E 0 D E F G 0 A F G 0 C H 0 B H 0 B H 0 C H 0ABCDEFGH图G和它的邻接链表EGFCADBH56374218图G的宽度优先搜索树EGFCADBH56783214图G的深度优先搜索树图的深度优先搜索proc DFS(v)/访问由v到达的所有顶点,计数器count已经初 /始化为1；数组Visited标示各顶点被访问的次序，其元 /素已经初始化为0。1.Visited(v):=count;2.for邻接于v的每个顶点w do3 if Visited(w)=0 then4.count:=count+1;5.DFS(w);6.endif7.endfor 8endDFS ET:=ET union (u,w);ET初始化为空集。算法BFS的复杂性分析空间复杂度为 ；时间复杂度，当G用邻接矩阵表示时：；当G由邻接链表表示时，。除结点v外，只有当结点w满足Visited(w)=0时才被加到队列上，然后，Visited(w)的值马上被修改增加1.因此每个结点有一次机会被放到队列上。需要的队列空间至多是n-1，其余变量所用的空间为O(1)，S(n,m)=O(n)。在极端情况下，v邻接于全部其他n-1个结点，此时队列需要n-1的空间。又Visited需要(n)的空间，所以S(n,m)=(n)。如果使用邻接链表，语句4的for循环要做d(u)次，而语句311的while循环需要做n次，因而整个循环做d(u)=2m次O(1)操作，又Visited的赋值需要n次操作，因而T(n,m)=(n+m)。如果采用邻接矩阵，则语句312的while循环总共需要做n2次O(1)操作，Visited赋值需要n操作，因而T(n,m)=(n2)。2-连通与网络可靠性定义定义 连通图G中的顶点v称为割点，如果在G中去掉v及其关联的边，剩下的图就不再连通。没有割点的连通图称为2-连通的（也称为块）。图G中极大的2-连通子图称为G的一个2-连通分支。ABFCDCGIJFHGEC 右下图的5个2-连通分支AEGBCDFABFEGDCIgHJ2-连通化添加边的算法E1：for每个割点u doE2：设B1，B2，Bk，是包含割点u的全部2-连通分支；E3：设 Vi是Bi的一个顶点，且Viu，1ik。E4：将边(Vi,Vi+1)添加到G，1ik-1。E5：endfor ABFEGDCIgHJ图G 添加边使成为2-连通图问题：设计算法测试一个连通图是否2-连 通；若不是，算法将识别出割点。采用深度优先算法得到深度优先搜索树,并且给每个顶点赋值深索数 DFN(v)。182a76cd934510b假定图的邻接链表是按照顺时针方向的顺序构造的a,b,c,d是图G关于这棵生 成 树 的余边边ABFEGDCIHJ图G及其深度优先生成树T分析割点特征1关于深度优先生成树T，图G的每一条边(u,v)的两个端点u、v之间，或u是v的祖先，或v是u的祖先，即不是平辈关系。2树T的根是图G的割点当且仅当其在T中至少有两儿子；3.既不是根也不是叶的顶点u不是G的割点当且仅当u在T中的每个儿子w都至少有一个子孙（或w本身）关联着一条余边e，e的另一个端点是u的某个祖先；4叶顶点不能是割点。根据性质1，3，4，深度优先生成树T的非根顶点u是G的割点当且仅当u至少有一个儿子w，w及其子孙都不与u的任何祖先相邻。1235476988d1abc64511616ABFEGDCIgHJ10深度优先树的分层最低深索数 L(u)L(u):=min DFN(u),minL(w)|w是u的儿子，minDFN(x)|(u,x)是T的余边结论：如果u不是深度优先生成树的根，则u是图G的割点当且仅当u有某个儿子w，w的最低深索数不小于u的深索数，即 L(w)DFN(u),对u的某个儿子w成立。求法：采用深度优先搜索结合递归算法，逐层深入确定各点的深索数和最低深索数。红色数字表示最低深索数8d1abc64511616ABFEGDCIgHJ10123547698计算DFN和L的算法伪代码DFNL(u,v)/一个深度优先搜索算法，u是开始顶点。在深度 /优先搜索树中，若u有父亲，则v即是。数组DFN初始化 /为0，变量num初始化为1，n是图G的顶点数。global DFNn，Ln，num，n 1.DFN(u):=num;L(u):=num;num:=num+1;2.for 每个邻接于u的顶点w do 3.if DFN(w)=0 then 4.DFNL(w,u);/还未访问w 5.L(u):=min(L(u),L(w);6.else 7.if wv then L(u):=min(L(u),DFN(w);endif 8.endif 9.endfor10.endDFNL给出图G的各个2-连通分支 引进一个存放边的全程栈引进一个存放边的全程栈S；在在2到到3行之间加下列语句行之间加下列语句：2.1 if wv and DFN(w)DFN(u)then 2.2 将(u,w)加到S的顶部；2.3 endif在在4到到5行之间加下列语句行之间加下列语句：4.1 if L(w)DFN(u)then 4.2 print（new biconnected component）;4.3 loop 4.4 从栈S的顶部删去一条边；4.5 设这条边是(x,y)4.6 print(“(”，x，“，”，y，“)”)；4.7 until(x,y)=(u,w)or(x,y)=(w,u)；4.8 endif 对 策 树取火柴游戏：规则：规则：两人轮流从盘子上取走1，2或3支火柴为合法步骤；评判：评判：拿走盘中最后一支火柴者为负。对弈棋局：以盘中剩下的火柴数来表示该时刻的棋局。棋局序列C0，C1，Ck-1,Ck称为有效序列，如果：1.C0是开始棋局；2.Ci不是终止棋局，i0,1，2，k-1；3.由Ci走到Ci+1是按下述规则进行的：若i是偶数，则A走一合法步骤；若i是奇数，则B走一合法步骤。4.以Ck为终局.一个有效棋局序列C0，C1，Ck是此游戏的一盘战例.取火柴游戏所有可能的战例X:节点，代表一种棋局，V(X)表示该局下奕者A的胜负估计。奕者A 走子奕者B 走子/A/BBBB/BB/B/A/A/AA/AAAAAAA/BBBBB1-1-1111-1-1-11-1-1-1-1 1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-11111111111111111111111123各种棋局下奕者胜算估值奕者奕者A,B,A,B,站在站在A A的角度估计棋局的角度估计棋局X X下，奕者下，奕者A A的胜率的胜率代表棋局的顶点X是对策树的叶顶点时的胜率 代表棋局的顶点X不是对策树的叶顶点时的胜率计算 为了不要总是区别A走棋还B走棋，用V(X)替换V(X)若X是A走棋的位置，则e(X)=E(X);若是B走棋，则e(X)=-E(X)对策树的后根次序求值算法VE(X,)/通过至多向前看 着棋计算V(X)，弈者A的估价函 /数是e(X)。假定由任一不是终局的棋局X开始，此棋局的 /合法棋着只允许将棋局X转换成棋局X1，X2，Xd.if X是终局或 =0 then return(e(X)endif ans:=-VE(X1，-1)；/遍历第一棵子树 for i from 2 to d do ans:=max(ans,-VE(Xi，-1)；endfor return(ans);endVE A的最优棋着奕者A走子奕者B走子maxminmaxmine(x)maxP1132-3 0323-3+-1+3-33159272-305110P41P42P43P45P51P52P53P54P55P56P57P58P59P5,10P5,11P31P33P34P21P22P23P44P32P35P36P37P24A胜A胜A负A负A负一盘假想博弈游戏的部分对策树一盘假想博弈游戏的部分对策树 截断规则设Y是X的父亲，X有儿子 X1，X2，Xd，则一旦知道 V(Xk)，就不必再计算以 Xk+1，Xd为根的子树的顶点的价值。其中，是当前所知道的V(Y)的最大可能值:使用截断规则的后根次序求值算法使用截断规则的后根次序求值算法 VEB(X,D)/通过至多向前看 着棋，使用 /截断规则和公式计算V(X)，弈者A的 /估价函数e(X)假定由任一不是终局的棋局 /X开始，此棋局的合法棋着只允许将棋局 /X转换成棋局X1,X2,Xd if X是终局或 =0 then return(e(X)endif ans:=-VEB(X1,-1,)；for i from 2 to d do /使用截断规则 if ans D then return(ans)endif ans:=max(ans,-VEB(Xi，-1，-ans)；endfor return(ans);endVEB 截断算法AB(X，LB，D)/LB是V(X)的一个下界。/通过至多向前看 着棋，使用截断规则计算 /V(X),弈者A的估价函数是e(X)。假定由 /任一不是终局的棋局X开始，此棋局的 /合法棋着只允许将棋局X转换成棋局 /X1，X2，Xd.if X是终局或=0 then return(e(X)endif ans:=LB；for i from 1 to d do /使用截断规则 if ans D then return（ans）endif ans:=max(ans,-AB(Xi，-1,-D,-ans)；endfor return(ans);endAB 比较VEB和AB的执行情况 P1 10-10-99xP3P2P4P5P6上面是一棵假想的对策树，对图这棵对策树调用算法VEB(P1,l,)和调用算法AB(P1,l,-，)实际需要计算价值的结点数是不一样的。使用算法VEB需要计算V(P7)，但使用算法AB时不必。因为，当我们知道V(P2)=-10后，就知道10是V(P1)至少是10，因而知道了10是V(P4)的一个下界，进而知道10也是V(P6)的下界。但是V(P6)=910，所以计算V(P5)的进程停止，即不需计算V(P7).人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。