第7章-图.doc

第七章 图
一、基本概念
1、图的概念和基本术语
（1）有向图和无向图
（2）有向完全图和无向完全图
（3）度和边（弧）的关系
（4）路径、简单路径、回路
（5）连通图和连通分量
（6）强连通图和强连通分量
（7）生成树和最小生成树
2、图的两种存储结构
（1）邻接矩阵与邻接表表示（给定图，能够写出其表示）
（2）根据图的存储表示求边数、弧数、度（入度和出度）的方法
3、图的搜索
（1）图的深度搜索基本算法，能够写出深度搜索序列
（2）图的广度搜索基本方法，能够写出广度搜索序列
4、图的最小生成树算法（Prim和Kruskal），可根据给定图，写出其生成过程。（图或表的方式均可）
5、拓扑排序
（1）写出有向图的拓扑序列
（2）拓扑排序是检测图中是否有环的方法，除此外，检测有向图是否具有环还可以利用深度优先搜索。
6、最短路径
（1）两个最短路径算法的基本步骤和时间复杂度
（2）最短路径的求解步骤（参见教材p190和p192）
7、关键路径
（1）关键路径的定义和意义
（2）关键路径的求解步骤（四个关键量的求解）

讲课提要
【主要内容】
1．基本概念及术语
2．图的存储结构
3．图的遍历
4．生成树和最小生成树
5．拓扑排序
6．关键路径
7．最短路径
【教学目标】
1．掌握图的基本概念、图的存储结构、深度和广度优先遍历算法。
2．重点掌握图的邻接矩阵和邻接表存储结构以及相应的遍历算法。
3．重点掌握最小生成树、拓扑排序和关键路径算法的基本思想，并能灵活应用。
学习指导
1．基本概念及术语
Ÿ 图G：由两个集合V(G)和E(G)所组成，记作G＝(V，E)，其中V(G)是图中顶点的非空有限集合，E(G)是图中边的有限集合。
Ÿ 有向图(Digraph)：如果图中每条边都是有向的即每条边在图示时都用箭头表示方向，则称此图为有向图。有向图的边也称为弧，如图6-1中G1是有向图有向图的边用尖括号表示。
，它由V(G1)和E(G1)组成。V(G1)={V1,V2,V3}，Ｅ(G1)={<V1,V2>,,}

Ÿ 无向图(Undigraph)：如果图中每条边都是顶点无序对，则称为无向图。无向边用圆括号括起的两个相关顶点来表示。在无向图无向图的边用圆括号表示。
中，(V1,V2)和(V2,V1)是表示同一条边。
如图6-1所示，G2和G3都是无向图。其中，
V(G2)={V1,V2,V3,V4}
E(G2)={(V1,V2),(V1,V3),(V2,V3),(V2,V4),(V3,V4)} 写一次就好了 用圆括号表示。画邻接矩阵的时候（V1 V2）为1（V2 V1）也为1.

V(G3)={V1,V2,V3,V4,V5,V6,V7}
E(G3)={(V1,V2),(V1,V3),(V2,V4),(V2,V5),(V3,V6),(V3,V7)}
Ÿ 无向完全图和有向完全图：若一个无向图有n个顶点，而每一个顶点与其他n-1个顶点之间都有边，这样的图称之为无向完全图。即共有n(n—1)／2条边。类似地，在有n个顶点的有向图中，若有n(n—1)条弧，即任意两顶点之间都有双向相反的两条弧连接，则称此图为有向完全图。
Ÿ 子图：设有两个图A和B且满足条件：V(B)∈Ｖ(A)且E(B)∈E(A)则称B是A的子图。
Ÿ 路径：在图Ｇ中，从顶点Ｖp到Ｖq的一条路径是顶点序列(Vp, Vi1, Vi2, … , Vin, Vq)且(VpVi1),(Vi1,Vi2), … , (Vin,Vq)是E(G)中的边，路径上边的数目称之为该路径长度。对于有向图，其路径也是有向的，路径由弧组成。
Ÿ 简单路径：如果一条路径上所有顶点除其起始点和终止点外彼此都是不同的，则称该路径是简单路径。
Ÿ 回路和简单回路：在一条路径中，如果其起始点和终止点是同—顶点，则称其为回路。简单路径相应的回路称为简单回路。
Ÿ 连通图和强连通图：在无向图G中，若从Vi到Vj有路径，则称Vi和Vj是连通的。若G中任意两顶点都是连通的，则称G是连通图。对于有向图而言，若G中每一对不同顶点Vi和Vj之间都有Vi到Vj和Vj到Vi的路径，则称G为强连通图。

