第7章 图 课后习题一、单项选择题1.设无向图的顶点个数为n则该图最多有B条边。A.n−1B.n(n−1)/2C.n(n1)/2D.n(n−1)解析无向完全图边数最多每对顶点之间有一条边总边数为n(n−1)/2。2.n个顶点的连通图至少有A条边。A.n−1B.nC.n1D.0解析连通图至少要有n−1条边构成一棵树少于n−1条边必不连通。3.在一个无向图中所有顶点的度数之和等于所有边数的B倍。A. 3B. 2C. 1D.1/2解析每条边贡献2度所以度数之和 2 ×边数。4.具有n个(n1)顶点的强连通图中至少含有B条有向边。A.n−1B.nC.n(n−1)/2D.n(n−1)解析强连通图至少需要n条边构成一个有向环。例如n个顶点排成一个有向环恰好n条边。5.具有n个顶点的有向无环图最多可包含C条有向边。A.n−1B.nC.n(n−1)/2D.n(n−1)解析有向无环图DAG最多边数为完全有向无环图即每个顶点对之间最多一条有向边且无环最大边数为n(n−1)/2如拓扑排序后的上三角全连。6.一个有n个顶点和n条边的无向图一定是D。A.连通的B.不连通的C.无环的D.有环的解析树有n−1条边且无环。nn个顶点n条边比树多一条边必然至少有一个环。7.已知如图7-20所示的一个图若从顶点a出发按深度优先搜索法进行遍历则可能得到的一种顶点序列为A。A. abedfcB. acfebdC. aebcfdD. aedfcb图7-208.已知如图7-21所示的一个图若从顶点a出发按广度优先搜索法进行遍历则可能得到的一种顶点序列为B。A. abcedfB. abcefdC. aebcfdD. acfdeb图7-219.已知如图7-22所示的一个图若从顶点V1出发按深度优先搜索法进行遍历则可能得到的一种顶点序列为A。A. V1 V2 V4 V8 V5 V3 V6 V7B. V1 V2 V4 V5 V8 V3 V6 V7C. V1 V2 V4 V8 V3 V5 V6 V7D. V1 V2 V6 V7 V2 V4 V5 V8图7-2210.已知如图7-23所示的一个图若从顶点V1出发按广度优先搜索法进行遍历则可能得到的一种顶点序列为C。A.V1,V2,V3,V6,V7,V4,V5,V8B.V1,V2,V3,V4,V5,V8,V6,V7C.V1,V2,V3,V4,V5,V6,V7,V8D.V1,V2,V3,V4,V8,V5,V6,V7​图7-23二、综合题1. (1)说明什么是顶点活动网AOV网和拓扑序列。(2)设有向图如图7-24所示写出所有拓扑序列。(3)在图7-24中增加一条边使图仅有一种拓扑序列。图7-24答(1) 顶点活动网用顶点表示活动边表示活动间的先后关系的有向图称为顶点活动网。拓扑序列在顶点活动网中若不存在回路则所有活动可排列成一个线性序列使每个活动的所有前驱活动都排在该活动的前面称此序列为拓扑。(2) 所有拓扑系列如下abdcadbcdabc(3)仅有一条拓扑序列的有向图如下2. (1)说明什么是拓扑排序。(2) 举例用3个顶点的图说明顶点活动网AOV网不能带回路(3)设有向图如图7-25所示写出先删除顶点1的5种拓扑序列。图7-25答(1) 拓扑排序是将顶点活动网中所有顶点排成一个线性序列使得对图中每条有向边⟨u,v⟩顶点u 在序列中都出现在 v之前。它是对依赖关系的一种线性化。(2) 顶点活动网不允许有回路因为回路会导致一组活动互相等待无法确定执行的先后顺序从而使拓扑排序无法完成。图示如下(3) 5 种拓扑序列如下1253641256341523641526341562343. (1) 简述拓扑排序的步骤。(2) 说明有向图的拓扑序列不一定是唯一的原因。(3) 如何利用拓扑排序算法判定图是否存在回路(4) 设有向图如图 7-26 所示写出先删除顶点 1 的 3 种拓扑序列。图 7-26答(1)①从图中选择一个入度为0的顶点输出。②删除该顶点及其所有出边。③重复①、②直到所有顶点输出。④若输出顶点数小于总顶点数则图中存在回路。(2)当图中存在多个入度为0的顶点时选择输出的顺序不唯一从而产生不同的拓扑序列。(3)执行拓扑排序后若输出的顶点数小于图中顶点总数则说明存在回路因为剩余顶点入度均不为0形成环。(4) 3 种拓扑序列如下1523641526341562344. 对于图 7-27 (a) 和图 7-27 (b)按下列条件分别写出从顶点v0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示。(2)假定它们均采用邻接表表示并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序连接的7-27 (a)7-27 (b)解析邻接矩阵表示从小到大访问邻居。邻接表是先访问序号大的邻居。答1a图深度优先0128345679广度优先0142738659b图深度优先012584736广度优先0134267582a图深度优先0438956712广度优先0413728695b图深度优先045873612广度优先0431576285. 对于图 7-28 (1)画出最小生成树并求出它的权。(2)按照用克鲁斯卡尔算法求最小生成树时所得到的各边的次序写出各条边。(3)按照用迪杰斯特拉算法求从顶点0到其余各顶点的最短路径长度。图 7-28答1最小生成树如下6. 对于图7-29试给出一种拓扑序列当出现多于一个入度为0的顶点时则序号最大的顶点优先被删除。图7-29答拓扑序列如下1402365879三、算法设计题1. 根据有向图的邻接矩阵 GA 求出序号为 numb 的顶点的度数。答intgetDegree(intGA[][MAX],intn,intnumb){intoutDegree0,inDegree0;for(inti0;in;i){if(GA[numb][i]!0)outDegree;//出边if(GA[i][numb]!0)inDegree;//入边}returnoutDegreeinDegree;//总度数入度出度}2. 根据无向图的邻接表 GL 求出序号为 numb 的顶点的度数。答typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; } ArcNode; typedef struct VNode { int data; ArcNode *firstarc; } VNode, AdjList[MAX]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; int getDegree(ALGraph *GL, int numb) { int count 0; ArcNode *p GL-vertices[numb].firstarc; while (p ! NULL) { count; p p-nextarc; } return count; // 无向图中度数 邻接表中边结点数 }3. 求出一个用邻接矩阵 GA 表示的图中所有顶点的最大出度值。答int getMaxOutDegree(int GA[][MAX], int n) { int maxOut 0; for (int i 0; i n; i) { int out 0; for (int j 0; j n; j) { if (GA[i][j] ! 0) out; } if (out maxOut) maxOut out; } return maxOut; }