最新习题五资料

1、1. 设一有向图 G=(V,E,其中 V=a,b,c,d,e , E=va,b, va,d, vb,a, vc,b, vc,d, vd,e,ve,a.ve,b, ve,c 请画出该有向图，并求各顶点的入度和出度。 分别画出有向图的正邻接链表和逆邻接链表。 写出相应的邻接矩阵表示。 写出从顶点a开始的深度优先和广度优先遍历序列。 画出从顶点a开始的深度优先和广度优先生成树。A：入度2出度2B：入度3出度1C:入度1出度2D:入度2出度1E入度1出度3 总计入度9 ;出度9a!-T3 I -Hi |a4|A|10 A(h) G的止邻接链表(b) G的逆邻接琏表a b c d ea01001从a点开

2、始深度优先序列a-b-d-e-cbcde10 10000010 100001110 0广度优先遍历序列：a-b-d-e-c(a)深度优先生成树(b)广度优先生成树2. 对于图7-27所示的带权无向图。 按照Prime算法给出从顶点 2开始构造最小生成树的过程。 按照Kruskal算法给出最小生成树的过程。图了-盘*?厝权尢向图若从顶点2洌发构造U=2t TE=； 先找权值晟小的边(5 v,其中uWU且 vE V-U, 井且子罔不构成砰*则U = UUv, TE=TEU(u, v *(3慎豆” fLfijU=V止.则TE中必有C 条边.T=(U, T巳就能最小生成树“CD(I)选取权值最小的边(

3、v“ Vj), 若边 Vj加入到TE后形成回路 则舍弃该边(边vjh否罠山 将该边并入到TE中，即TE=TEU(Vj. Vj)-重复，直到TE中包含有rv图7-27带权无向时C3. 一个AOV网用邻接矩阵表示，如图7-31。用拓扑排序求该 AOV网的一个拓扑序列，给出相应的步骤。(提示：先根据邻接矩阵画出有向图，然后写出可能的一个拓扑序列 )Vo011Vi000v2000V.000000v5000V；000 0 0 011100 10 1()0000 0 0 10 0 0 I0 0 0 0图7T1 个AOV网的邻接矩阵相关知识：AOV网：图中顶点表示活动， 有向边表示活动之间的优先关系，这样的

4、有向图称为顶点表示活动的网(Activity On Vertex Network ，AOV 网)。?有向图的拓扑排序：构造AOV网中顶点的一个拓扑线性序列(v；,v2, ? ,v,使得该线性序列不仅保持原来有向图中顶点之间的优先关系，而且对原图中没有优先关系 的顶点之间也建立一种(人为的)优先关系。算法思想： 在AOV网中选择一个没有前驱的顶点且输出； 在AOV网中删除该顶点以及从该顶点出发的（以该顶点为尾的弧）所有有向弧（边）； 重复、，直到图中全部顶点都已输出（图中无环）或图中不存在无前驱的顶点（图中必有环）。V0-v1,v0-v2V1-v3,v1-v4,v1-v5V2-v4,v2-v6V

5、4-v6V5-v6入度为零，可画图V0-v1-v3-v5-v2-v4-v64. 假设一个工程的进度计划用 AOE网表示，如图7-33所示。 求出每个事件的最早发生时间和最晚发生时间。 该工程完工至少需要多少时间？ 求出所有关键路径和关键活动。相关知识:与AOV网相对应的是 AOE(Activity On Edge)，是边表示活动的有向无环图，图中顶点表示 事件(Event),每个事件表示在其前的所有活动已经完成，其后的活动可以开始；弧表示活 动，弧上的权值表示相应活动所需的时间或费用。顶点ViV4V5Nve(ij匚161821pi23252830W(i)6tsd6佃2226IT26183(Fa

6、1a3a5a6a?a9a10a 11313时园直i0566151821rii-23K2B10015619d23222226232S关犍路径；V0-v2-v3-v6-v8-v9关键活动型困4嗣聞2月145. 已知带权有向图如图 7-29所示，请利用迪杰斯特拉 （Djkstra）算法从顶点 V出发到其余 顶点的最短路径及长度，给出相应的求解步骤。图7-29带权有向图 令S=Vs，用带权的邻接矩阵表示有向图，对图中每个顶点 Vi按以下原则置初值: 选择一个顶点 Vj ,使得：distj=Min distk| V k V-S Vj就是求得的下一条最短路径终点，将Vj并入到S中，即S=SU Vj o对V

7、-S中的每个顶点 Vk，修改distk，方法是：若 distj+Wjkdistk，则修改为:distk=distj+Wjk( Vk V-S ) 重复，直到 S=V为止。或者采用以下方式:终占八、i=1i=2i=3i=4i=5v1oo30(v4,v2,v1)30 (v4,v2,v1)v220(v4,v2)20(v4,v2)v3oooo45(v4,v2,v1,v3)45(v4,v2,v1,v3)v5oo50(v4,v2,v5)50(v4,v2,v5)50(v4,v2,v5)50(v4,v2,v5)v615(v4,v6)vjV6V2V1V3V5Sv4,v6v4,v6,v2v4,v6,v2,v1v4,v6,v2,v1,v3v4,v6,v2,v1,v3,v56.已知带权有向图如图7-30所示，请利用弗洛伊德（Floyd）算法求出每对顶点之间的最短路径及路径长度。07-30带权有向图abcd|efaoo535acd8ace9abfb13bfeao16beac