Ÿ 度、入度和出度：若(Vi, Vj)是E(G)中的一条边，则称顶点Vi和Vj是邻接的．并称边(Vi, Vj)依附于顶点Vi和Vj。所谓顶点的度，就是依附于该顶点的边数。在有向图中，以某顶点为头，即终止于该顶点的弧的数目称为该顶点的入度；以某顶点为尾，即起始于该顶点的弧的数目称为该顶点的出度。该顶点的入度和出度之和称为该顶点的度。
Ÿ
若图G中每一条边都有一个对应的数，则称G为网。这些边上的数字称为权，它可以表示两顶点之间的距离或所花费的代价。类似地，边上带权的有向图称为有向网。如在图6-2中G4是一个网，而图G5则是一个有向网。

【例6-1】回答下列问题：

（1）具有n个顶点的连通图至少有多少条边?
（2）具有n个顶点的强连通图至少有多少条边?这样的图应该是什么形状?
（3）具有n个顶点的有向无环图最多有多少条边?
解：
（1）具有n个顶点的连通图至少有n-1条边。
这是一个与生成树相关的问题。生成树是一个连通图，它具有能够连通图中任何两个顶点的最小边集，任何一个生成树都具有n-1边。因此，具有n个顶点的连通图至少有n-1条边。
（2）具有n个顶点的强连通图至少有n条边，这样的图是一个由n个顶点构成的环。
强连通图是相对于有向图而言的。由于强连通图要求图中任何两个顶点之间能够相互连通，因此每个顶点至少要有一条以该顶点为弧头的弧和一条以该顶点为弧尾的弧，每个顶点的入度和出度至少各为1，即顶点的度至少为2，这样根据图的顶点数、边数以及各项点的度三者之间的关系计算可得：边数=2×n/2=n。
（3）具有n个顶点的有向无环图最多有n×(n—1)/2条边。
这是一个拓扑排序相关的问题。—个有向无环图至少可以排出一个拓扑序列，不妨设这n个顶点排成的拓扑序列为v1，v2，v3，…，vn，那么在这个序列中，每个顶点vi只可能与排在它后面的顶点之间存在着以vi为弧尾的弧，最多有n-i条，因此在整个图中最多有(n-1)+(n-2)+ … +2+1=n×(n-1)/2条边。
2．图的存储结构
常用的存储结构有邻接矩阵和邻接表。
1）邻接矩阵表示法
设G＝(V，E)是有n(n≥1)个顶点的图。则G的邻接矩阵是按如下定义的n阶方阵：

例如，图6-1中G1，Ｇ2的邻接矩阵分别表示为A1、A2，矩阵的行列号对应于图6-1中结点的序号。

由邻接矩阵的定义可知，无向图的邻接矩阵必定是对称阵；有向图的邻接矩阵不一定是对称的。
根据邻接矩阵，很容易判定任意两个顶点之间是否有边相连。求各顶点的度也是非常容易的。对于无向图，顶点Vi的度就是邻接矩阵中第i行(或第j列)上非零元的个数，即。对于有向图，第i行中非零元的个数为顶点Vi的出度，而第i列上的非零元个数为顶点Vi的入度。

（2）邻接表表示法
图的邻接链表存储结构是一种顺序分配和链式分配相结合的存储结构括两个部分：一部分是向量，另一部分是链表。
邻接链表中的表头部分是向量，用来存储n个表头结点。向量的下标指示顶点的序号。
例如，对于图6-1中G1和G2，其邻接链表由大到小
如图6-3所示。
在无向图的邻接表中顶点vi的度就是第i个链表中结点的个数。在有向图中，第i个链表的结点数仅是vi的出度，求vi的入度，必须查遍n个链表才能得出。

