内容发布更新时间 : 2024/10/21 6:05:08星期一 下面是文章的全部内容请认真阅读。

执行深度优先搜索的结果为：V0V1V4V3V6V7V8V2V5，搜索结果不唯一。 3. 以顶点 ① 为根的深度优先生成树（不唯一）：

① ①

② ③ ② ③

④ ④ ⑤

⑤

以顶点 ② 为根的广度优先生成树：

①

② ③

④ ⑤

4. 深度优先生成森林为： 广度优先生成森林为： V

V0 0 VV3

2

V1 V2 V3

V4 V5 V6 V7 V5 V6

应用Kruskal算法顺序选出最小生成树的各条边为：

( 始顶点号，终顶点号， 权值 )

0 ( 0, 3, 1 ) ( 2, 5, 2 ) 1 1 2 ( 1, 4, 3 ) 3 ( 3, 5, 4 )

5 3 4 2 ( 3, 4, 5 ) 4 5

5. 采用prim算法从顶点0开始构造最小生成树的过程：

S: 顶点号 Edge(顶点，顶点，权值) : 0 ( 0， 1， 9 ) 0, 1 ( 1， 3， 5 ) 0, 1, 3 ( 1， 2， 7 ) 0, 1, 3, 2 ( 2， 4， 6 ) 0, 1, 3, 2, 4 ( 2， 5， 7 ) 0, 1, 3, 2, 4, 5 0 9 1 7 2

5 6 7 3 4 5 V1V4 V7

6. 相应的AOV网络为： A1 A2

A4 A3 A0 A7

A5 A6

一个拓扑排序序列为：A0,A1,A4,A2,A5,A3,A6,A7。 注意：拓扑排序结果不唯一。 按拓扑有序的次序对所有顶点从新编号： 原编号 新编号 A0 A0 A1 A1 A4 A2 A2 A3 A5 A4 A3 A5 A6 A6 A7 A7

相应邻接矩阵为：

0?0?0??0?Edge??0?0??0?0???012345671010100?0100000??0001000??0001100?0000001??0000010?0000001??0000000??012 34567

7. 针对下图所示的AOE网络 10 2 4 2 6

1 19 6 4 15 11 5 5 3

各顶点（事件）的最早可能开始时间Ve(i)和最迟允许开始时间Vl(i)参看下表：

顶点 Ve Vl

1 0 0

2 19 19

3 15 15

4 29 37

5 38 38

6 43 43

各边（活动）的最早可能开始时间Ee(k)和最迟允许开始时间El(k)参看下表：

边 Ee El

<1,2> <1,3> 0 17

0 0

<3,2> 15 15

<2,5> 19 19

<3,5> 15 27

<2,4> <4,6> 19 27

29 37

<5,6> 38 38

如果活动k的最早可能开始时间Ee(k) 与最迟允许开始时间El(k)相等，则该活动是关键活动。本题

的关键活动为<1,3>, <3,2>, <2,5>, <5,6>，它们组成关键路径。这些关键活动中任一个提前完成，整个工程就能提前完成。

整个工程最早在43天完成。由关键活动组成的AOV网络如图所示。 10 2 4 2 6

1 19 6 4 15 11 5 5 3

8. 带权有向图如图所示： 8

0 4 1 7 2 4 1

9 2

5 3 4 应用Dijkstra算法求从顶点V0到其他各顶点的最短路径Path和最短路径长度Len的步骤如下：

步骤 1 2 3 4 V0 V1 Path V0V1 V0V1 V0V1 V0V1 V0V1 V0V1 V0V1 Len 4 4 4 4 4 4 4 V2 Path — V0V1V2 V0V1V2 V0V1V2 V0V1V2 V0V1V2 V0V1V2 Len ∞ 8 8 8 8 8 8 V3 Path V0V3 V0V3 V0V3 V0V3 V0V3 V0V3 V0V3 Len 7 7 7 7 7 7 7 V4 Path — — — V0V3V4 V0V3V4 V0V1V2V4 V0V1V2V4 Len ∞ ∞ ∞ 12 12 10 10 动作 选V0V1 参照V1调整 选V0V3 参照V3调整 选V0V1V2 参照V2调整 选V0V1V2V4