第五课 图
一、选择题
1．图中有关路径的定义是（ ）。
A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 参考答案：A
2．设无向图的顶点个数为n，则该图最多有（ ）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 参考答案：B
备注：设有向图的顶点个数为n，则该图最多有n(n-1)条边。
3．一个n个顶点的连通无向图，其边的个数至少为（ ）。
A．n-1 B．n C．n+1 D．nlogn 参考答案：A
4．要连通具有n个顶点的有向图，至少需要（ ）条边。
A．n-l B．n C．n+l D．2n 参考答案：B
5．n个结点的完全有向图含有边的数目（ ）。
A．n*n Ｂ．n（n+1） C．n／2 D．n*（n-1） 参考答案：D
6．一个有n个结点的图，最少有（ ）个连通分量。
A．0 B．1 C．n-1 D．n 参考答案：B
7．一个有n个结点的图，最多有（ ）个连通分量。
A．0 B．1 C．n-1 D．n 参考答案：D
8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为（ ）。
A．5 B．6 C．8 D．9 参考答案：A 9．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是（A．逆拓扑有序 B．拓扑有序 C．无序的 参考答案：A
10．下面结构中最适于表示稀疏无向图的是（ ）。
A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接表 参考答案：C
11．下列哪一种图的邻接矩阵是对称矩阵？（ ）
。 ）
A．有向图 B．无向图 C．AOV网 D．AOE网 参考答案：B
12．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（ ）。
A．
?A[i,j]i?1n B．
?A?i,j?j?1n C．
?A[j,i]i?1n D．
?A[i,j]?A?j,i?i?1nn+
j?1
参考答案：B
13．下列说法不正确的是（ ）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程 参考答案：C
14．无向图G=(V,E),其中：
V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 参考答案：D
15．设图如右所示， ，在下面的5个序列中，符合深度优先遍历的序列有（ ）个。
a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c
A．5个 B．4个 C．3个 D．2个 参考答案：D
16．下列方法中可以判断出一个有向图是否有环（回路）的是（ ）。
A．广度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径 参考答案：B
17．下列方法中可以判断出一个有向图是否有环（回路）的是（ ）。
A．深度优先遍历 B．广度优先遍历 C．求最短路径 D．求关键路径 参考答案：A
18．在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（ ）。
A．O(n) B．O(n+e) C．O(n2) D．O(n3) 参考答案：B
19．当各边上的权值（ ）时，BFS算法可用来解决单源最短路径问题。
A．均相等 B．均互不相等 C．不一定相等
参考答案：A
20．求解最短路径的Floyd算法的时间复杂度为（ ）。
A．O（n） B．O（n+c） C．O（n*n） D．O（n*n*n） 参考答案：D
21．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={
A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7
参考答案：A
22．若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列（ ）。
A．存在 B．不存在 参考答案：A
23．一个有向无环图的拓扑排序序列（ ）是唯一的。
A．一定 B．不一定 参考答案：A
24．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。
A．G中有弧
25．在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。
A．O(n) B．O(n+e) C．O(n*n) D．O(n*n*n) 参考答案：B
26．关键路径是事件结点网络中（ ）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 参考答案：A
27．下面关于求关键路径的说法不正确的是（ ）。 A．求关键路径是以拓扑排序为基础的
B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D．关键活动一定位于关键路径上 参考答案：C
28．下列关于AOE网的叙述中，不正确的是（ ）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成
参考答案：B
29．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍。
A．1/2 B．2 C．1 D．4 参考答案：B
30．在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
A．1/2 B．2 C．1 D．4 参考答案：C
二、应用题 1．
（1）如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？ 参考答案：G1最多n(n-1)/2条边，最少n-1条边。
（2）如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？ 参考答案：G2最多n(n-1)条边，最少n条边。
2．n个顶点的无向连通图最少有多少条边？n个顶点的有向连通图最少有多少条边？ 参考答案：n-1，n
3．证明：具有n个顶点和多于n-1条边的无向连通图G一定不是树。 参考答案：
具有n个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n-1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。
4．用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？ 参考答案：
设图的顶点个数为n(n≥0)，则邻接矩阵元素个数为n2，即顶点个数的平方，与图的边数无关。
5．请回答下列关于图(Graph)的一些问题：
（1）有n个顶点的有向强连通图最多有多少条边?最少有多少条边?
（2）表示有1000个顶点、l000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？ （3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环？ 参考答案： （1）n(n-1)，n
（2）106，不一定是稀疏矩阵（稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律）
（3）使用深度优先遍历，按退出DFS过程的先后顺序记录下的顶点是逆向拓扑有序序列。若在执行DFS (v)未退出前，出现顶点u到v的回边，则说明存在包含顶点v和顶点u的环。
6．设有数据逻辑结构为：B = (K, R), K = {k1, k2, ?, k9}
R={
（1）画出这个逻辑结构的图示。
（2）相对于关系r，指出所有的开始接点和终端结点。
（3）分别对关系r中的开始结点，举出一个拓扑序列的例子。
（4）分别画出该逻辑结构的正向邻接表和逆向邻接表。 参考答案： （1）略。
（2）开始结点：（入度为0）K1，K2，终端结点（出度为0）K6，K7。 （3）拓扑序列K1，K2，K3，K4，K5，K6，K8，K9，K7
K2，K1，K3，K4，K5，K6，K8，K9，K7
规则：开始结点为K1或K2，之后，若遇多个入度为0的顶点，按顶点编号顺序选择。 （4）略。
7．有向图的邻接表存储如下，要求：（1）画出其邻接矩阵存储；（2）写出图的所有强连通分量；（3）写出顶点a到顶点i的全部简单路径。
参考答案：
（1）略。（注：邻接矩阵下标按字母升序:abcdefghi）
（2）强连通分量：（a），(d)，（h），(b，e，i，f，c，g）
（3）顶点a到顶点i的简单路径：（a->b->e->i），（a->c->g->i），（a->c->b->e->i）。
8．如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线以上？ 参考答案：
按各顶点的出度进行排序。n个顶点的有向图，其顶点最大出度是n-1，最小出度为0。这样排序后，出度最大的顶点编号为1，出度最小的顶点编号为n。之后，进行调整，即若存在弧
9．首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。
参考答案：
深度优先遍历序列：125967384；宽度优先遍历序列：123456789。
注：（1）邻接表不唯一，这里顶点的邻接点按升序排列；（2）在邻接表确定后，深度优先和宽度优先遍历序列唯一；（3）这里的遍历，均从顶点1开始。
10．下面的邻接表表示一个给定的无向图，
（1）给出从顶点v1开始，对图G用深度优先搜索法进行遍历时的顶点序列； （2）给出从顶点v1开始，对图G用广度优先搜索法进行遍历时的顶点序列。
参考答案：（1）V1V2V4V3V5V6；（2）V1V2V3V4V5V6。
11．设G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。
234?1
5?1342
124?3
12 35?4 24?5
参考答案：
深度优先生成树：
广度优先生成树：
12．对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些？ 参考答案：
遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。
13．某田径赛中各选手的参赛项目表如下: 姓名 参 赛 项 ZHAO A B E QIAN C D SHUN C E F LI D F A ZHOU B F 设项目A,B ,?，F各表示一数据元素，若两项目不能同时举行，则将其连线(约束条件)。 （1）根据此表及约束条件画出相应的图状结构模型，并画出此图的邻接表结构； （2）写出从元素A出发按“广度优先搜索”算法遍历此图的元素序列。 参考答案：
（1）
（2）AFEDBC或ABDEFC。
14．已知无向图如下所示：（1）给出从V1开始的广度优先搜索序列；（2）画出它的邻接表；（3）画出从V1开始深度优先搜索生成树。
参考答案：
设邻接表（略）中顶点的邻接点按顶点编号升序排列（V1编号为1），广度优先搜索序列：V1V2V3V4V5V6V7V8；深度优先搜索序列：V1V2V4V8V5V3V6V7。
15．已知某图的邻接表为
v1v2v3v4v5v6211124?35563????4? （1）写出此邻接表对应的邻接矩阵；
（2）写出由v1开始的深度优先遍历的序列； （3）写出由v1开始的深度优先的生成树； （4）写出由v1开始的广度优先遍历的序列； （5）写出由v1开始的广度优先的生成树；
（6）写出将无向图的邻接表转换成邻接矩阵的算法。 参考答案： （1）略。
（2）V1V2V5V3V4V6
（3）
（4）V1V2V3V4V5V6
（5）
（6）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 }//算法结束
16．考虑右图：
（1）从顶点A出发，求它的深度优先生成树； （2）从顶点E出发，求它的广度优先生成树；
（3）根据普利姆（Prim）算法，求它的最小生成树。 参考答案：
设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列
（1）ABGFDEC
（2）EACFBDG
（3）
17．在什么情况下，Prim算法与Kruskual算法生成不同的MST？ 参考答案：
在有相同权值边时生成不同的MST，在这种情况下，用Prim或Kruskal也会生成不同的MST。
18．已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。
参考答案：
Prim算法构造最小生成树的步骤：(1,6),(1,5),(6,2),(2,3),(3,4)
Kruskal算法，构造最小生成树过程：(2,3),(3,4) (或(2,4)),(1,6),(5,6)（或(1，5)）,(2,6)
19．G=(V,E)是一个带有权的连通图，则：
（1）请回答什么是G的最小生成树；
（2）G为下图所示，请找出G的所有最小生成树。 参考答案：
（2）2棵：和
20．试写出用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小生成树的过程。
参考答案：
V（G）={1，2，3，4，5，6，7}
E（G）={（1，6，4），（1，7，6），（2，3，5），（2，4，8），（2，5，12），（
21．求出下图的最小生成树。
1，2，18）}
参考答案：
V（G）={1，2，3，4，5，6，7，8}
E（G）={（3，8，2），（4，7，2），（3，4，3），（5，8，3），（2，5，4），（6，7，4），（1，2，5）}
注：（或将（3，4，3）换成（7，8，3））
22．一带权无向图的邻接矩阵如下图 ，试画出它的一棵最小生成树。
参考答案：
设顶点集合为{1，2，3，4，5，6}，由右边的逻辑图可以看出，在{1，2，3}和{4，5，
6}回路中，各任选两条边，加上（2，4），则可构成9棵不同的最小生成树。
23．下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。
参考答案：
V(G)={1,2,3,4,5,6}
E1(G)={（1，2，16），（2，3，5），（2，6，6），（2，4，11），（6，5，18）}， E2(G)={（1，2，16），（2，3，5），（3，6，6），（2，4，11），（6，5，18）}
24．设无向网G如下：
（1）设顶点a、b、c、d、e、f、h的序号分别为1、2、3、4、5、6、7，请列出网G的邻接矩阵、画出网G的邻接表结构；
（2）写出从顶点a出发,按“深度优先搜索”和“广度优先搜索”方法遍历网G所得到的顶点序列； （3）按Prim算法求出网G的一棵最小生成树。 参考答案：
（2）深度优先搜索序列：abcdehf；宽度优先搜索序列：abfcdef；
（3）最小生成树：。
25．有一图的邻接矩阵如下，试给出用弗洛伊德算法求各点间最短距离的矩阵序列A1，A2，A3，A4。
?02?????016????5?04???3??0? A=?参考答案：
A0= A1= A2=
A3= A4=
26．下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：
（1）该带权有向图的图形；
（2）从顶点V1为起点的广度优先周游的顶点序列及对应的生成树（即支撑树）； （3）以顶点V1为起点的深度优先周游生成树；
（4）由顶点V1到顶点V3的最短路径。 参考答案：
（2）V1,V2,V4,V6,V3,V5
（3）顶点集合V(G)={V1,V2,V3,V4,V5,V6}；边的集合E(G)={(V1,V2),(V2,V3),(V1,V4),(V4,V5),(V5,V6)} （4）V1到V3最短路径为67：(V1—V4—V3)。
27．用最短路径算法，求如下图中a到z的最短通路。
参考答案：
注：
（1）本表中DIST中各列最下方的数字是顶点a到顶点的最短通路，a到z为13。
（2）DIST数组的常量表达式（即下标）应为符号常量，即‘b’，‘c’等，为节省篇幅，用了b,c等。 （3）最短路径问题属于有向图，本题给出无向图，只能按有向完全图理解。
28．求出下图中顶点1到其余各顶点的最短路径。
参考答案：
顶点1到其它顶点的最短路径依次是20，31，28，10，17，25，35。按Dijkstra算法所选顶点依次是5，6，2，7，4，3，8，其步骤原理略。
29．试利用Dijkstra算法求下图中从顶点a到其他个顶点间的最短路径，写出执行算法过程中各步的状态。
参考答案：
顶点a到顶点b，c，d，e，f，g间的最短路径分别是15，2，11，10，6，13。
30．已知图的邻接矩阵为：
当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出： （1）以顶点V1为出发点的唯一的深度优先遍历； （2）以顶点V1为出发点的唯一的广度优先遍历； （3）该图唯一的拓扑有序序列。 参考答案：
（1）深度优先遍历：V1 V2 V4 V6 V8 V10 V9 V7 V5 V3； （2）广度优先遍历：V1 V2 V3 V4 V5 V6 V7 V9 V8 V10；
（3）V1,V2,V5,V3,V4,V6,V8,V7,V9,V10，设一栈，将入度为零的顶点放入栈中。
31．已知一图如下图所示：
（1）写出该图的邻接矩阵； （2）写出全部拓扑排序；
（3）以v1为源点,以v8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径； （4）求V1结点到各点的最短距离。 参考答案： （1）（2）略
（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。
32．下图是带权的有向图G的邻接表表示法，求： （1）以结点V1出发深度遍历图G所得的结点序列； （2）以结点V1出发广度遍历图G所得的结点序列； （3）从结点V1到结点V8的最短路径； （4）从结点V1到结点V8的关键路径。
参考答案：
（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； （4）V1到V8的关键路径是V1----V6----V5----V3----V8，长97。
33．下表给出了某工程各工序之间的优先关系和各工序所需时间，要求： （1）画出相应的AOE网；
（2）列出各事件的最早发生时间,最迟发生时间； （3）找出关键路径并指明完成该工程所需最短时间。
工序代号 A B C D E F G H I J K L M N 所需时间 15 10 50 8 15 40 300 15 120 60 15 30 20 40 A,B B C,D B E G,I E I F,I H ,J,K L G 先驱工作 -- -- 参考答案：
（1）AOE网如右图图中虚线表示在时间上前后工序之间仅是接续顺序关系不存在依赖关系。顶点代表事件，弧代表活动，弧上的权代表活动持续时间。题中顶点1代表工程开始事件，顶点11代表工程结束事件。 （2）各事件发生的最早和最晚时间如下表
（3）关键路径为顶点序列：1->2->4->6->8->9->10->11；事件序列：A->C->E->G->H->L->M，完成工程所需的最短时间为445。
34．对图示的AOE网络，计算各活动弧的e(ai)和l(ai)的函数值，各事件（顶点）的ve（Vj）和vl (Vj)的函数值，列出各条关键路径。
参考答案：
关键路径是：
活动与顶点的对照表：a1<α,A> a2<α,B> a3<α,C> a4<α,D> a5
35．设有ＡＯＥ网如下，试求关键路径。
参考答案：
关键路径１：v1→v2→v5→v7 关键路径２：v1→v3→v6→v7
36．请写出应填入下列叙述中（ ）内的正确答案。
某一工程作业的网络图如下图所示：
其中箭头表示作业，箭头边的数字表示完成作业所需的天数。箭头前后的圆圈表示事件，圆圈中的数字表示事件的编号。用事件编号的序列（例如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)
{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。
8．假设有向图以邻接表存储，试编写算法删除弧
void DeleteArc（AdjList g,vertype vi, vertype vj）
//删除以邻接表存储的有向图g的一条弧
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;} }
9．设有向图用邻接表表示，图有n个顶点，表示为1至n，试写一个算法求顶点k的入度(1 在有向图的邻接表中，求顶点的出度容易，只要简单在该顶点的邻接点链表中查结点个数即可。而求顶点的入度，则要遍历整个邻接表。 参考答案： int count (AdjList g , int k ) //在n个顶点以邻接表表示的有向图g中，求指定顶点k(1<=k<=n)的入度。 { int count =0; for (i=1;i<=n;i++) //求顶点k的入度要遍历整个邻接表。 if(i!=k) //顶点k的邻接链表不必计算 { p=g[i].firstarc;//取顶点 i 的邻接表。 while (p) {if (p->adjvex==k) count++; p=p->next; }//while }//if return(count); //顶点k的入度. } 10．试编写求无向图G的连通分量的算法。要求输出每一连通分量的顶点值。(设图G已用邻接表存储) 参考答案： 使用图的遍历可以求出图的连通分量。进入dfs或bfs一次，就可以访问到图的一个连通分量的所有顶点。 void dfs () { visited[v]=1; printf ( “=”,v); //输出连通分量的顶点。 p=g[v].firstarc; while (p!=null) {if（visited[p->adjvex==0]） dfs(p->adjvex); p=p->next; }//while }// dfs void Count() //求图中连通分量的个数 {int k=0 ; static AdjList g ; //设无向图g有n个结点 for (i=1;i<=n;i++ ) if (visited[i]==0) { printf (\第%d个连通分量:\\n\}//Count 算法中visited[]数组是全程变量，每个连通分量的顶点集按遍历顺序输出。这里设顶点信息就是顶点编号，否则应取其g[i].vertex分量输出。 11．设无向图G已用邻接表结构存储，顶点表为GL[n] (n为图中顶点数)，试用“广度优先搜索”方法，写出求图G中各连通分量的C语言描述算法：BFSCOM(GL)。（注：算法中可调用队列操作的基本算法。） 参考答案： void bfs(AdjList GL，vertype v ) //从v发广度优先遍历以邻接表为存储结构的无向图GL。 { visited[v]=1; printf( \输出第一个遍历的顶点。 QueueInit(Q); QueueIn(Q ,v); //先置空队列，然后第一个顶点v入队列，设队列容量足够大 while (!QueueEmpty(Q)) {v=QueueOut(Q); p=GL[v].firstarc; //GL是全局变量， v入队列。 while (p!=null) {if(visited[p->adjvex]==0) {printf(\p=p->next; }//while }// while (!QueueEmpty(Q)) }//bfs void BFSCOM() //广度优先搜索，求无向图Ｇ的连通分量。 { int count=0; //记连通分量个数。 for (i=1;i<=n;i++) visited[i]=0; for (i=1;i<=n;i++) if (visited[i]==0) {printf(\第%d个连通分量:\\n\}//BFSCOM 12．写出图的深度优先搜索DFS算法的非递归算法。 参考答案： void Traver(AdjList g,vertype v) //图g以邻接表为存储结构，算法从顶点v开始实现非递归深度优先遍历。 {struct arc *stack[]; visited[v]=1;printf(v); //输出顶点v top=0; p=g[v].firstarc; stack[++top]=p; while(top>0 || p!=null) {while (p) if (p && visited[p->adjvex]) p=p->next; else {printf(p->adjvex); visited[p->adjvex]=1; stack[++top]=p; p=g[p->adjvex].firstarc; }//else if (top>0) {p=stack[top--]; p=p->next; } }//while }//算法结束。 以上算法适合连通图，若是非连通图，则再增加一个主调算法，其核心语句是 for (vi=1;vi<=n;vi++) if (!visited[vi]) Traver(g,vi); 13．设计算法以实现对无向图G的深度遍历，要求：将每一个连通分量中的顶点以一个表的形式输出。例如，下图的输出结果为：（1，3）（2，6，7，4，5，8）（9，10） （注：本算法中可以调用以下几个函数： firstadj（g,v）——返回图g中顶点v的第一个邻接点的号码，若不存在，则返回0； nextadj（g,v,w）——返回图g中顶点v的邻接点中处于w之后的邻接点的号码，若不存在，则返回0。 nodes（g）——返回图g中的顶点数） 参考答案： 本题是对无向图Ｇ的深度优先遍历，dfs算法见前述。这里仅给出将连通分量的顶点用括号括起来的算法。为了得出题中的输出结果，各顶点的邻接点要按升序排列。 void Traver( ) {for (i=1;i<=nodes(g);i++) visited[i]=0; //visited是全局变量，初始化。 for (i=1;i<=nodes(g);i++) if (visied[i]==0) {printf (\}//Traver 14．设计算法以判断给定的无向图G中是否存在一条以V0为起点的包含所有顶点的简单路径，若存在，返回TRUE，否则，返回FALSE（注：本算法中可以调用以下几个函数：FIRSTADJ（G，V）——返回图G中顶点V的第一个邻接点的号码，若不存在，则返回0；NEXTADJ（G，V，W）——返回图G中顶点V的邻接点中处于W之后的邻接点的号码，若不存在，则返回0；NODES（G）——返回图G中的顶点数） 参考答案： 本题应使用深度优先遍历。设图的顶点信息就是顶点编号，用num记录访问顶点个数，当num等于图的顶点个数（题中的NODES(G)），输出所访问的顶点序列，顶点序列存在path中，path和visited数组，顶点计数器num，均是全局变量，都已初始化。 void SPathdfs(v0) //判断无向图Ｇ中是否存在以v0为起点，包含图中全部顶点的简单路径。 { visited[v0]=1; path[++num]=v0; if (num==nodes(G)) //有一条简单路径，输出之。 {for (i=1;i<=num;i++) printf( \p=g[v0].firstarc; while (p) {if (visited[p->adjvex]==0) SPathdfs(p->adjvex); //深度优先遍历。 p=p->next; //下一个邻接点。 }//while visited[v0]=0; num--; //取消访问标记，使该顶点可重新使用。 }//SPathdfs 15．已有邻接表表示的有向图， 请编程判断从第u顶点至第v顶点是否有简单路径，若有则印出该路径上的顶点。要求：先描述图的存储结构，并简述算法思路；查找邻接点等图的运算要自己实现。（尽量采用非递归算法） 参考答案： 非递归算法，顶点信息仍是编号。 void AllSPdfs(AdjList g,vertype u,vertype v) //求有向图g中顶点u到顶点v的所有简单路径，初始调用形式：AllSPdfs(g,u,v) { int top=0,s[]; s[++top]=u; visited[u]=1; while (top>0 || p) {p=g[s[top]].firstarc; //第一个邻接点。 while (p!=null && visited[p->adjvex]==1) p=p->next; //下一个访问邻接点表。 if (p==null) top--; //退栈。 else { i=p->adjvex; //取邻接点（编号）。 if (i==v) //找到从u到v的一条简单路径，输出。 {for (k=1;k<=top;k++) printf( \else { visited[i]=1; s[++top]=i; } //else深度优先遍历。 }//else }//while }// AllSPdfs 16．图的D_搜索类似与BFS，不同之处在于使用栈代替BFS中的队列，入出队列的操作改为入出栈的操作，即当一个顶点的所有邻接点被搜索之后，下一个搜索出发点应该是最近入栈(栈顶)的顶点。 （1）用邻接表做存储结构，写一个D_搜索算法； （2）用D_搜索方法的访问次序和相应的生成树，当从某顶点出发搜索它的邻接点，请按邻接点序号递增序搜索，以使答案唯一。 参考答案： （1）D_搜索类似BFS，只是用栈代替队列，入出队列改为入出栈。查某顶点的邻接点时，若其邻接点尚未遍历，则遍历之，并将其压入栈中。当一个顶点的所有邻接点被搜索后，栈顶顶点是下一个搜索出发点。 void D_BFS(AdjList g ,vertype v0) // 从v0顶点开始，对以邻接表为存储结构的图g进行D_搜索。 { int s[], top=0; //栈，栈中元素为顶点，仍假定顶点用编号表示。 for (i=1;i<=n;i++) visited[i]=0; //图有n个顶点，visited数组为全局变量。 for (i=1;i<=n;i++) //对n个顶点的图g进行D_搜索。 if (visited[i]==0) {s[++top]=i; visited[i]=1; printf( \while (top>0) {i=s[top--]; //退栈 p=g[i].firstarc; //取第一个邻接点 while (p!=null) //处理顶点的所有邻接点 {j=p->adjvex; if (visited[j]==0) //未访问的邻接点访问并入栈。 {visited[j]=1; printf( \p=p->next; } //下一个邻接点 }//while(top>0) } //if }//D_BFS （2）D_搜索序列：1234675，生成树如图： 17．我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。 参考答案： 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。 void SpnTree (AdjList g) //用“破圈法”求解带权连通无向图的一棵最小代价生成树。 { typedef struct {int i,j,w}node; //设顶点信息就是顶点编号，权是整型数 node edge[]; scanf( \输入边数和顶点数。 for (i=1;i<=e;i++) //输入e条边：顶点，权值。 scanf(\ for (i=2;i<=e;i++) //按边上的权值大小，对边进行逆序排序。 {edge[0]=edge[i]; j=i-1; while (edge[j].w k=1; eg=e; while (eg>=n) //破圈，直到边数e=n-1. {if (connect(k)) //删除第k条边若仍连通。 {edge[k].w=0; eg--; }//测试下一条边edge[k]，权值置0表示该边被删除 k++; //下条边 }//while }//算法结束。 connect()是测试图是否连通的函数，可用图的遍历实现，若是连通图，一次进入dfs或bfs就可遍历完全部结点，否则，因为删除该边而使原连通图成为两个连通分量时，该边不应删除。前面第17,18题就是测连通分量个数的算法，请参考。“破圈”结束后，可输出edge中w不为０的n-1条边。 18．已知个n顶点的有向图，用邻接矩阵表示，编写函数计算每对顶点的最短路径。 参考答案： 本题用FLOYD算法直接求解如下： void ShortPath_FLOYD(AdjMatrix g) //求具有n个顶点的有向图每对顶点间的最短路径 {AdjMatrix length; //length[i][j]存放顶点vi到vj的最短路径长度。 for (i=1;i<=n;i++) for (j=1;j<=n;j++) length[i][j]=g[i][j]; //初始化。 for (k=1;k<=n;k++) for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (length[i][k]+length[k][j] length[i][j]=length[i][k]+length[k][j]; } 19．欲用四种颜色对地图上的国家涂色，有相邻边界的国家不能用同一种颜色（点相交不算相邻）。（1）试用一种数据结构表示地图上各国相邻的关系；（2）描述涂色过程的算法。 参考答案： 地图涂色问题可以用“四染色“定理。将地图上的国家编号（1到n），从编号1开始逐一涂色，对每个区域用1色，2色，3色，4色（下称“色数”）依次试探，若当前所取颜色与周围已涂色区域不重色，则将该区域颜色进栈；否则，用下一颜色。若1至4色均与相邻某区域重色，则需退栈回溯,修改栈顶区域的颜色。用邻接矩阵数据结构C[n][n]描叙地图上国家间的关系。n个国家用n阶方阵表示，若第i个国家与第j个国家 相邻，则Cij=1，否则Cij=0。用栈s记录染色结果，栈的下标值为区域号，元素值是色数。 void MapColor(AdjMatrix C) //以邻接矩阵C表示的n个国家的地区涂色 { int s[]; //栈的下标是国家编号，内容是色数 s[1]=1; //编号01的国家涂1色 i=2;j=1; //i为国家号，j为涂色号 while (i<=n) { while (j<=4 && i<=n) { k=1; //k指已涂色区域号 while (k //与相邻区不重色，涂色结果进栈，继续对下一区涂色进行试探 }//while (j<=4 && i<=n) if (j>4) {i--; j=s[i]+1;} //变更栈顶区域的颜色。 }//while(i<=n) }//结束MapColor 20．设有向图Ｇ以邻接表形式存储，试基于图的深度优先遍历方法设计一算法，用以判定图中是否存在从顶点vi到顶点vj的路径（i≠j）。 参考答案： 从顶点vi出发进行深度优先遍历，调用完成时所有与vi有路径相通的顶点都被访问到。 Boolean Path(ALGraph G,int i,int j){ //若有向图G中从顶点vi到顶点vj有路径相通，则返回TRUE，否则返回FALSE for(k=0;k if (visited[j]) return TRUE; else return FALSE; }//Path void DFS(ALGraph G,int i){//从顶点vi出发对图Ｇ进行深度优先遍历 visited[i]=TRUE; for(p=G.vertices[i].firstarc;p;p=p->next) //从顶点vi的未被访问的邻接点出发深度优先遍历图Ｇ if (!visited[p->adj]) DFS(G,p->adj); }//DFS 21．设有向图Ｇ以邻接表形式存储，试基于图的广度优先遍历方法设计一算法，用以判定图中是否存在从顶点vi到顶点vj的路径（i≠j）。 参考答案： int exist_path_BFS(ALGraph G,int i,int j){ int visited[MAXSIZE]; InitQueue(Q); EnQueue(Q,i); while(!QueueEmpty(Q)) { DeQueue(Q,u); visited[u]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(k==j) return 1; if(!visited[k]) EnQueue(Q,k); }//for }//while return 0; }//exist_path_BFS 22．试无向图采用邻接表存储结构，试设计算法，判定图中任意给定的两个顶点间是否存在一条长为k的简单路径。 参考答案： 设要判定结点i和结点j间是否存在长为k的简单路径，则只需判定结点i的邻接点l和结点j间是否存在长为k-1的简单路径。 int visited[MAXSIZE]; int exist_path_len(ALGraph G,int i,int j,int k){ if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 else if(k>0) { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { l=p->adjvex; if(!visited[l]) if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else return 0; //没找到 }//exist_path_len 23．已知有向图G中两个顶点u和v，试编写算法求图中从u到v的所有简单路径。 参考答案： int path[MAXSIZE],visited[MAXSIZE]; //暂存遍历过程中的路径 int Find_All_Path(ALGraph G,int u,int v,int k) { //初次调用时传入的参数应为G,u,v,0 path[k]=u; //加入当前路径中 visited[u]=1; if(u==v) { //找到了一条简单路径 printf(\ for(i=0;path[i];i++) printf(\ //打印输出 } else for(p=G.vertices[u].firstarc;p;p=p->nextarc) { l=p->adjvex; if(!visited[l]) Find_All_Path(G,l,v,k+1); //继续寻找 } visited[u]=0; path[k]=0; //回溯 }//Find_All_Path