【例6-2】 图G＝(V，E)，其中V={1,2,3,4,5,6}，Ｅ＝{<1,2>,<1,3>,<1,4>,<2,5>,<3,2>,<3,5>,
<3,6><4,6>,<5,6>}，请画出图G，并写出其邻接矩阵和邻接表表示。
解：图G如图6-4中的(a)所示，图G的邻接矩阵和邻接表表示分别如图(b)和(c)所示。
对于这类问题，只要掌握了图的概念和存储结构就可以做出正确的答案。通常情况下．对图的顶点排列顺序和各顶点的邻接点排列顺序并没有特定要求，因此，在写出邻接矩阵和邻接表表示时，只要按照某种排列顺序画出相应的结构图就可以了。但应该注意的是，对于邻接矩阵表示，如果顶点结点的顺序不同，那么邻接矩阵就不相同；对于邻接表表示，如果顶点结点的顺序或者邻接点的顺序不同，那么邻接表就不相同。

3．图的遍历
给定一个无向连通图G，G＝(V，E)，当从V(G)中的任一顶点v出发，去访问图中其余顶点，使每个顶点仅被访问一次。这个过程叫做图的遍历。通常有两种遍历图的方法，—种是深度优先搜索法，另—种为广度优先搜索法。
（1）深度优先搜索访问V1 访问与V1相邻的点 比如说有V2 V3.如果访问了V2 接下来访问与V2相邻的点。
（DFS）
设有无向连通图G(V，E)，从V(G)中任一顶点v出发深度优先搜索遍历图的步骤是：先访问指定顶点V1，然后访问与该顶点V1相邻的顶点V2，再从V2出发，访问与V2相邻且未被访问过的任意顶点V3，然后从顶点V3出发，重复上述过程，直到一个所有邻接点都被访问过的顶点为止，然后回溯到此顶点的直接前趋，从这里出发再继续访问。显然搜索是一个递归过程。
（2）广度优先搜索访问V1 访问与V1相邻的点 比如说有V2 V3.。如果访问了V2，接下来访问V3。
(BFS)
设无向图G(V，E)是连通的，从V(G)中的任一顶点V1出发，广度优先搜索遍历图的步骤是：首先访问指定的起始顶点V1，从V1出发，依次访问与V1相邻的未被访问过的顶点W1，W2，W3，…，Wt，然后依次从W1，W2，W3，…，Wt出发，重复上述访问过程，直到所有顶点都被访问过为止。在广度优先搜索过程中，访问某个顶点之后，要将这个顶点保存起来，以备后面访问这个顶点的邻接点。由搜索这个过程可知，保存的信息应该组织成一个队列。
【例63】已知一个无向图的邻接表如图6-5所示，要求：
（1）画出该无向图；
（2）根据邻接表，分别写出用DFS(深度优先搜索)和BFS（广度优先搜索）算法从顶点V0开始遍历该图后所得到的遍历序列。

解：
（1）该无向图如图6-6所示。

（2）根据该无向图的邻接表表示，从顶点V0开始的深度优先遍历序列为：V0、V2、V3、V1、V4、V6、V5。广度优先遍历序列为V0、V2、V5、V6、V1、V3、V4。
从图的逻辑结构上来讲，从图中某个顶点开始的深度(或广度)优先遍历序列不一定是唯一的。这是因为在逻辑结构中，并没有对每个顶点的所有邻接点规定它们之间的先后顺序，这样在搜索算法中选取第—个邻接点和下一个邻接点时可能会有不同的结果。但是在存储结构中，明确地给出了邻接点的先后顺序，这时深度优先和广度优先遍历序列就是唯一的。
4．生成树和最小生成树
Ÿ 无向图的连通分量：无向图的连通分量是图的一个极大连通子图。如图6-7 (a)有两个连通分量，分别为图6-7(b)和(c)。而图6-7(d)不是图6-7(a)的连通分量，因为它虽是图6-7(a)的连通子图，却不是极大连能子图，只有加上顶点Ｖ3后，才构成极大连通子图。无向连通图只有一个连通分量，即是图本身。
Ÿ 最小生成树：设图G是一个连通网，G上的一棵各边权值之和最小的带权生成树，称为G的最小生成树。
构造最小生成树的算法有：普里姆算法和克鲁斯卡尔算法。

