习题五参考答案.doc

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: 入度2 出度2 B: 入度3 出度1 C：入度1出度2 D:入度2 出度1 E:入度1 出度3 总计 入度9 ；出度9 a b c d e a 0 1 0 1 0 b 1 0 0 0 0 c 0 1 0 1 0 d 0 0 0 0 1 e 1 1 1 0 0 从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网: 图中顶点表示活动，有向边表示活动之间的优先关系，这样的有向图称为顶点表示活动的网(Activity On Vertex Network ，AOV网) 。 有向图的拓扑排序：构造AOV网中顶点的一个拓扑线性序列(v’1,v’2, ?,v’n)，使得该线性序列不仅保持原来有向图中顶点之间的优先关系，而且对原图中没有优先关系的顶点之间也建立一种(人为的)优先关系。 算法思想: ① 在AOV网中选择一个没有前驱的顶点且输出； ② 在AOV网中删除该顶点以及从该顶点出发的(以该顶点为尾的弧)所有有向弧(边) ； ③ 重复①、②，直到图中全部顶点都已输出(图中无环)或图中不存在无前驱的顶点(图中必有环)。 V0-v1,v0-v2 V1-v3,v1-v4,v1-v5 V2-v4,v2-v6 V4-v6 V5-v6 入度为零,可画图 V0-v1-v3-v5-v2-v4-v6 4. 假设一个工程的进度计划用AOE网表示，如图7-33所示。 ① 求出每个事件的最早发生时间和最晚发生时间。 ② 该工程完工至少需要多少时间? ③ 求出所有关键路径和关键活动。 相关知识： 与AOV网相对应的是AOE(Activity On Edge) ，是边表示活动的有向无环图，图中顶点表示事件(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为止。 或者采用以下方式： 终点 i=1 i=2 i=3 i=4 i=5 v1 ∞ 30 (v4,v2,v1) 30 (v4,v2,v1) v2 20 (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) v6 15 (v4,v6) vj V6 V2 V1 V3 V5 S {v4,v6} {v4,v6,v2} {v4,v6,v2,v1} {v4,v6,v2,v1,v3} {v4,v6,v2,v1,v3,v5} 6. 已知带权有向图如图7-30所示，请利用弗洛伊德(Floyd)算法求出每对顶点之间