《数据结构 Java语言版 教学课件 ppt 王学军习题答案 第8章 图》由会员分享，可在线阅读，更多相关《数据结构 Java语言版 教学课件 ppt 王学军习题答案 第8章 图（8页珍藏版）》请在金锄头文库上搜索。
1、第八章习题参考答案一、简答题1【参考答案】：图是一种网状数据结构，图是由结点集合V和边集合E组成的。图中的结点又称为顶点。结点之间的关系称为边。全部由无向边构成的图，称为无向图。全部由有向边组成的图，称为有向图。完全图分为：有向完全图和无向完全图。具有n个结点的无向图G中，其边的最大数目为n(n-1)/2，当边数为最大值时，则称图G为无向完全图。具有n个结点的有向图G中，其边的最大数目为n(n-1)，当有向图G的边数为最大值时，则称图G为有向完全图。若图G中，任意两个不同的结点都连通，则称为G为连通图，设有两个图G=(V,E)和G=(V,E)，如果V是V的子集，即VV，而且E是E的子集即EE，
2、则称G为G的子图。即子图就是图G中的部分集合。边上标有权的图称为网，也称为带权图。举例略。2【参考答案】：无向图G的极大连通子图，称为图G的连通分量。有向图G中的极大强连通子图称为图G的强连通分量。举例略。3【参考答案】：结点的度（degree）是图中与结点v相关联边的数目，记为D(v)。在有向图中，结点v的度有入度和出度之分，以v为终点的弧的数目称为入度，记为ID(v)；以v为起点的弧的数目称为出度，记为OD(v)。出度为0的结点称为终端结点或叶子结点。结点的度等于它的入度和出度之和，即：D(v)=ID(v)+OD(v)举例略。4【参考答案】：连通图G的生成树是图G的极小连通子图，它包含有图
3、G中的全部结点，但只有构成一棵树的n-1条边，即子图G中的边集合E(G)是连通图G中所有结点又没有形成回路的边。称子图G是原图G的一棵生成树。在一个带权图的所有生成树中，加权值总和最小的生成树称为最小生成树，也称最小代价生成树。举例略。5【参考答案】：对于带权图，通常把一条路径上所经过边的权值之和称为该路径的路径长度。在图中，从一个结点到另外一个结点可能不止一条路径，把其中路径长度最短的那条路径称为最短路径，其路径长度（权值之和）称为最短路径长度或最短距离。由于AOE网中的某些活动能够同时进行，完成整个工程所必须花费的时间应该为开始结点到完成结点之间的最大路径长度，这里的路径长度是指该路径上的
4、各个活动所需时间之和。具有最大路径长度的路径称为关键路径。6【参考答案】：在有向图中，构造拓扑序列的过程，称为拓扑排序。对AOV网进行拓扑排序的方法和步骤如下：（1）从AOV网中选择一个没有前趋的结点（该结点的入度为0）并且输出它；（2）从网中删去该结点，并且删去从该结点发出的全部有向边；（3）重复上述两步，直到剩余网中不再存在没有前趋的结点为止。操作的结果有两种：一种是网中全部结点都被输出，这说明网中不存在有向回路，拓扑排序成功；另一种是网中结点未被全部输出，剩余的结点均有前趋结点，这说明网中存在有向回路，不存在拓扑有序序列。7【参考答案】：把结点表示活动，边表示活动先后关系的有向图称为结点
5、活动网，简称AOV网。AOE网是一个带权有向无环图，其中结点表示事件，有向边（弧）表示活动，弧上的权值表示活动的权值（如该活动持续的时间，活动的开销等）。举例略。8【参考答案】：深度优先搜索遍历9【参考答案】：（1）D(V1)=2 ID(V1)=0 OD(V1)=2 D(V2)=4 ID(V2)=2 OD(V2)=2D(V3)=4 ID(V3)=1 OD(V3)=3 D(V4)=4 ID(V4)=2 OD(V4)=2D(V5)=4 ID(V5)=3 OD(V5)=1 D(V6)=2 ID(V6)=2 OD(V6)=0（2）V2v3v4v1123414v5560502020503040V6330
6、440530123450 (3) 深度优先搜索遍历所得的节点序列可能为： v1，v2，v4，v6，v5，v3 v1，v3，v5，v6，v4，v2 v1，v2，v4，v5，v6，v3(4) D(V1)=2 D(V2)=2 D(V3)=2 D(V4)=4D(V5)=3 D(V6)=4 D(V7)=3 D(V8)=2 (5) (6) 广度优先搜索遍历所得的节点序列可能为： v1，v2，v3，v4，v5，v6，v7，v8 v1，v3，v2，v4，v5，v6，v7，v8 (7) 从节点v0开始，用Prim算法构造最小生成树的过程如下：（a）步骤1v22v1v33（b）步骤2v22v1v3v432（c）步
7、骤3v22v1v3v4122v5v64（e）步骤5v22v1v3v4122v7v5v624（f）步骤6v22v1v3v4122v8v7v5v62112（g）步骤7v22v1v3v4122v8v7v5v6112（h）步骤8v22v1v3v4122v8v7v5v6112（d）步骤4v22v1v3v4122v5v6413 (8) 源点终点最短路径路径长度v1v2(v1, v2)2v6(v1,v2,v4,v5,v6)或(v1,v3,v4,v5,v6)7v8(v1,v2,v4,v5,v6，v8)或(v1,v3,v4,v5,v6，v8)810【参考答案】：注意：将北京到南京的距离由原来的1141km更改为
8、1741km.（1）903BJSHNJXAQDDL14903491149135116122270212719211006657122417418321498（2）（3）BJSHNJXAQDDL349步骤1BJSHNJXAQDDL349657步骤2BJSHNJXAQDDL349657832步骤3903BJSHNJXAQDDL349657832步骤4903BJSHNJXAQDDL11491921657832步骤5349（4）注意：将北京到南京的距离由原来的1141km更改为1741km.北京到南京的路径为：BJ,QD,NJ 路径长度为：1489km二、选择题【1】A 【2】A 【3】D 三、实验题
9、1【参考答案】：深度优先搜索部分参考程序如下：public class GraphadjMat /以邻接矩阵存储的图类 protected int n; /图的结点个数 protected int adjMat; /二维数组存储图的邻接矩阵 protected int visited; /访问标记数组 public GraphadjMat() public GraphadjMat(int m1) n=m1.length; adjMat=new intnn; System.arraycopy(m1,0,adjMat,0,n); /System类方法，复制数组 visited=new int n;
10、 public void depthfs(int k) /从结点k开始的深度优先遍历 int i,j=0; System.out.print(v+k+ ); i=k-1; /i下标从0开始 visitedi=1; while(jn) /查找与k相邻的其他结点 if(adjMatij=1 & visitedj=0) depthfs(j+1); /递归 else j+; public void DFS() /图的深度优先遍历 System.out.println(分别依各个节点为起点开始遍历，得到的深度优先遍历搜索序列如下：); for(int k=1;k=n;k+) /k为结点序号,从1开始 d
11、epthfs(k); System.out.println(); unvisited(); public void unvisited() /设置未访问标记 int i; for(i=0;ivisited.length;i+) visitedi=0; 2【参考答案】：广度优先搜索部分参考程序如下：（注意，需要用到单链表和队列）class GraphadjMat /以邻接矩阵存储的图类 protected int n; /图的结点个数 protected int adjMat; /二维数组存储图的邻接矩阵 protected int visited; /访问标记数组 public GraphadjMat() public GraphadjMat(int m1) n=m1.length; adjMat=new intnn