5．普里姆（Prim）算法（顶点，确定一顶点）
假设N= ( V, {E} )是连通图，TE是N上最小生成树中边的集合。算法从U={u0}( u0∈Ｖ)，TE={}开始，重复执行下述操作：在所有u∈U, v∈V-U的边(u, v)∈Ｅ中找一条代价最小的边{u0, v0}并入集合TE，同时v0并入U，直到U=V为止。此时TE中必有n-1条边，则T= (V, {TE})为N的最小生成树。
6．鲁斯卡尔（Kruskal）算法（边）
克鲁斯卡尔算法是从另一途径求网的最小生成树。假设连通网N= ( V, {E} )，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T＝(V, {})，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。
【例6-5】 一个带权无向图的最小生成树是否一定唯一？在什么情况下构造出的最小生成树可能不唯一？
解：一个带权无向图的最小生成树不一定是唯一的。从Kruskal算法构造最小生成树的过程可以看出，当从图中选择当前权值最小的边时，如果存在多条这样的边，并且这些边与已经选取的边构成回路，此时这些边就不可能同时出现在一棵最小生成树中，对这些边的不同选择结果可能会产生不同的最小生成树。
7．拓扑排序
（1）AOV网：在有向图中以顶点表示“活动”，用有向边表示“活动”之间的优先关系，这样的有向图称为以顶点表示“活动”的网(Activity On Vertex Network)，简称AOV网。
（2）拓扑排序的方法
对于一个AOV网，构造其所有顶点的线性序列，使此序列不仅保持网中各顶点间原有的先后次序，而量使原来没有先后次序关系的顶点之间也建立起人为的先后关系。这样的序列称为拓扑有序序列。构造AOV网的拓扑有序序列的运算称为拓扑排序。
某个AOV网，如果它的拓扑有序序列被构造成功，则该网中不存在有向回路，其各子工程可按拓扑有序序列的次序进行安排一个AOV网的拓扑有序序列并不是唯一的。
对AOV网进行拓扑排序的步骤是：
第一步：在网中选择一个没有前趋的顶点且输出之。
第二步：在网中删去该顶点，并且删去从该顶点发出的全部有向边。
第三步：重复上述两步，直到网中不存在没有前趋的顶点为止。
这样操作结果有两种；一种是网中全部顶点均被输出，说明网中不存在有向回路；另一种是网中顶点未被全部输出，剩余的顶点均有前趋顶点，说明网中存在有向回路。
拓扑排序的方法很多，主要有深度优先按索排序和广度优先搜索排序两种。
（3）广度优先搜索拓扑排序
根据拓扑排序的方法．把入度为零的顶点插入一个队列，按顺序输出。
（4）深度优先拓扑排序
根据拓扑排序的方法，先用深度优先搜索法向下走，直到无路可走为止。每走一步都伴随着顶点进栈。无路可走时出栈，并同时显示顶点序号。当退回一步后，换向再走，若无向可换，则出栈，即删除无前趋的顶点。
8．掌握关键路径的概念及确定关键路径的算法
若在带权有向图G中，以顶点表示事件，边表示活动，权表示活动持续的时间，则此带权有向图称为用边表示活动的网(Activity On Edge net work)，简称AOE网。由于整个工程只有一个开始点和一个完成点，故在正常情况下，在这种工程图中只有一个入度为0的顶点(称为源点)和一个出度为0的顶点(称为汇点)。
从源点到汇点之间的长度最长的路径称为关键路径。
9．掌握最短路径的概念及确定最短路径的算法
所谓的最短路径是指对所经过的边的值之和为最小的路径。本章给出两个算法：一个是求从某个源点到其他顶点的最短路径，另一个是求每对顶点间的最短路径。
确定单源最短路径可采用迪杰斯特拉（Ｄijkstra）算法。
确定所有顶点之间的最短路径时间复杂度 O(N3)
有两种方法：一种是每次以一个顶点为源点，重复执行迪杰斯特拉算法n次，时间复杂度为O(n3)；另一种是弗洛伊德(Floyd)算法，时间复杂度也是O(n3)，但形式更简单。

