第七章 图
一、单项选择题 1.B 2.B 3．B 4．A 5．B 6．B 7．B C 8．B 9．C 10．B 11. B 12．A 13. D 14. A 15．B
二、填空题 1．45 2. 略 3. n 4．3
5．2（N-1）
6. 第I列非零元素个数 7. n 2e 8. 深度优先
9．普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法 10. 不存在环 11. 递增 负值
12. 50，经过中间顶点④
13.(1)活动 （2）活动间的优先关系 （3）事件 （4）活动 边上的权代表活动持续时间
14．关键路径
15．（1）某项活动以自己为先决条件 （2）荒谬 （3）死循环
16．1）V1 V4 V3 V6 V2 V5(尽管图以邻接表为存储结构，但因没规定邻接点的排列，所以结果是不唯一的。本答案是按邻接点升序排列给出的。)
（2） ① top==-1 ② top=graph[j].count ③ graph[k].count==0
三、应用题 1．【解答】
（1）顶点 入度 出度 1 3 0 2 2 2
3 1 2 4 1 3 5 2 1 6 2 3
（2） 邻接矩阵
（3）邻接表
（4）逆邻接表
（5）强连通分量
2．略
3．为节省篇幅，这里仅用Kruskal算法，构造最小生成树过程如下：（下图也可选(2,4)代
替(3,4),(5,6)代替(1,5)） 2 5 3 6 3 4
2 5 1
即 10 6 3 5 6 4
4．(1) Pe M N
Pa T
L
1 9 6 1 10 5 2 6 11
(2)略
(3)最小生成树6个顶点5条边： V(G)={Pe,N,Pa,L,T,M}
E(G)={(L,Pa,3),(Pe,T,21),(M,N,32),(L,N,55),(L,Pe,81)} 5．（1）AOE网图略
（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。
四、算法设计题
1． void CreatAdjList(AdjList g)
//建立有向图的邻接表存储结构 {int n;
scanf(\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);
} }
2．void AdjMatrixToAdjList( AdjMatrix gm, AdjList gl )
//将图的邻接矩阵表示法转换为邻接表表示法。 {for (i=1;i<=n;i++) //邻接表表头向量初始化。 {scanf(&gl[i].vertex); gl[i].firstarc=null;} 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
[算法讨论] 算法中邻接表中顶点在向量表中的下标与其在邻接矩阵中的行号相同。
3．void DeletEdge(AdjList g,int i,j)
//在用邻接表方式存储的无向图g中，删除边(i,j)
{p=g[i].firstarc; pre=null; //删顶点i 的边结点(i,j),pre是前驱指针 while (p)
if (p->adjvex==j)
{if(pre==null)g[i].firstarc=p->next;else pre->next=p->next;free(p);}//释放结点空间。
else {pre=p; p=p->next;} //沿链表继续查找
p=g[j].firstarc; pre=null; //删顶点j 的边结点(j,i) while (p)
if (p->adjvex==i)
{if(pre==null)g[j].firstarc=p->next;else pre->next=p->next;free(p);}//释放结点空间。
else {pre=p; p=p->next;} //沿链表继续查找 }// DeletEdge
[算法讨论] 算法中假定给的i，j 均存在，否则应检查其合法性。若未给顶点编号，而给出顶点信息，则先用顶点定位函数求出其在邻接表顶点向量中的下标i和j。
4．[题目分析]有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。
void Print(int v,int start ) //输出从顶点start开始的回路。 {for(i=1;i<=n;i++)
if(g[v][i]!=0 && visited[i]==1 ) //若存在边（v,i），且顶点i的状态为1。 {printf(“%d”,v); if(i==start) printf(“\\n”); else
Print(i,start);break;}//if }//Print
void dfs(int v) {visited[v]=1;
for(j=1;j<=n;j++ )
if (g[v][j]!=0) //存在边(v,j)
if (visited[j]!=1) {if (!visited[j]) dfs(j); }//if else {cycle=1; Print(j,j);} visited[v]=2;
}//dfs
void find_cycle() //判断是否有回路，有则输出邻接矩阵。visited数组为全局变量。 {for (i=1;i<=n;i++) visited[i]=0;
for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i);
}//find_cycle
5．[题目分析] 该题可用求每对顶点间最短路径的FLOYD算法求解。求出每一顶点（村庄）到其它顶点（村庄）的最短路径。在每个顶点到其它顶点的最短路径中，选出最长的一条。因为有n个顶点，所以有n条, 在这n条最长路径中找出最短一条，它的出发点（村庄）就是医院应建立的村庄。
void Hospital(AdjMatrix w,int n) //在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。
{for (k=1;k<=n;k++) //求任意两顶点间的最短路径 for (i=1;i<=n;i++) for (j=1;j<=n;j++)
if (w[i][k]+w[k][j] for (j=1;j<=n;j++) //求从某村庄i（1<=i<=n）到其它村庄的最长路径。 if (w[i][j]>s) s=w[i][j]; if (s<=m) {m=s; k=i;}//在最长路径中，取最短的一条。m记最长路径，k记出发顶点的下标。 Printf(“医院应建在%d村庄，到医院距离为%d\\n”,i,m); }//for }//算法结束 (6) 对以上实例模拟的过程略。在A矩阵中（见下图），各行中最大数依次是9，9，6，7，9，9。这几个最大数中最小者为6，故医院应建在第三个村庄中,离医院最远的村庄到医院的距离是6。 6．[题目分析] 对有向图进行深度优先遍历可以判定图中是否有回路。若从有向图某个顶点v出发遍历，在dfs(v)结束之前，出现从顶点u到顶点v的回边，图中必存在环。这里设定visited访问数组和finished数组为全局变量，若finished[i]=1,表示顶点i的邻接点已搜索完毕。由于dfs产生的是逆拓扑排序，故设一类型是指向邻接表的边结点的全局指针变