圖習(xí)題參考答案

1、習(xí)題六參考答案一、選擇題J,則所有頂點(diǎn)的入度之和為（ A）。1 .在一個(gè)有個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度之和為A. 一BJ JI. C一 D.2 . 一個(gè)有向圖有1個(gè)頂點(diǎn)，則每個(gè)頂點(diǎn)的度可能的最大值是（ B）。A.iB.3 .具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有（A.5B.6C.74 . 一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有（A.B.如一1）C.D、A ）條邊才能確保是一個(gè)連通圖。D.8C ）條邊。C麻 L。庫(kù)D._5 .對(duì)某個(gè)無向圖的鄰接矩陣來說，下列敘述正確的是（ A）。a.第i行上的非零元素個(gè)數(shù)和第i列上的非零元素個(gè)數(shù)一定相等B.矩陣中的非零元素個(gè)數(shù)等于圖中的邊數(shù)c.第:行與第i列上的非零元素的總數(shù)

2、等于頂點(diǎn)辦的度數(shù)D.矩陣中非全零行的行數(shù)等于圖中的頂點(diǎn)數(shù)6 .已知一個(gè)有向圖的鄰接矩陣，要?jiǎng)h除所有以第：個(gè)頂點(diǎn)為孤尾的邊，應(yīng)該（B）。A.將鄰接矩陣的第1行刪除B.將鄰接矩陣的第i行元素全部置為0c.將鄰接矩陣的第！列刪除d.將鄰接矩陣的第i列元素全部置為07 .下面關(guān)于圖的存儲(chǔ)的敘述中，哪一個(gè)是正確的？（A）A.用鄰接矩陣存儲(chǔ)圖，占用的存儲(chǔ)空間只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無關(guān)B.用鄰接矩陣存儲(chǔ)圖，占用的存儲(chǔ)空間只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)數(shù)無關(guān)C.用鄰接表存儲(chǔ)圖，占用的存儲(chǔ)空間只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無關(guān)D.用鄰接表存儲(chǔ)圖，占用的存儲(chǔ)空間只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)數(shù)無關(guān)8 .對(duì)圖的深度優(yōu)先

3、遍歷，類似于又樹的哪種遍歷？（ A）A.先根遍歷B.中根遍歷C.后根遍歷D.層次遍歷9 .任何一個(gè)無向連通圖的最小生成樹（B）。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在10 .下面是三個(gè)關(guān)于有向圖運(yùn)算的敘述：(1)求兩個(gè)指向結(jié)點(diǎn)間的最短路徑，其結(jié)果必定是唯一的(2)求有向圖結(jié)點(diǎn)的拓?fù)湫蛄?，其結(jié)果必定是唯一的(3)求AOE網(wǎng)的關(guān)鍵路徑，其結(jié)果必定是唯一的其中哪個(gè)(些)是正確的？( D )A.只有(1)B. (1)和(2)C.都正確D.都不正確二、填空題1 .若用F表示圖中頂點(diǎn)數(shù)，則有-1)/2條邊的無向圖稱為完全圖。2 .若一個(gè)無向圖有100條邊，則其頂點(diǎn)總數(shù)最少為15個(gè)。3 .

4、個(gè)頂點(diǎn)的連通無向圖至少有 5一1 條邊，至多有 血一口條邊。4 .若有向圖(J的鄰接矩陣為：斯外。小心坨/01010均 10 111嗎01011叫0000100100/則頂點(diǎn)胃的入度是3 。5 .對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的度為H,出度為仁工 則對(duì)應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)為止顯。6 .圖的遍歷算法BFS中用到輔助隊(duì)列，每個(gè)頂點(diǎn)最多進(jìn)隊(duì)1次。7 .在求最小生成樹的兩種算法中，克魯斯卡爾算法適合于稀疏圖。8 .數(shù)據(jù)結(jié)構(gòu)中的迪杰斯特拉算法是用來求某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑。9 .除了使用拓?fù)渑判虻姆椒ǎ€有深度優(yōu)先搜索方法可以判斷出一個(gè)有向圖是否有回路。10 .在用鄰接表表示圖時(shí)，拓

5、撲排序算法的時(shí)間復(fù)雜度為JXn+吐。三、應(yīng)用題1 .已知如圖6.28所示的有向圖，請(qǐng)給出該圖的圖6.28 有向圖(1)每個(gè)頂點(diǎn)的出/入度;(2)鄰接矩陣；(3)鄰接表；(4)逆鄰接表。答：(1)每個(gè)頂點(diǎn)的出/入度是:出度入度103222321431512632(2)鄰接矩陣:so o o 1o 1 4 0 1-0000 3 0 0 0 10 011 /0230鄰接表:(4)逆鄰接表:0123450123451A2345612345630120A0121A3 A323A5A415A45A3A5A4A5A2 .試對(duì)如圖6.29所示的非連通圖，畫出其廣度優(yōu)先生成森林。答:.29 非連通圖M6.30所