二、练习题
1．在一个图中，所有顶点的度数之和等于所有边数的____倍。
A. 1/2 B. 1 C. 2 D. 4
2．任何一个无向连通图的最小生成树 。
A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在
4．一个有n个顶点的无向图最多有____条边。
A. n B. n(n-1) C. n(n-1)/2 D. 2n
6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。
A. 5 B. 6 C. 7 D. 8
7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。
A. n B. n+1 C n-1 D. n/2
8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。
A. n B. (n-1)2 C. n-1 D. n2
9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。
① A. n B. n+1 C. n-1 D. n+e
② A. e/2 B. e C.2e D. n+e

14．判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用____。
A. 求关键路径的方法 B. 求最短路径的Dijkstra方法
C. 宽度优先遍历算法 D. 深度优先遍历算法
16．下面不正确的说法是 。
（1）在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小；
（2）AOE网工程工期为关键活动上的权之和；
（3）在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。
A.（1） B.（2） C.（3） D.（1）、（2）
17．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是 。
A逆拓朴有序的 B.拓朴有序的 C.无序的
19．一个有n个顶点的无向连通图，它所包含的连通分量个数为 。
A.0 B.1 C.n D.n+1
20．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为 。
A.k1 B.k2 C.k1-k2 D.k1+k2
21．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为 。
A.k1 B.k2 C.k1-k2 D.k1+k2
综合题类型：
22. 已知如图7.5所示的有向图，请给出该图的:
（1）每个顶点的入/出度；
（2）邻接距阵；
1
5
6
2
4
3
（3）邻接表；
（4）逆邻接表；
（5）强连通分量。

图7。5一个有向图

23．请用克鲁斯卡尔和普里姆两种算法分别为下图构造从顶点a出发的最小生成树：（给出构造过程，表或图均可）
b
a
d
c
e
f
16
11
15
15
15
16
13
14
12
21

24．试列出图中全部的拓扑排序序列。

1
2
3
4
5
6

25．求顶点a到其余各顶点之间的最短路径。（要求给出求解过程）
5
4
3
2
2
3
3
5
6
a
b
d
f
c

e

26．已知AOE网有9个结点：V1，V2，V3，V4，V5，V6，V7，V8，V9，其邻接矩阵如下：
(1)请画出该AOE图。
(2)计算完成整个计划需要的时间。
(3)求出该AOE网的关键路径。（要求计算出ve,vl,ee,el）
∝
6
4
5
∝
∝
∝
∝
∝
∝
∝
∝
∝
1
∝
∝
∝
∝

∝
∝
∝
∝
1
∝
∝
∝
∝
∝
∝
∝
∝
∝
2
∝
∝
∝
∝
∝
∝
∝
∝
∝
9
7
∝
∝
∝
∝
∝
∝
∝
∝
4
∝
∝
∝
∝
∝
∝
∝
∝
∝
2
∝
∝
∝
∝
∝
∝
∝
∝
4
∝
∝
∝
∝
∝
∝
∝
∝
∝

27. 已知图G的邻接表如图7.4所示，其从顶点v1出发的深度有限搜索序列为____，其从顶点v1出发的宽度优先搜索序列为____。

v1
v3
v2
v4
v5
v6
v2
v5
v4
v3
v5
^
^
v6
v4
v6
v3

图7.4 图G的邻接表
一、选择题
2、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ B ）。
A. 完全图 B. 连通图 C. 有回路 D. 一棵树
4、下面（ B ）可以判断出一个有向图中是否有环（回路）。
A. 广度优先遍历 B. 拓扑排序
C. 求最短路径 D. 求关键路径
6、采用邻接表存储的图，其深度优先遍历类似于二叉树的（ B ）。
A. 中序遍历 B. 先序遍历 C. 后序遍历 D. 按层次遍历
8、当利用大小为N的数组存储循环队列时，该队列的最大长度是（ C ）。
A. N-2 B. N-1 C. N D. N+1
9、邻接表是图的一种（ B ）。
A. 顺序存储结构 B. 链式存储结构 C. 索引存储结构 D. 散列存储结构

