您好,欢迎访问三七文档
1.设一有向图G=(V,E),其中V={a,b,c,d,e},E={a,b,a,d,b,a,c,b,c,d,d,e,e,a,e,b,e,c}①请画出该有向图,并求各顶点的入度和出度。②分别画出有向图的正邻接链表和逆邻接链表。③写出相应的邻接矩阵表示。④写出从顶点a开始的深度优先和广度优先遍历序列。⑤画出从顶点a开始的深度优先和广度优先生成树。A:入度2出度2B:入度3出度1C:入度1出度2D:入度2出度1E:入度1出度3总计入度9;出度9abcdea01010b10000c01010d00001e11100从a点开始深度优先序列a-b-d-e-c广度优先遍历序列:a-b-d-e-c(a)深度优先生成树(b)广度优先生成树2.对于图7-27所示的带权无向图。①按照Prime算法给出从顶点2开始构造最小生成树的过程。②按照Kruskal算法给出最小生成树的过程。3.一个AOV网用邻接矩阵表示,如图7-31。用拓扑排序求该AOV网的一个拓扑序列,给出相应的步骤。(提示:先根据邻接矩阵画出有向图,然后写出可能的一个拓扑序列)相关知识:AOV网:图中顶点表示活动,有向边表示活动之间的优先关系,这样的有向图称为顶点表示活动的网(ActivityOnVertexNetwork,AOV网)。•有向图的拓扑排序:构造AOV网中顶点的一个拓扑线性序列(v’1,v’2,⋯,v’n),使得该线性序列不仅保持原来有向图中顶点之间的优先关系,而且对原图中没有优先关系的顶点之间也建立一种(人为的)优先关系。算法思想:①在AOV网中选择一个没有前驱的顶点且输出;②在AOV网中删除该顶点以及从该顶点出发的(以该顶点为尾的弧)所有有向弧(边);③重复①、②,直到图中全部顶点都已输出(图中无环)或图中不存在无前驱的顶点(图中必有环)。V0-v1,v0-v2V1-v3,v1-v4,v1-v5V2-v4,v2-v6V4-v6V5-v6入度为零,可画图V0-v1-v3-v5-v2-v4-v64.假设一个工程的进度计划用AOE网表示,如图7-33所示。①求出每个事件的最早发生时间和最晚发生时间。②该工程完工至少需要多少时间?③求出所有关键路径和关键活动。相关知识:与AOV网相对应的是AOE(ActivityOnEdge),是边表示活动的有向无环图,图中顶点表示事件(Event),每个事件表示在其前的所有活动已经完成,其后的活动可以开始;弧表示活动,弧上的权值表示相应活动所需的时间或费用。5.已知带权有向图如图7-29所示,请利用迪杰斯特拉(Dijkstra)算法从顶点V4出发到其余顶点的最短路径及长度,给出相应的求解步骤。①令S={Vs},用带权的邻接矩阵表示有向图,对图中每个顶点Vi按以下原则置初值:②选择一个顶点Vj,使得:dist[j]=Min{dist[k]|Vk∈V-S}Vj就是求得的下一条最短路径终点,将Vj并入到S中,即S=S∪{Vj}。③对V-S中的每个顶点Vk,修改dist[k],方法是:若dist[j]+Wjkdist[k],则修改为:dist[k]=dist[j]+Wjk(Vk∈V-S)④重复②,③,直到S=V为止。顶点步骤12356S路径初态Distpre∞0200∞0∞0150{v4}1Distpre302200∞0502150{v4,v6}V4,v62Distpre302200∞0502150{v4,v6,v2}V4,v23Distpre302200451502150{v4,v6,v2,v1}V4,v2,v14Distpre302200451502150{v4,v6,v2,v1,v3}V4,v2,v1,v35Distpre302200451502150{v4,v6,v2,v1,v5}V4,v2,v5或者采用以下方式:终点i=1i=2i=3i=4i=5v1∞30(v4,v2,v1)30(v4,v2,v1)v220(v4,v2)20(v4,v2)v3∞∞45(v4,v2,v1,v3)45(v4,v2,v1,v3)v5∞50(v4,v2,v5)50(v4,v2,v5)50(v4,v2,v5)50(v4,v2,v5)v615(v4,v6)vjV6V2V1V3V5S{v4,v6}{v4,v6,v2}{v4,v6,v2,v1}{v4,v6,v2,v1,v3}{v4,v6,v2,v1,v3,v5}6.已知带权有向图如图7-30所示,请利用弗洛伊德(Floyd)算法求出每对顶点之间的最短路径及路径长度。图7-30带权有向图adecfb354423956∞53∞∞∞∞∞∞∞94∞∞∞25∞∞∞∞∞4∞6∞∞∞∞∞∞∞∞∞3∞abcdef邻接矩阵abcdefa∞535acd8ace9abfb13bfea∞16beac18bfeacd7bfe4c11cea16ceab∞2620ceabfd10dea15deab13deac∞419deabfe611eab9eac11eacd∞15eabff9fea14feab12feac14feacd3∞
本文标题:习题五(参考答案)
链接地址:https://www.777doc.com/doc-2733951 .html