图习题参考答案

1、习题六参考答案一、选择题J,则所有顶点的入度之和为（ A）。1 .在一个有个顶点的有向图中，若所有顶点的出度之和为A. 一BJ JI. C一 D.2 . 一个有向图有1个顶点，则每个顶点的度可能的最大值是（ B）。A.iB.3 .具有6个顶点的无向图至少应有（A.5B.6C.74 . 一个有n个顶点的无向图最多有（A.B.如一1）C.D、A ）条边才能确保是一个连通图。D.8C ）条边。C麻 L。库D._5 .对某个无向图的邻接矩阵来说，下列叙述正确的是（ A）。a.第i行上的非零元素个数和第i列上的非零元素个数一定相等B.矩阵中的非零元素个数等于图中的边数c.第:行与第i列上的非零元素的总数

2、等于顶点办的度数D.矩阵中非全零行的行数等于图中的顶点数6 .已知一个有向图的邻接矩阵，要删除所有以第：个顶点为孤尾的边，应该（B）。A.将邻接矩阵的第1行删除B.将邻接矩阵的第i行元素全部置为0c.将邻接矩阵的第！列删除d.将邻接矩阵的第i列元素全部置为07 .下面关于图的存储的叙述中，哪一个是正确的？（A）A.用邻接矩阵存储图，占用的存储空间只与图中顶点数有关，而与边数无关B.用邻接矩阵存储图，占用的存储空间只与图中边数有关，而与顶点数无关C.用邻接表存储图，占用的存储空间只与图中顶点数有关，而与边数无关D.用邻接表存储图，占用的存储空间只与图中边数有关，而与顶点数无关8 .对图的深度优先

3、遍历，类似于又树的哪种遍历？（ A）A.先根遍历B.中根遍历C.后根遍历D.层次遍历9 .任何一个无向连通图的最小生成树（B）。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在10 .下面是三个关于有向图运算的叙述：(1)求两个指向结点间的最短路径，其结果必定是唯一的(2)求有向图结点的拓扑序列，其结果必定是唯一的(3)求AOE网的关键路径，其结果必定是唯一的其中哪个(些)是正确的？( D )A.只有(1)B. (1)和(2)C.都正确D.都不正确二、填空题1 .若用F表示图中顶点数，则有-1)/2条边的无向图称为完全图。2 .若一个无向图有100条边，则其顶点总数最少为15个。3 .

