内容发布更新时间 : 2024/12/22 16:04:10星期一 下面是文章的全部内容请认真阅读。
（ 2 ,
16 ） （ , , ） 1 ,
（ 5 ,
14 ） （ , , ） 1 ,
（ 6 ,
21 ） （ , , ） 1 ,
（ 6 ,
19 ） （ 6 , 1 , 21 ） 2 ,
（ 6 ,
11 ） （ , , ） 4 ,
（ 6 ,
26 ） （ 6 , 5 , 26 ） 5 ,
（ 5 ,
18 ） （ 6 , 2 , 19 ） 4 ,
（ 4 ,
9 ） （ 5 , 4 , 18 ） 2 ,
（ 3 ,
5 ） （ , , ） 2 ,
（ 4 ,
6 ） （ 4 , 2 , 9 ）
3 ,
选择顺序不唯一。
相应的AOV网络为：
A1 A4 A0 A2 A5 A7
A3 A6 一个拓扑排序序列为：A0,A1,A4,A2,A5,A3,A6,A7。 注意：拓扑排序结果不唯一。按拓扑有序的次序对所有顶点从新编号：
原编号 A0 A1 A4 A2 A5 A3 A6 A7 新编号 A0 A1 A2 A3 A4 A5 A6 A7 A1 A2 A0 A3 A4 A7
A5 A6 相应邻接矩阵为：
13
11.
0?0?0??0?Edge??0?0??0?0???011000000020100000031000000040011000051001000060000010070?0??0??0?1??0?1??0??01234567
12. 针对下图所示的AOE网络
2 2
1
4
15 11 3
10 19 5 5 4 6 6 各顶点（事件）的最早可能开始时间Ve(i)和最迟允许开始时间Vl(i)参看下表： 顶点 Ve Vl
各边（活动）的最早可能开始时间Ee(k)和最迟允许开始时间El(k)参看下表： 边 <1,2> <1,3> <3,2> <2,5> <3,5> <2,4> <4,6> <5,6> Ee 0 0 15 19 15 19 29 38 El 17 0 15 19 27 27 37 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
13. 带权有向图如图所示： 0
7
3
8 1 4 1 2 9 5 2 4 4 1 0 0 2 19 19 3 15 15 4 29 37 5 38 38 6 43 43
14
应用Dijkstra算法求从顶点V0到其他各顶点的最短路径Path和最短路径长度Len的步骤如下：
步V0 V1 V2 V3 V4 动作 骤 Path LPath LPath LPath L en en en en 1 V0V1 4 — ∞ V0V3 7 — ∞ 选V0V1 V0V1 4 V0V1V2 8 V0V3 7 — ∞ 参照V1调整 2 V0V1 4 V0V1V2 8 V0V3 7 — ∞ 选V0V3 V0V1 4 V0V1V2 8 V0V3 7 V0V3V4 12 参照V3调整 3 V0V1 4 V0V1V2 8 V0V3 7 V0V3V4 12 选V0V1V2 V0V1 4 V0V1V2 8 V0V3 7 V0V1V2V4 10 参照V2调整 4 V0V1 4 V0V1V2 8 V0V3 7 V0V1V2V4 10 选V0V1V2V4
14. 图G为 p2
p1 p3 p6
p4 p5 可能的施工顺序有：
p1, p2, p4, p3, p5, p6 p1, p4, p2, p3, p5, p6 p4, p5, p1, p3, p2, p6
15. 该图的强连通分量分别为：
a
d
b c
f g
e
五、算法分析题
1. 已知有向图的邻接矩阵表示及其一个算法描述如下： 0 1 1 1 1 0 0 1 0 0
A = 0 0 0 1 1 1 1 0 0 0
0 0 1 1 0
15
const int MaxVertices = 5;
struct Graph { //图的邻接矩阵表示 int Edge[MaxVertices][MaxVertices]; //有向图邻接距阵 int CurrentNode; //有向图当前结点数 int CurrentEdges; //当前边数 }
int unknown ( int i ) {
int d = 0;
for ( int j = 0; j < CurrentNode; j++) { if ( Edge[i][j] != 0 ) d++;
if ( Edge[j][i] != 0 ) d++; }
return d; }
(1) 若定义图的一个对象Graph G，则执行操作G.unknown (3) 后的返回值是多少？ (2) 试说明该算法的功能及时间复杂度。
2. 已知有向图的邻接矩阵表示及其一个操作算法描述如下：
0 1 1 0 1 0 0 0 0 0 A = 0 0 0 1 1
1 1 0 0 0
0 0 0 1 0
const int MaxVertices = 5;
struct Graph { //图的邻接矩阵表示 int Edge[MaxVertices][MaxVertices]; //有向图邻接距阵 int CurrentNode; //有向图当前结点数 int CurrentEdges; //当前边数 }
void unknown ( int i ) { int d, j; d = 0;
for ( j = 0; j < CurrentNode; j++ ) {
if ( Edge[i][j] ) { d++; Edge[i][j] = 0; } if ( Edge[j][i] ) { d++; Edge[j][i] = 0; } }
CurrentEdges -= d; }
若定义图的一个对象Graph G，试写出执行操作G.unknown (3) 后该图的邻接矩阵，并说明该算法的功能。
3. 已知有向图的邻接表类的表示的形式描述如下：
16