圖習題參考答案

1、習題六參考答案一、選擇題1. 在一個有個極點的有向圖中，若所有極點的出度之和為，則所有極點的人度之和為（A）。A.B.-1C.+1D.2. 一個有向圖有個極點，則每一個極點的度可能的最大值是（B）oA.n1B.2（n1）C.nD.2n3 .具有6個極點的無向圖至少應(yīng)有（A）條邊才能確保是一個連通圖。4 .一個有n個極點的無向圖最多有（C）條邊。A.nB.n（n1）C.n（n-1）/2D.2n5 .對某個無向圖的鄰接矩陣來講，下列敘述正確的是（A）。A.第i行上的非零元素個數(shù)和第i列上的非零元素個數(shù)必然相等B.矩陣中的非零元素個數(shù)等于圖中的邊數(shù)C.第i行與第i列上的非零元素的總數(shù)等于極點%的度數(shù)

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

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

4、有4 .如有向圖G的鄰接矩陣為:n -1條邊,最多有一%必%(01 01 °%10 11 1v201 01 1%00 00 1%1o0 10 0/n(n -1)/2 條邊。則極點做的入度是35 .對于一個有向圖，若一個極點的度為kl,出度為k2,則對應(yīng)逆鄰接表中該極點單鏈表中的邊結(jié)點數(shù)為kl一k2.6 .圖的遍歷算法BFS頂用到輔助隊列，每一個極點最多進隊1次。7 .在求最小生成樹的兩種算法中，克魯斯卡爾算法適合于稀疏圖。8 .數(shù)據(jù)結(jié)構(gòu)中的迪杰斯特拉算法是用來求某個源點到其余各極點的最短路徑。9 .除利用拓撲排序的方式，還有深度優(yōu)先搜索方式能夠判斷出一個有向圖是不是有回路。10 .在

5、用鄰接表表示圖時，拓撲排序算法的時刻復(fù)雜度為O(n+e),三、應(yīng)用題(1)每一個極點的出/入度:(2)鄰接矩陣；(3)鄰接表：(4)逆鄰接表。答：(1)每一個極點的出/入度是:出度入度1032223214315126321234561/00000021001003010001400101151000006110010)鄰接矩陣:鄰接表:(4)逆鄰接表:0123450123452.試對如圖所示的非連通圖，畫出其廣度優(yōu)先生成叢林。答:圖錯誤!文檔中沒有指定樣式的文字.非連通圖3.己知圖的鄰接矩陣如圖所示。試別離畫出自極點A動身進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。ABCDEFGHIJABC

6、/O00OOI000000000110001100000100D0010000100E0001000010FGHIJ010100100000100000101000100000000010001001001J10000/圖錯誤!文檔中沒有指定樣式的文字鄰接矩陣答:4.請對如圖所示的無向網(wǎng):(1)寫出它的鄰接矩陣，并按克魯斯卡爾算法求其最小生成樹:(2)寫出它的鄰接表，并按普里姆算法求其最小生成樹。圖錯誤!文檔中沒有指定樣式的文字.無向網(wǎng)ABCDEFGH43co004 3oooo05595 05co55079oo70cooo63cocosooco54oo克魯斯卡爾算法求其最小生成樹0123456

7、7©oo©A二DcHEBAD一普里姆算法求其最小生成樹,從A開始A5.試列出圖中全數(shù)可能的拓撲有序序列。ac圖有向圖答：abcdef>abcef、abecdfxbacdefxbacedf>baecdfbeacdf四、算法設(shè)計題1.編寫算法，從鍵盤讀入有向圖的極點和弧，創(chuàng)建有向圖的鄰接表存儲結(jié)構(gòu)。參考答案：publicstaticALGraphcreateDGOScannersc=newScanner;"請別離輸入有向圖的極點數(shù)和邊數(shù):")；intvexNum=();intarcNum=();VNodevexs=newVNodevexNum;&

8、quot;請別離輸入有向圖的各個極點門；for(intv=0;v<vexNum;v+)錯誤味定義書簽。H叫KqKetKey()>heapArrayj+l.getKey()j+；)if()<=hcapArrayfjJ.getKeyO)etKeyO<=()ength);)publicbooleandiffer(Objectu.Objectv)booleanisDiffer=false;intcount=0;for(inti=0;i<i+)if(Vi!=null&&(Vi.equals(u)IIVi.equals(v)+count;if(count=0I

9、Icount=2)isDiffer=true;returnisDiffer;)publicvoidunion(Objectu,Objectv)booleanisHaveU=false:quals(u)isHaveU=true;elseif(Si.equals(v)isHaveV=true;)if(JisHaveU)Si=u;if(JisHaveV)Si=v;)克魯斯卡爾算法只需取所有邊中知足條件的v-1條邊組成最小生成樹。因此可用最小堆存儲所有的邊，從最小堆上掏出知足條件的V-1條邊即可，其時刻復(fù)雜度接近最壞情形下也為°(山陪©)。另外，判斷新加入的邊是不是會形成回路，則可

10、轉(zhuǎn)化為判斷邊的兩個極點是不是在同一等價類中。五、上機實踐題1.在鄰接矩陣存儲結(jié)構(gòu)上實現(xiàn)圖的大體操作：InsertArc(Gvw),DeleteArc(Gv,w)o參考答案：packagechO6Exercise;import;import;publicclassExercise5_lpublicfinalstaticintINFINITY=;voidinsertArc(MGraphG,Objectv.Objectw,intP)intiv=(v);intiw=(w);intarcs=();arcsiviw=P：(arcs);()+1);)voiddeleteArc(MGraphGObjectv,

11、Objectw)intiv=(v);intiw=(w);arcs=();arcsiviw=INFINITY;(arcs);()-1)；publicstaticvoidmain(Stringargs)throwsExceptionObjectvexs=Mv0nv2Hv3M,Hv4Hv5,f);arcs=0.7,1,5,INFINITY.INFINITY),7,0,6,INFINITY,3JNFINITY),1,6,0,7,6,4,5,INFINITY.7,0,INFINITY.2,INFINITY,3,6,INFINITY,0,7,INFINITY.INFINITY.4,2,7,0);MGrap

12、hG=newMGraph,6.10.vexs.arcs);”修改前圖的邊數(shù)為：”+()；Exercise5_lexercise5_l=newExercise5_l();(Gnv0'HvlM);"刪除V0-V1邊后，圖的邊數(shù)為："+();(G7);"增加V0-V1邊后,圖的邊數(shù)為："+();)(1)求最短路徑的迪杰斯特拉算法。(2)設(shè)計一個測試主函數(shù)，使其實際運行來求從某個源點到其余各個極點的最短路徑。參考答案：packagechO6Exercise;import;import;import;publicclassExercise5_2(privatebooleanP：ength);Pww=true;publicint|getD()returnD;)publicbooleangctP()returnP:publicstaticvoidmain(Stringargs)th