1、1. 设一有向图 G=(V,E)，其中 V=a,b,c,d,e ， E=, , , , , , , 请画出该有向图，并求各顶点的入度和出度。 分别画出有向图的正邻接链表和逆邻接链表。 写出相应的邻接矩阵表示。 写出从顶点 a 开始的深度优先和广度优先遍历序列。 画出从顶点 a 开始的深度优先和广度优先生成树。A: 入度 2 出度 2B: 入度 3 出度 1C：入度 1 出度 2D:入度 2 出度 1E:入度 1 出度 3总计 入度 9 ；出度 9a b c d e a 0 1 0 1 0b 1 0 0 0 0c 0 1 0 1 0d 0 0 0 0 1e 1 1 1 0 0从 a 点开始深度优
2、先序列 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 Netw
3、ork ，AOV 网) 。 有向图的拓扑排序：构造 AOV 网中顶点的一个拓扑线性序列(v 1,v2, ,vn)，使得该线性序列不仅保持原来有向图中顶点之间的优先关系，而且对原图中没有优先关系的顶点之间也建立一种( 人为的) 优先关系。算法思想: 在 AOV 网中选择一个没有前驱的顶点且输出； 在 AOV 网中删除该顶点以及从该顶点出发的(以该顶点为尾的弧)所有有向弧(边) ； 重复、，直到图中全部顶点都已输出(图中无环) 或图中不存在无前驱的顶点(图中必有环)。V0-v1,v0-v2V1-v3,v1-v4,v1-v5V2-v4,v2-v6V4-v6V5-v6入度为零,可画图 V0-v1-v3
4、-v5-v2-v4-v64. 假设一个工程的进度计划用 AOE 网表示，如图 7-33 所示。 求出每个事件的最早发生时间和最晚发生时间。 该工程完工至少需要多少时间? 求出所有关键路径和关键活动。相关知识：与 AOV 网相对应的是 AOE(Activity On Edge) ，是边表示活动的有向无环图，图中顶点表示事件(Event)，每个事件表示在其前的所有活动已经完成，其后的活动可以开始；弧表示活动，弧上的权值表示相应活动所需的时间或费用。5. 已知带权有向图如图 7-29 所示，请利用迪杰斯特拉(Dijkstra) 算法从顶点 V4 出发到其余顶点的最短路径及长度，给出相应的求解步骤。
5、令 S=Vs ，用带权的邻接矩阵表示有向图，对图中每个顶点 Vi 按以下原则置初值： 选择一个顶点 Vj ，使得：distj=Min distk| VkV-S Vj 就是求得的下一条最短路径终点，将 Vj 并入到 S 中，即 S=SV j 。 对 V-S 中的每个顶点 Vk ，修改 distk，方法是：若 distj+Wjkdistk，则修改为：distk=distj+Wjk (VkV-S ) 重复，直到 S=V 为止。顶 点步 骤 12356S 路 径初态 Distpre020000150v41Distpre3022000502150v4, v6 V4,v62Distpre302200050
6、2150v4, v6,v2V4,v23Distpre302200451502150v4, v6,v2,v1 V4,v2,v14Distpre302200451502150v4, v6,v2, v1,v3 V4,v2,v1,v35Distpre302200451502150v4, v6,v2, v1,v5 V4,v2,v5或者采用以下方式：终点 i=1 i=2 i=3 i=4 i=5v1 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 (
7、v4,v2,v5)50 (v4,v2,v5)50 (v4,v2,v5)v6 15 (v4,v6)vj V6 V2 V1 V3 V5S v4,v6 v4,v6,v2 v4,v6,v2,v1 v4,v6,v2,v1,v3 v4,v6,v2,v1,v3,v56. 已知带权有向图如图 7-30 所示，请利用弗洛伊德(Floyd)算法求出每对顶点之间的最短路径及路径长度。图 7-30 带 权 有 向 图adec fb354 42 3956 5 3 94 2 5 46 3 abcdef邻 接 矩 阵a bc d efa 5 3 5acd8ace9abfb 13bfea16beac18bfeacd7bfe4c 1cea16ceab2 620ceabfd 10dea15deab13deac 419deabfe 6 1eab9eac1eacd15eabff 9fea14feab12feac14feacd3
