边的集合 E(G)={(V1,V2),(V2,V3),(V1,V4),(V4,V5),(V5,V6)}
(4) V1到V3最短路径为67: (V1—V4—V3)
39．注：(1).本表中DIST中各列最下方的数字是顶点a到顶点的最短通路，a到z为13。 (2)．DIST数组的常量表达式（即下标）应为符号常量，即‘b’，‘c’等，为节省篇幅，所S（已确定最短路径的顶 选点集合） 顶点 初{a} 态 d {a,d} c b g f i e j z h {a,d,c} {a,d,c,b} {a,d,c,b,g} {a,d,c,b,g,f} {a,d,c,b,g,f,i} {a,d,c,b,g,f,i,e} {a,d,c,b,g,f,i,e,j} {a,d,c,b,g,f,i,e,j,z} T(尚未确定最短路径的顶点集合) DIST b c d e f g h i j z {b,c,d,e,f,g,h,i,j,z} 3 2 1 ? ? ? ? ? ? ? {b,c,d,e,f,g,h,i,j,z} 3 2 {b,e,f,g,h,i,j,z} {e,f,g,h,i,j,z} {e,f,h,i,j,z} {e,h,i,j,z} {e,h,j,z} {h,j,z} {h,z} {h} 3 ? ? 4 ? ? ? ? ? 6 4 ? ? ? ? 9 6 4 ? ? ? ? 9 5 9 9 ? 10 13 ? 14 7 13 ? 14 11 16 14 14 14 11 16 13 {a,d,c,b,g,f,i,e,j,z,h} {} 用了b,c等。 (3)．最短路径问题属于有向图，本题给出无向图，只能按有向完全图理解。
（6）
40．下面用FLOYD算法求出任意两顶点的最短路径（如图A所示）。题目要求娱乐中心“距其它各结点的最长往返路程最短”，结点V1，V3，V5和V6最长往返路径最短都是9。按着“相同条件下总的往返路径越短越好”，选顶点V5，总的往返路径是34。
A=
(0)
A=
(1)
A=
(2)
A=
(3)
A=
(4)
A=
(5)
A=
(6)
41．顶点1到其它顶点的最短路径依次是20，31，28，10，17，25，35。按Dijkstra算法所选顶点依次是5，6，2，7，4，3，8，其步骤原理请参见第39题，因篇幅所限，不再画出各步状态。
42．顶点a到顶点b，c，d，e，f，g间的最短路径分别是15，2，11，10，6，13。 43．顶点A到顶点B，C，D，E的最短路径依次是3，18，38，43，
按Dijkstra所选顶点过程是B，C，D，E。支撑树的边集合为{,
45．（1）略 （2） V2 V3 V8 V4 V6 V5 V7
V1
V3 V2 V4 V6 V5 V7 V8
（3）关键路径有3条，长17。（各事件允许发生的最早时间和最晚时间略）
V1->V2->V4->V6->V8，V1->V3->V5->V7->V8，V1->V2->V4->V6->V5->V7->V8
（4）V1结点到其它各结点的最短距离为：2，3，6，12，10，15，16。 46．（1）对有向图，求拓扑序列步骤为：
1）在有向图中选一个没有前驱（即入度为零）的顶点并输出。 2）在图中删除该顶点及所有以它为尾的弧。 3）重复1）和2），直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。
（2）这里使用形式化描述方法，当有多个顶点可以输出时，将其按序从上往下排列，这样不会丢掉一种拓扑序列。这里只画出从顶点1开始的所有可能的拓扑序列，从顶点3开始的拓扑序列可类似画出。 1 2 3 4 5 6 7 8 7 6 8 8 6 7 5 6 8 (3)V1,V2,V5,V3,V4,V6,V8,V7,V9,V10 V9 V7 V6 V5 V9 V7 V6 V5 设一栈，将入度为零的顶
V10 点放入栈中 V8 V10 V8 8 6 8 5 6 5 4 6 7 8 7 6 8 8 6 3 2 4 5 6 7 8 7 6 8 8 6 8 6 8 5 6 5 4 6 7 8 7 6 8 8 6 4 2 5 6 7 8 7 6 8 8 6 7 5 6 8 8 6 8 5 6 1 3 2 4 7 5 6 8 1 3 4 5 2 6 7 8 7 6 8 8 6 6 2 7 8 5 2 4 6 7 8 7 6 8 8 6 4 2 6 7 8 7 6 8 8 6 6 2 7 8
47．图的深度优先遍历可用于拓扑排序。带环的有向图不能拓扑排序。深度优先遍历如何发现环呢？若从有向图某顶点V出发进行遍历，在dfs(v)结束之前出现从顶点W到顶点V的回边，由于W在生成树上是V的子孙，则有向图中必定存在包含顶点V和W的环。其算法实现见下面算法题第41题。 48．（1）V1,V2,V3,V8,V5,V7,V4,V6 （2）V1,V2,V4,V6,V3,V5,V7,V8 （3）V1到V8最短路径56，路径为V1----V2----V5----V7----V8 3 a4=43 （4） a12=8 2 a1=6 a5=6 a10=38 8 1 5 a6=11 a2=1 a7=12 a11=24 a13=20 4 7
a3=50 a8=1 a9=12 6
V1到V8的关键路径是V1----V6----V5----V3----V8，长97。 49．（1） B 100 60 A 10 30 20 C D 10 50 E （2）略
（3）深度优先遍历序列：ABCDE 广度优先遍历序列：ABCED （4）关键路径A--B
（长100）
50．AOE网的始点是入度为零的顶点，该顶点所代表的事件无任何先决条件，可首先开始。终点是出度为零的顶点，表示一项工程的结束。正常的AOE网只有一个始点和一个终点。 51．（1）AOE网如右图
F.40 L.30 K.15 图中虚线表示在时间上前后工序之间仅是接 10 9 5 J.60 B.10 3 M.20 续顺序关系不存在依赖关系。顶点代表事件，弧 H.15 D.8 7 1 12 11 I.120 代表活动，弧上的权代表活动持续时间。题中顶 A.15 4 6 8 2 点1代表工程开始事件，顶点11代表工程结束事件。 C.50 E.15 G.300 （2）各事件发生的最早和最晚时间如下表 事 件 1 2 15 15 3 10 57 4 65 65 5 50 6 80 7 8 9 10 11 12 最早发生时间 0 最晚发生时间 0 200 380 395 425 445 420 335 380 395 425 445 425 380 80 （3）关键路径为顶点序列：1->2->4->6->8->9->10->11；
事件序列：A->C->E->G->H->L->M，完成工程所需的最短时间为445。
52
顶点 Ve(i) Vl(i)
活动 e(i) l(i) aaaaaaaaaa11 2 3 4 5 6 7 8 9 0 0 0 0 0 1 6 6 3 3 4 210 3 22333 7 8 8 9 4 1 4 a11 a12 a13 a14 a15 a16 a17 α A 0 0 1 B 6 C 3 D 4 7 E F G H W 24 13 39 22 52 31 13 39 22 52 29 24 3 24 13 13 13 39 22 22 31 20 36 13 39 22 40 关键路径是：
C F H G W ，长52。 ?
活动与顶点的对照表：a1<α,A> a2<α,B> a3<α,C> a4<α,D> a5 a6
a8
53．A.0—2—6—9—11 B.20 C.1，5，7 D.各2 天 E.0
五.算法设计题
1. void CreatGraph (AdjList g)
//建立有n个顶点和m 条边的无向图的邻接表存储结构 {int n,m;
scanf(\
for (i =1,i<=n;i++)//输入顶点信息,建立顶点向量 {scanf(&g[i].vertex); g[i].firstarc=null;} for (k=1;k<=m;k++)//输入边信息 {scanf(&v1,&v2);//输入两个顶点
i=GraphLocateVertex (g,v1); j=GraphLocateVertex (g,v2); //顶点定位 p=(ArcNode *)malloc(sizeof(ArcNode));//申请边结点
p->adjvex=j; p->next=g[i].firstarc; g[i].firstarc=p;//将边结点链入 p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=i; p->next=g[j].firstarc; g[j].frstarc=p; }
}//算法CreatGraph结束
2. void CreatAdjList(AdjList g)
//建立有向图的邻接表存储结构 {int n;
scanf(\\,&n); for (i=1;i<=n;j++)
{scanf(&g[i].vertex); g[i].firstarc=null;}//输入顶点信息 scanf(&v1,.&v2);
while(v1 && v2)//题目要求两顶点之一为0表示结束 {i=GraphLocateVertex(g2,v1);
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j; p->next=g[i].firstarc; g[i].firstarc=p;
scanf(&v1,&v2); } }
3. void CreatMGraph(AdjMulist g)
//建立有n个顶点e条边的无向图的邻接多重表的存储结构 {int n,e;
scanf(\
for(i=1,i<=n;i++) //建立顶点向量
{ scanf(&g[i].vertex); g[i].firstedge=null;} for(k=1;k<=e;k++) //建立边结点 {scanf(&v1,&v2);
i=GraphLocateVertex(g,v1); j=GraphLocateVertex(g,v2);
p=(ENode *)malloc(sizeof(ENode)); p->ivex=i; p->jvex=j; p->ilink=g[i].firstedge; p->jlink=g[j].firstedge; g[i].firstedge=p; g[j].firstedge=p; }
}//算法结束
4. void CreatOrthList(OrthList g)
//建立有向图的十字链表存储结构 {int i,j,v; //假定权值为整型 scanf(\
for(i=1,i<=n;i++) //建立顶点向量