6、示。試分別畫出自頂點(diǎn)3.已知圖的鄰接矩陣如圖A出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹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圖 錯(cuò)誤！文檔中沒有指定樣式的文字。.30鄰接矩陣答:4.請(qǐng)對(duì)如圖6.31所示的無向網(wǎng)：(1)寫出它的鄰接矩陣，并按克魯斯卡爾算法求其最小生成樹;

7、(2)寫出它的鄰接表，并按普里姆算法求其最小生成樹。答：圖錯(cuò)誤！文檔中沒有指定樣式的文字。.31無向網(wǎng)ABCDEfGH/043GO比800m40559mGOm3505;mCO5mS507654m90010360000cos6302DDGO005DO2060054OTw6EFE3EE33BF4BFBF44AD2ADA333CCC4HHE3BF4AD53CG4H5(2)3:A223 C012345E(D CD2 cz) %H克魯斯卡爾算法求其最小生成樹ABCD-I+EF67422 0GH21441531936-352523A253153253743523447553A62A76A66A49A75A

8、566574ABB45AAAD333CCCBB44B455ADADAD5333CGCC444HHHE3BF45AD53CG4Hacdfbe5.試列出圖6.32中全部可能的拓?fù)溆行蛐蛄?。四、算法設(shè)計(jì)題2普里姆算法求其最小生成樹，從A開始圖6.32 有向圖答：abcdef、abcef、abecdf、bacdef、bacedf、baecdf、beacdf1.編寫算法，從鍵盤讀入有向圖的頂點(diǎn)和弧，創(chuàng)建有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)。參考答案：public static ALGraph createDG() Scanner sc = new Scanner(System.in);System.out.print