11、在无向图中定义顶点vi与vj之间的路径为从vi到vj的一个（ A ）。
A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条数
12、在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（ A ）邻接点。
A. 入边 B. 出边 C. 入边和出边 D. 不是出边也不是入边
15、任一个有向图的拓扑序列（D ）。
A.不存在 B. 有一个 C. 一定有多个 D. 有一个或多个
17、下列关于图遍历的说法不正确的是（ C ）。
A. 连通图的深度优先搜索是一个递归过程
B. 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征
C. 非连通图不能用深度优先搜索法
D. 图的遍历要求每一顶点仅被访问一次
19、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（D ）。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层次遍历
23、以下说法正确的是（ ）。
A. 连通分量是无向图中的极小连通子图
B. 强连通分量是有向图中的极大强连通子图
C. 在一个有向图的拓扑序列中若顶点a在顶点b之前，则图中必有一条弧
D. 对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图
24、假设有向图含n个顶点及e条弧，则表示该图的邻接表中包含的弧结点个数为（ ）。
A. n B. e C. 2e D. n*e
31、无向图中一个顶点的度是指图中（ ）。
A. 通过该顶点的简单路径数 B. 与该顶点相邻接的顶点数
C. 与该顶点连通的顶点数 D. 通过该顶点的回路数

二、填空题
1、n个顶点的连通图至少有 n-1条 边。
2、一个连通图的生成树是一个 极小连通子图 ，它包含图中所有顶点，但只有足以构成一棵树的n-1条边。
3、一个图的 邻接矩阵 表示法是惟一的。
4、遍历图的基本方法有深度优先搜索和广度优先搜索，其中 深度优先搜索 是一个递归过程。
5、在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于 1 。
6、判定一个有向图是否存在回路，可以利用 拓扑排序 。
。
三、判断题
1、图的连通分量是无向图的极小连通子图。 O
2、一个图的广度优先搜索树是惟一的。O
3、图的深度优先搜索序列和广度优先搜索序列不是惟一的。P
4、邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。O
5、存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。O
6、AOV网是一个带权的有向图。O
7、从源点到终点的最短路径是唯一的。O

9、图的生成树是惟一的。O

四、程序分析题
1、写出下面算法的功能。
typedef struct{
int vexnum,arcnum;
char vexs[N];
int arcs[N][N];
}graph;
void funtion(int i,graph *g){
int j;
printf("node:%c\n",g->vexs[i]);
visited[i]=TRUE;
for(j=0;jvexnum;j++) if((g->arcs[i][j]==1)&&(!visited[j]))
function(j,g);
}
答案：实现图的深度优先遍历算法

五、综合题
1、已知图G的邻接矩阵如下所示：
（1）求从顶点1出发的广度优先搜索序列；
（2）根据prim算法，求图G从顶点1出发的最小生成树，要求表示出其每一步生成过程。（用图或者表的方式均可）。

答案：(1)广度优先遍历序列：1; 2, 3, 4; 5; 6
(2)最小生成树（prim算法）

2、设一个无向图的邻接矩阵如下图所示：
（1）画出该图；
（2）画出从顶点0出发的深度优先生成树；

答案： (1)图形态 (2)深度优先搜索树

3、写出下图中全部可能的拓扑排序序列。

答案：1，5，2，3，64 1，5，6，2，3，4 5，1，2，3，6，4
5，1，6，2，3，4 5，6，1，2，3，4
4、AOE网G如下所示，求关键路径。（要求标明每个顶点的最早发生时间和最迟发生时间，并画出关键路径）

答案：(1)最早发生时间和最迟发生时间： (2)关键路径：

5、已知有向图G如下所示，根据迪杰斯特拉算法求顶点v0到其他顶点的最短距离。（给出求解过程）

答案：
终点
从v0到各终点的d值和最短路径的求解过程
i=1
i=2
i=3
i=4
v1
12 (v0,v1)
12 (v0,v1)

7 (v0,v4,v1)

v2
4 (v0,v2)

v3
9 (v0,v3)
8 (v0,v2,v3)
7 (v0,v4,v3)
7 (v0,v4,v3)
v4
5 (v0,v4)
5 (v0,v4)

vj
v2
v4
v1
v3
s
{v0,v2}
{v0,v4}
{v0,v4,v1}
{v0,v4,v3}

6、已知图G如下所示，根据Prim算法，构造最小生成树。（要求给出生成过程）

答案：prim算法求最小生成树如下：

7、已知有向图如下所示，请写出该图所有的拓扑序列。

