其中箭头表示作业，箭头边的数字表示完成作业所需的天数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如0-2-7-9-11）表示进行作业的路径。
完成此工程的关键路径是（A）完成此工程所需的最少天数为（B）天，此工程中具有最大充裕天数的事件是（C），充裕天数是（D）。关键路径上的事件的充裕天数是（E）。 参考答案：
A．0—2—6—9—11；B．20；C．1，5，7；D．各2天；E．0。
37．设有无向网如下，写出其邻接矩阵，并在此基础上按普里姆算法求最小生成树。
参考答案：
邻接矩阵：
???4??3??????????????4?559???35?5???5?55?7654?9?7?3?????63?2????5?2?6?????5??4? ?????6?????最小生成树：
38．试写出对如下有向无环图进行拓扑排序可能得到的所有拓扑序列。
参考答案：
每次输出一个入度为０的顶点。ａｂｃｄｅｆｇ、ａｂｃｄｆｅｇ、ａｂｃｆｄｅｇ。
39．设有向网如下，用弗洛伊德算法求图中各对顶点间的最短路径。
参考答案：
三、算法设计题
1．设无向图G有n个顶点，m条边。试编写用邻接表存储该图的算法。（设顶点值用1～n或0～n-1编号） 参考答案：
void CreatGraph (AdjList g)
//建立有n个顶点和m 条边的无向图的邻接表存储结构 {int n,m;
scanf(\输入顶点的个数n，边的数量m for (i=1;i<=n;i++)//输入顶点信息,建立顶点向量 { scanf(\for (k=1;k<=m;k++)//输入边信息 {
scanf(\输入两个顶点 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].firstarc=p; }
}//CreatGraph
2．请用C语言描述算法。已知有向图有n个顶点，请写算法，根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的
void CreatAdjList(AdjList g)
//建立有向图的邻接表存储结构 {int n;
scanf(\for (i=1;i<=n;j++)
{scanf(\输入顶点信息 scanf(\
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(\} }
3．设有向G图有n个点(用1,2,?,n表示)，e条边，写一算法根据其邻接表生成其反向邻接表，要求算法复杂性为O(n+e)。 参考答案：
void InvertAdjList(AdjList gin, AdjList gout）
//将有向图的出度邻接表改为按入度建立的逆邻接表
{for (i=1;i<=n;i++)//设有向图有n个顶点，建逆邻接表的顶点向量。 {gin[i].vertex=gout[i].vertex; gin[i].firstarc=null; } for (i=1;i<=n;i++) //邻接表转为逆邻接表。 {p=gout[i].firstarc;//取指向邻接表的指针。 while (p!=null) { j=p->adjvex;
s=(ArcNode *)malloc(sizeof(ArcNode));//申请结点空间。 s->adjvex=i; s->next=gin[j].firstarc; gin[j].firstarc=s; p=p->next;//下一个邻接点。 }//while }//for }
4．写出从图的邻接表表示转换成邻接矩阵表示的算法，用C语言写成过程形式。 参考答案：
void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm) //将图的邻接表表示转换为邻接矩阵表示。
{for (i=1;i<=n;i++) //设图有n个顶点，邻接矩阵初始化。 for (j=1;j<=n;j++) gm[i][j]=0; for (i=1;i<=n;i++)
{ p=gl[i].firstarc; //取第一个邻接点。
while (p!=null) {gm[i][p->adjvex]=1;p=p->next; }//下一个邻接点 }//for }//算法结束
5．设已给出图的邻接矩阵，要求将邻接矩阵转换为邻接表，用C语言写为过程形式。 参考答案：
void AdjMatrixToAdjList( AdjMatrix gm, AdjList gl ) //将图的邻接矩阵表示法转换为邻接表表示法。 {for (i=1;i<=n;i++) //邻接表表头向量初始化。 {scanf(\for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (gm[i][j]==1)
{ p=(ArcNode *)malloc(sizeof(ArcNode)) ;//申请结点空间。 p->adjvex=j;//顶点I的邻接点是j
p->next=gl[i].firstarc; gl[i].firstarc=p; //链入顶点i的邻接点链表中 } }//end
算法中邻接表中顶点在向量表中的下标与其在邻接矩阵中的行号相同。
6．试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径（i<>j）。注意：算法中涉及的图的基本操作必须在存储结构上实现。 参考答案：
在有向图中，判断顶点Vi和顶点Vj间是否有路径，可采用遍历的方法，从顶点Vi出发，不论是深度优先遍历（dfs）还是宽度优先遍历（bfs），在未退出dfs或bfs前,若访问到Vj，则说明有通路，否则无通路。设一全程变量flag。初始化为0，若有通路，则flag=1。
int visited[]=0; //全局变量，访问数组初始化 int dfs(AdjList g, int vi)
//以邻接表为存储结构的有向图g，判断顶点Vi到Vj是否有通路,返回1或0表示有或无 {
visited[vi]=1; //visited是访问数组，设顶点的信息就是顶点编号。 p=g[vi].firstarc; //第一个邻接点。 while ( p!=null) {
j=p->adjvex;
if (vj==j) { flag=1; return（1）;} //vi 和 vj 有通路。 if (visited[j]==0) dfs(g,j); p=p->next; }//while if (!flag) return(0); }//结束
若顶点vi和vj 不是编号，必须先用顶点定位函数,查出其在邻接表顶点向量中的下标i和j。
7．已知无向图采用邻接表存储方式，试写出删除边（i，j）的算法。 参考答案：
void DeletEdge(AdjList g,int i,int j)
//在用邻接表方式存储的无向图g中，删除边(i,j) {
p=g[i].firstarc; pre=null; //删顶点i 的边结点(i,j),pre是前驱指针 while (p)
if (p->adjvex==j)