圖習題參考答案

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行上的非零元素個數(shù)和第i列上的非零元素個數(shù)一定相等B.矩陣中的非零元素個數(shù)等于圖中的邊數(shù)c.第:行與第i列上的非零元素的總數(shù)

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

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

4、個頂點的連通無向圖至少有 5一1 條邊，至多有 血一口條邊。4 .若有向圖(J的鄰接矩陣為：斯外。小心坨/01010均 10 111嗎01011叫0000100100/則頂點胃的入度是3 。5 .對于一個有向圖，若一個頂點的度為H,出度為仁工 則對應逆鄰接表中該頂點單鏈表中的邊結點數(shù)為止顯。6 .圖的遍歷算法BFS中用到輔助隊列，每個頂點最多進隊1次。7 .在求最小生成樹的兩種算法中，克魯斯卡爾算法適合于稀疏圖。8 .數(shù)據(jù)結構中的迪杰斯特拉算法是用來求某個源點到其余各頂點的最短路徑。9 .除了使用拓撲排序的方法，還有深度優(yōu)先搜索方法可以判斷出一個有向圖是否有回路。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所示的非連通圖，畫出其廣度優(yōu)先生成森林。答:.29 非連通圖M6.30所

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

7、(2)寫出它的鄰接表，并按普里姆算法求其最小生成樹。答：圖錯誤！文檔中沒有指定樣式的文字。.31無向網(wǎng)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.編寫算法，從鍵盤讀入有向圖的頂點和弧，創(chuàng)建有向圖的鄰接表存儲結構。參考答案：public static ALGraph createDG() Scanner sc = new Scanner(System.in);System.out.print

9、ln(請分別輸入有向圖的頂點數(shù)和邊數(shù)：);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();/ 訪問標志數(shù)組for (int v = 0; v G.getVexNum(); v+

11、)/ 訪問標志數(shù)組初始化visitedv = false;LinkQueue Q = new LinkQueue();/ 輔助隊列QLinkQueue P = new LinkQueue();/輔助隊列P用于記錄連通分量的頂點int i = 0;/ 用于記數(shù)連通分量的個數(shù)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)?？梢圆捎蒙疃葍?yōu)先搜索遍歷策略。當頂點u 和頂點 v 在無向圖的同一連通分量中時，從頂點u到頂點 v 一定有路徑，可從頂點u( v) 進行深度優(yōu)先搜索，一定可以遍歷至頂點v( u) 。 否則，遍歷不能成功，不存在由頂點u 到頂點 v 的路徑。參考答案:private boolean visited;/ 訪問標志數(shù)組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遞歸調(diào)用find_DFS4 .編寫算法求距離頂點 小的最短路徑長度為K的所有頂點。參考答案：用迪杰斯特拉算法，當發(fā)現(xiàn)新頂點與頂點向的距離大于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的點的增量/開始主循環(huán)，每次求得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);/ 等價類數(shù)組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;/ 生成樹的邊放入數(shù)組中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);/ 自上而下調(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é)點if (heapArrayi.getKey() = temp.getKey() / 雙親結點值小，不調(diào)整 break; else / 雙親結點值大，調(diào)整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; 存放已經(jīng)選擇過的頂點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點是否已經(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、點的最短路徑 ，若Pvw為true,則w是從v0至Uv當前求 得最短路徑上的頂點private int口 D;/ v0到其余頂點的帶權長度public final static int INFINITY = Integer.MAX_VALUE;/用Dijkstra算法求有向網(wǎng)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,即已經(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;/ 設空路徑if (Dv INFINITY) Pvv0 = true;Pvv = true;Dv0 = 0; 初始化，v0頂點屬于S集finishv0 = true;int v = -1;/開始主循環(huán)，每次求得 v0到某個v頂點的最短路徑，并加v到S集for (int i = 1; i vexNum; i+) / 其余 G.getVexNum-1 個頂點int min = INFINITY;/當前所知離v0頂點的最近距離for (int w = 0;