9、ln(請(qǐng)分別輸入有向圖的頂點(diǎn)數(shù)和邊數(shù)：);int vexNum = sc.nextInt();int arcNum = sc.nextInt();425VNode vexs = new VNodevexNum;System.out.println( 請(qǐng)分別輸入有向圖的各個(gè)頂點(diǎn):);for (int v = 0; v vexNum; v+)/ 構(gòu)造頂點(diǎn)向量vexsv = new VNode(sc.next();ALGraph G = new ALGraph(GraphKind.DG, vexNum, arcNum, vexs);System.out.println( 請(qǐng)輸入各個(gè)邊的起點(diǎn)和終點(diǎn):)

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 . 無向圖采用鄰接表存儲(chǔ)結(jié)構(gòu)，編寫算法輸出圖中各連通分量的頂點(diǎn)序列。參考答案:public static void CC_BFS(IGraph G) throws Exception boolean visited = new booleanG .getVexNum();/ 訪問標(biāo)志數(shù)組for (int v = 0; v G.getVexNum(); v+

11、)/ 訪問標(biāo)志數(shù)組初始化visitedv = false;LinkQueue Q = new LinkQueue();/ 輔助隊(duì)列QLinkQueue P = new LinkQueue();/輔助隊(duì)列P用于記錄連通分量的頂點(diǎn)int i = 0;/ 用于記數(shù)連通分量的個(gè)數(shù)for (int v = 0; v = 0; w = G.nextAdjVex(u, w) if (!visitedw) / w 為 u 的尚未訪問的鄰接頂點(diǎn)visitedw = true;P.offer(G.getVex(w);Q.offer(w); System.out.println( 圖的第 + +i + 個(gè)連通分量為

12、：);while (!P.isEmpty()System.out.print(P.poll().toString() + );System.out.println();3 .編寫算法判別以鄰接表方式存儲(chǔ)的無向圖中是否存在由頂點(diǎn)u到頂點(diǎn)v的路徑(uwv)。可以采用深度優(yōu)先搜索遍歷策略。當(dāng)頂點(diǎn)u 和頂點(diǎn) v 在無向圖的同一連通分量中時(shí)，從頂點(diǎn)u到頂點(diǎn) v 一定有路徑，可從頂點(diǎn)u( v) 進(jìn)行深度優(yōu)先搜索，一定可以遍歷至頂點(diǎn)v( u) 。 否則，遍歷不能成功，不存在由頂點(diǎn)u 到頂點(diǎn) v 的路徑。參考答案:private boolean visited;/ 訪問標(biāo)志數(shù)組private boolean

13、find = false;/ 標(biāo)示是否已找到了指定長(zhǎng)度的路徑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的尚未訪問的鄰接頂點(diǎn)w遞歸調(diào)用find_DFS4 .編寫算法求距離頂點(diǎn) 小的最短路徑長(zhǎng)度為K的所有頂點(diǎn)。參考答案：用迪杰斯特拉算法，當(dāng)發(fā)現(xiàn)新頂點(diǎn)與頂點(diǎn)向的距離大于R時(shí)算法終止publi

14、c final static int INFINITY = Integer.MAX_VALUE;/用Dijkstra算法求vi頂點(diǎn)到其余頂點(diǎn) v的最短長(zhǎng)度Dv public void findVex_DIJ(MGraph G, int vi, int k) throws Exception int vexNum = G.getVexNum();int R = new intvexNum;/存放距離 vi距離為k的頂點(diǎn)int D = new intvexNum;/ vi到其余頂點(diǎn)的最短長(zhǎng)度boolean isHaveVex = false;/ 記錄是否存在距離到vi距離為k的點(diǎn)boolean口

15、finish = new booleanvexNum;for (int v = 0; v vexNum; v+) finishv = false;Rv = -1;Dv = G.getArcs()viv;Dvi = 0; 初始化，vi頂點(diǎn)屬于S集finishvi = true;int v = -1;int j = 0;距離vi長(zhǎng)度為k的點(diǎn)的增量/開始主循環(huán)，每次求得vi到某個(gè)v頂點(diǎn)的最短路徑，并加 v到S集for (int i = 1; i vexNum; i+) / 其余 G.getVexNum-1 個(gè)頂點(diǎn) int min = INFINITY;/當(dāng)前所知離vi頂點(diǎn)的最近距離for (int

16、w = 0; w vexNum; w+) if (!finishw)if (Dw k)break;finishv = true;/ 離vi頂點(diǎn)最近的 v加入S集/更新當(dāng)前最短路徑及距離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 長(zhǎng)度為 k 的頂點(diǎn)為：);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 長(zhǎng)度為 k 的頂點(diǎn)！);5 . 編寫克魯斯卡爾算法構(gòu)造最小生成樹。參考答案:public final static int INFINITY = Integer.MAX_VALUE;public static Object KRUSKAL (MGraph G) throws Exception Object tree = new ObjectG.getVexNum() - 12;

18、/ 存儲(chǔ)最小生成樹的邊EqualClass A = new EqualClass(G);/ 等價(jià)類數(shù)組MinHeap H = new MinHeap (G);/ 用圖 G 的邊構(gòu)造一個(gè)最小堆 int count = 0;while (count G.getVexNum() - 1) / 用 G.vexnum - 1 條邊構(gòu)成最小生成樹Object vexs = H.removeMin();/ 取堆上最小邊Object u = vexs0;Object v = vexs1;if (A.differ(u, v) / 如果u,v不在同一等價(jià)類中A.union(u, v);/ 合并到同一等價(jià)類tree

19、count0 = u;/ 生成樹的邊放入數(shù)組中treecount1 = v;count+; return tree;static class MinHeapNode private Object vexs;/ 邊的兩個(gè)頂點(diǎn)private int key;/ 邊的權(quán)值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);/ 自上而下調(diào)整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) / 沿雙親結(jié)點(diǎn)路徑向上直達(dá)根節(jié)點(diǎn)if (heapArrayi.getKey() = temp.getKey() / 雙親結(jié)點(diǎn)值小，不調(diào)整 break; else / 雙親結(jié)點(diǎn)值大，調(diào)整heapArrayj = heapArrayi;j = i;i = (i - 1) / 2;heapArrayj = temp; / 回送/ 堆中插入結(jié)點(diǎn)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; 存放已經(jīng)選擇過的頂點(diǎn)private Object口 V;/存放未選擇的頂點(diǎn)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點(diǎn)是否已經(jīng)被選擇boolean isHaveV = false;int i = 0;for (; i d. exe的邊數(shù)為;的邊數(shù)為:參考答案：package ch06Exercise;import ch06.GenerateGraph;import ch06.MGraph;import ch06.ShortestPath_DIJ;public class Exercise5_2 private boolean川P; v0到其余頂

26、點(diǎn)的最短路徑 ，若Pvw為true,則w是從v0至Uv當(dāng)前求 得最短路徑上的頂點(diǎn)private int口 D;/ v0到其余頂點(diǎn)的帶權(quán)長(zhǎng)度public final static int INFINITY = Integer.MAX_VALUE;/用Dijkstra算法求有向網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑Pv及其權(quán)值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當(dāng)且僅當(dāng) v屬于 S,即已經(jīng)求得從V0到v的最短路徑for (int v = 0; v vexNum; v+) finishv = false;Dv = G.getArcs()v0v;for (int w = 0; w vexNum; w+)Pvw = false;/ 設(shè)空路徑if (Dv INFINITY) Pvv0 = true;Pvv = true;Dv0 = 0; 初始化，v0頂點(diǎn)屬于S集finishv0 = true;int v = -1;/開始主循環(huán)，每次求得 v0到某個(gè)v頂點(diǎn)的最短路徑，并加v到S集for (int i = 1; i vexNum; i+) / 其余 G.getVexNum-1 個(gè)頂點(diǎn)int min = INFINITY;/當(dāng)前所知離v0頂點(diǎn)的最近距離for (int w = 0;