执行深度优先搜索的结果为: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