4、个顶点的连通无向图至少有 5一1 条边，至多有 血一口条边。4 .若有向图(J的邻接矩阵为：斯外。小心坨/01010均 10 111吗01011叫0000100100/则顶点胃的入度是3 。5 .对于一个有向图，若一个顶点的度为H,出度为仁工 则对应逆邻接表中该顶点单链表中的边结点数为止显。6 .图的遍历算法BFS中用到辅助队列，每个顶点最多进队1次。7 .在求最小生成树的两种算法中，克鲁斯卡尔算法适合于稀疏图。8 .数据结构中的迪杰斯特拉算法是用来求某个源点到其余各顶点的最短路径。9 .除了使用拓扑排序的方法，还有深度优先搜索方法可以判断出一个有向图是否有回路。10 .在用邻接表表示图时，拓

5、扑排序算法的时间复杂度为JXn+吐。三、应用题1 .已知如图6.28所示的有向图，请给出该图的图6.28 有向图(1)每个顶点的出/入度;(2)邻接矩阵；(3)邻接表；(4)逆邻接表。答：(1)每个顶点的出/入度是:出度入度103222321431512632(2)邻接矩阵:so o o 1o 1 4 0 1-0000 3 0 0 0 10 011 /0230邻接表:(4)逆邻接表:0123450123451A2345612345630120A0121A3 A323A5A415A45A3A5A4A5A2 .试对如图6.29所示的非连通图，画出其广度优先生成森林。答:.29 非连通图M6.30所

6、示。试分别画出自顶点3.已知图的邻接矩阵如图A出发进行遍历所得的深度优先生成树C 10 1-0 1 0 0 0 1-0 O o o o o o o Oco 1 o o o O 1 o o OBo o o o o 1 o o o o .Ao o o 11 1 J B CD E FG HI rjD E F G H 1 J 00 0 101(h00 0 100010 0 0100010 000 1000 0 000 0 010 0 0 010 100 10图 错误！文档中没有指定样式的文字。.30邻接矩阵答:4.请对如图6.31所示的无向网：(1)写出它的邻接矩阵，并按克鲁斯卡尔算法求其最小生成树;

7、(2)写出它的邻接表，并按普里姆算法求其最小生成树。答：图错误！文档中没有指定样式的文字。.31无向网ABCDEfGH/043GO比800m40559mGOm3505;mCO5mS507654m90010360000cos6302DDGO005DO2060054OTw6EFE3EE33BF4BFBF44AD2ADA333CCC4HHE3BF4AD53CG4H5(2)3:A223 C012345E(D CD2 cz) %H克鲁斯卡尔算法求其最小生成树ABCD-I+EF67422 0GH21441531936-352523A253153253743523447553A62A76A66A49A75A

8、566574ABB45AAAD333CCCBB44B455ADADAD5333CGCC444HHHE3BF45AD53CG4Hacdfbe5.试列出图6.32中全部可能的拓扑有序序列。四、算法设计题2普里姆算法求其最小生成树，从A开始图6.32 有向图答：abcdef、abcef、abecdf、bacdef、bacedf、baecdf、beacdf1.编写算法，从键盘读入有向图的顶点和弧，创建有向图的邻接表存储结构。参考答案：public static ALGraph createDG() Scanner sc = new Scanner(System.in);System.out.print

9、ln(请分别输入有向图的顶点数和边数：);int vexNum = sc.nextInt();int arcNum = sc.nextInt();425VNode vexs = new VNodevexNum;System.out.println( 请分别输入有向图的各个顶点:);for (int v = 0; v vexNum; v+)/ 构造顶点向量vexsv = new VNode(sc.next();ALGraph G = new ALGraph(GraphKind.DG, vexNum, arcNum, vexs);System.out.println( 请输入各个边的起点和终点:)

10、;for (int k = 0; k arcNum; k+) int v = G.locateVex(sc.next();int u = G.locateVex(sc.next();G.addArc(v, u, 0); return G;2 . 无向图采用邻接表存储结构，编写算法输出图中各连通分量的顶点序列。参考答案:public static void CC_BFS(IGraph G) throws Exception boolean visited = new booleanG .getVexNum();/ 访问标志数组for (int v = 0; v G.getVexNum(); v+

11、)/ 访问标志数组初始化visitedv = false;LinkQueue Q = new LinkQueue();/ 辅助队列QLinkQueue P = new LinkQueue();/辅助队列P用于记录连通分量的顶点int i = 0;/ 用于记数连通分量的个数for (int v = 0; v = 0; w = G.nextAdjVex(u, w) if (!visitedw) / w 为 u 的尚未访问的邻接顶点visitedw = true;P.offer(G.getVex(w);Q.offer(w); System.out.println( 图的第 + +i + 个连通分量为

12、：);while (!P.isEmpty()System.out.print(P.poll().toString() + );System.out.println();3 .编写算法判别以邻接表方式存储的无向图中是否存在由顶点u到顶点v的路径(uwv)。可以采用深度优先搜索遍历策略。当顶点u 和顶点 v 在无向图的同一连通分量中时，从顶点u到顶点 v 一定有路径，可从顶点u( v) 进行深度优先搜索，一定可以遍历至顶点v( u) 。 否则，遍历不能成功，不存在由顶点u 到顶点 v 的路径。参考答案:private boolean visited;/ 访问标志数组private boolean

13、find = false;/ 标示是否已找到了指定长度的路径public void findPath(IGraph G, int u, int v) throws Exception visited = new booleanG.getVexNum();for (int w = 0; w = 0; w = G.nextAdjVex(u, w)if (!visitedw)find_DFS(G, w, v);/ Xv的尚未访问的邻接顶点w递归调用find_DFS4 .编写算法求距离顶点 小的最短路径长度为K的所有顶点。参考答案：用迪杰斯特拉算法，当发现新顶点与顶点向的距离大于R时算法终止publi

14、c final static int INFINITY = Integer.MAX_VALUE;/用Dijkstra算法求vi顶点到其余顶点 v的最短长度Dv public void findVex_DIJ(MGraph G, int vi, int k) throws Exception int vexNum = G.getVexNum();int R = new intvexNum;/存放距离 vi距离为k的顶点int D = new intvexNum;/ vi到其余顶点的最短长度boolean isHaveVex = false;/ 记录是否存在距离到vi距离为k的点boolean口

15、finish = new booleanvexNum;for (int v = 0; v vexNum; v+) finishv = false;Rv = -1;Dv = G.getArcs()viv;Dvi = 0; 初始化，vi顶点属于S集finishvi = true;int v = -1;int j = 0;距离vi长度为k的点的增量/开始主循环，每次求得vi到某个v顶点的最短路径，并加 v到S集for (int i = 1; i vexNum; i+) / 其余 G.getVexNum-1 个顶点 int min = INFINITY;/当前所知离vi顶点的最近距离for (int

16、w = 0; w vexNum; w+) if (!finishw)if (Dw k)break;finishv = true;/ 离vi顶点最近的 v加入S集/更新当前最短路径及距离for (int w = 0; w vexNum; w+) if (!finishw & G.getArcs()vw INFINITY& (min + G.getArcs()vw Dw) / 修改 Dw和 Pw,w 属于 V-SDw = min + G.getArcs()vw;if (isHaveVex) System.out.println( 距离 vi 长度为 k 的顶点为：);for (int i = 0;

17、 i R.length; i+) if (Ri != -1)System.out.print(G.getVex(Ri) + t);else break;else System.out.println( 不存在距离vi 长度为 k 的顶点！);5 . 编写克鲁斯卡尔算法构造最小生成树。参考答案:public final static int INFINITY = Integer.MAX_VALUE;public static Object KRUSKAL (MGraph G) throws Exception Object tree = new ObjectG.getVexNum() - 12;

18、/ 存储最小生成树的边EqualClass A = new EqualClass(G);/ 等价类数组MinHeap H = new MinHeap (G);/ 用图 G 的边构造一个最小堆 int count = 0;while (count G.getVexNum() - 1) / 用 G.vexnum - 1 条边构成最小生成树Object vexs = H.removeMin();/ 取堆上最小边Object u = vexs0;Object v = vexs1;if (A.differ(u, v) / 如果u,v不在同一等价类中A.union(u, v);/ 合并到同一等价类tree

19、count0 = u;/ 生成树的边放入数组中treecount1 = v;count+; return tree;static class MinHeapNode private Object vexs;/ 边的两个顶点private int key;/ 边的权值public MinHeapNode(Object vexs, int key) this.vexs = vexs;this.key = key;public Object getVexs() return vexs;public int getKey() return key;static class MinHeap privat

20、e MinHeapNode heapArray; / 堆容器private int maxSize; / 堆得最大大小private int currentSize; / 堆大小public MinHeap(MGraph G) throws Exception maxSize = G.getVexNum() * G.getVexNum();heapArray = new MinHeapNodemaxSize;currentSize = 0;for (int i = 0; i G.getVexNum(); i+) for (int j = i + 1; j G.getVexNum(); j+)

21、Object vexs = G.getVex(i), G.getVex(j) ;MinHeapNode newNode = new MinHeapNode(vexs, G.getArcs()ij);insert(newNode);/ 自上而下调整public void filterDown(int start, int endOfHeap) int i = start;int j = 2 * i + 1;/ j是i的左子女位置MinHeapNode temp = heapArrayi;while (j = endOfHeap) / 检查是否到最后位置if (j heapArrayj + 1.g

22、etKey() j+;if (temp.getKey() 0) / 沿双亲结点路径向上直达根节点if (heapArrayi.getKey() = temp.getKey() / 双亲结点值小，不调整 break; else / 双亲结点值大，调整heapArrayj = heapArrayi;j = i;i = (i - 1) / 2;heapArrayj = temp; / 回送/ 堆中插入结点public void insert(MinHeapNode newNode) heapArraycurrentSize = newNode;filterUp(currentSize);curren

23、tSize+;/ 删除堆中的最小值public Object removeMin() MinHeapNode root = heapArray0;heapArray0 = heapArraycurrentSize - 1;currentSize-;filterDown(0, currentSize - 1);return root.getVexs();static class EqualClass private Object口 S; 存放已经选择过的顶点private Object口 V;/存放未选择的顶点EqualClass(MGraph G) S = new ObjectG.getVex

24、Num();V = new ObjectG.getVexNum();System.arraycopy(G.getVexs(), 0, V, 0, G.getVexs().length);public boolean differ(Object u, Object v) boolean isDiffer = false;int count = 0;for (int i = 0; i V.length; i+) if (Vi != null & (Vi.equals(u) 11Vi.equals(v) +count;if (count = 0 | count = 2) isDiffer = tru

25、e;return isDiffer;public void union(Object u, Object v) boolean isHaveU = false;/ u点是否已经被选择boolean isHaveV = false;int i = 0;for (; i d. exe的边数为;的边数为:参考答案：package ch06Exercise;import ch06.GenerateGraph;import ch06.MGraph;import ch06.ShortestPath_DIJ;public class Exercise5_2 private boolean川P; v0到其余顶

26、点的最短路径 ，若Pvw为true,则w是从v0至Uv当前求 得最短路径上的顶点private int口 D;/ v0到其余顶点的带权长度public final static int INFINITY = Integer.MAX_VALUE;/用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径Pv及其权值Dvpublic void DIJ(MGraph G, int v0) int vexNum = G.getVexNum();P = new booleanvexNumvexNum;D = new intvexNum;boolean finish = new booleanve

27、xNum; / finishv 为true当且仅当 v属于 S,即已经求得从V0到v的最短路径for (int v = 0; v vexNum; v+) finishv = false;Dv = G.getArcs()v0v;for (int w = 0; w vexNum; w+)Pvw = false;/ 设空路径if (Dv INFINITY) Pvv0 = true;Pvv = true;Dv0 = 0; 初始化，v0顶点属于S集finishv0 = true;int v = -1;/开始主循环，每次求得 v0到某个v顶点的最短路径，并加v到S集for (int i = 1; i vexNum; i+) / 其余 G.getVexNum-1 个顶点int min = INFINITY;/当前所知离v0顶点的最近距离for (int w = 0;