答案：拓扑排序如下
v1, v2, v4, v6, v5, v3, v7, v8 v1, v2, v4, v6, v5, v7, v3, v8
v1, v2, v6, v4, v5, v3, v7, v8 v1, v2, v6, v4, v5, v7, v3, v8
v1, v6, v2, v4, v5, v3, v7, v8 v1, v6, v2, v4, v5, v7, v3, v8
8、如下图所示的AOE网，求：
（1）求事件的最早开始时间ve和最迟开始时间vl；
事件
1
2
3
4
5
6
7
8
9
Ve

Vl

（2）求出关键路径；

答案：(1)求ve和vl (2)关键路径
如下所示的有向图，回答下面问题：

（1）该图是强连通的吗？若不是，给出强连通分量。
（2）请给出图的邻接矩阵和邻接表表示。
答案：(1) 是强连通图 (2) 邻接矩阵和邻接表为：

9、已知图G的邻接矩阵A=， 试画出它所表示的图G，并根据Prim算法求出图的的最小生成树（给出生成过程）。
答案：
(1)图形态： (2)prim算法求最小生成树：

10、如下图所示的AOV网，写出其中三种拓扑排序序列。

11、已知图G如下，根据克鲁斯卡尔算法求图G的一棵最小生成树。（要求给出构造过程）

答案：kruskal算法的最小生成树

12、已知图G如下所示，求从顶点a到其余各顶点的最短路径。（给出求解过程）
5
4
3
2
2
3
3
5
6
a
b
d
f
c

e

答案：
终点
最短路径求解过程
b
6 (a,b)
5 (a,c,b)

c
3 (a,c)

d
¥
6 (a,c,d)
6 (a,c,d)

e
¥
7 (a,c,e)
7 (a,c,e)
7 (a,c,e)

f
¥
¥
¥
9 (a,c,d,f)
9 (a,c,d,f)
vj
c
b
d
e
f
S
{a,c}
{a,c,b}
{a,c,d}
{a,c,e}
{a,c,d,f}

一、单项选择题
3. 在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为( )。
A. n B. e C. n+e D. 2e
4. 在一个具有n个顶点的无向完全图有n(n-1)/2条边的无向图称为完全图。
中，所含的边数为( )。
A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/2
5. 在一个具有n个顶点的有向完全图n(n-1)条边的有向图称为有向完全图 有向完全图的任意两个顶点都被两条边相连。
中，所含的边数为( )。
A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/2

7. 对于一个具有n个顶点的无向连通图无向连通图，任意两个顶点都连通 强连通图 A到B B到A都有路径。
，它包含的连通分量的个数为( )。
A. 0 B. 1 C. n D. n+1
8. 若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用( )次深度优先搜索遍历的算法。
A. k B. 1 C. k-1 D. k+1
9. 若要把n个顶点连接为一个连通图，则至少需要( )条边。
A. n B. n+1 C. n-1 D. 2n
10. 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为( )。
A. n B. n´e C. e D. 2´e
11. 在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为( )。
A. n B. n´e C. e D. 2´e
12. 在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为( )。
A. n B. n´e C. e D. 2´e
13. 在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为( )。
A. n B. 2n C. e D. 2e
14. 在一个无权图的邻接表表示中，每个边结点至少包含( )域。
A. 1 B. 2 C. 3 D. 4
15. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为( )。
A. k1 B. k2 C. k1-k2 D. k1+k2
16. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的边结点数为( )。
A. k1 B. k2 C. k1-k2 D. k1+k2
17. 对于一个无向图，下面( )种说法是正确的。
A. 每个顶点的入度等于出度 B. 每个顶点的度等于其入度与出度之和
C. 每个顶点的入度为0 D. 每个顶点的出度为0
18. 在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的( )。
A. 出边数 B. 入边数 C. 度数 D. 度数减1
19. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为( )。
A. A,B,C,F,D,E B. A,C,F,D,E,B
C. A,B,D,C,F,E D. A,B,D,F,E,C
20. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为( )。
A. A,B,C,D,E,F B. A,B,C,F,D,E
C. A,B,D,C,E,F D. A,C,B,F,D,E
21. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为( )。
A. 1,2,5,4,3 B. 1,2,3,4,5
C. 1,2,5,3,4 D. 1,4,3,2,5
22. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开