2023年圖習題參考答案

習題六參考答案一、選擇題在一個有n個頂點的有向圖中，若所有頂點的出度之和為s，則所有頂點的入度之和為（A）。A.sB.s-1C.s一個有向圖有n個頂點，則每個頂點的度也許的最大值是（B）。A.n-1B.2(n-1)C.nD.2n具有6個頂點的無向圖至少應有（A）條邊才干保證是一個連通圖。A.5B.6C.7D.8一個有n個頂點的無向圖最多有（C）條邊。A.nB.nn-1C.對某個無向圖的鄰接矩陣來說，下列敘述對的的是（A）。A.第i行上的非零元素個數(shù)和第i列上的非零元素個數(shù)一定相等B.矩陣中的非零元素個數(shù)等于圖中的邊數(shù)C.第i行與第i列上的非零元素的總數(shù)等于頂點viD.矩陣中非全零行的行數(shù)等于圖中的頂點數(shù)已知一個有向圖的鄰接矩陣，要刪除所有以第i個頂點為孤尾的邊，應當（B）。A.將鄰接矩陣的第i行刪除B.將鄰接矩陣的第i行元素所有置為0C.將鄰接矩陣的第i列刪除D.將鄰接矩陣的第i列元素所有置為0下面關于圖的存儲的敘述中，哪一個是對的的？……（A）A．用鄰接矩陣存儲圖，占用的存儲空間只與圖中頂點數(shù)有關，而與邊數(shù)無關B．用鄰接矩陣存儲圖，占用的存儲空間只與圖中邊數(shù)有關，而與頂點數(shù)無關C．用鄰接表存儲圖，占用的存儲空間只與圖中頂點數(shù)有關，而與邊數(shù)無關D．用鄰接表存儲圖，占用的存儲空間只與圖中邊數(shù)有關，而與頂點數(shù)無關對圖的深度優(yōu)先遍歷，類似于對樹的哪種遍歷？……（A）A.先根遍歷B.中根遍歷C．后根遍歷D．層次遍歷任何一個無向連通圖的最小生成樹（B）。A.只有一棵B.有一棵或多棵C.一定有多棵D.也許不存在下面是三個關于有向圖運算的敘述：（1）求兩個指向結點間的最短途徑，其結果必然是唯一的（2）求有向圖結點的拓撲序列，其結果必然是唯一的（3）求AOE網(wǎng)的關鍵途徑，其結果必然是唯一的其中哪個（些）是對的的？……（D）A.只有（1）B.（1）和（2）C.都對的D.都不對的二、填空題若用n表達圖中頂點數(shù)，則有nn-若一個無向圖有100條邊，則其頂點總數(shù)最少為15個。n個頂點的連通無向圖至少有n-1條邊，至多有n若有向圖G的鄰接矩陣為：v則頂點v4的入度是3對于一個有向圖，若一個頂點的度為k1，出度為k2，則相應逆鄰接表中該頂點單鏈表中的邊結點數(shù)為k1-k2圖的遍歷算法BFS中用到輔助隊列，每個頂點最多進隊1次。在求最小生成樹的兩種算法中，克魯斯卡爾算法適合于稀疏圖。數(shù)據(jù)結構中的迪杰斯特拉算法是用來求某個源點到其余各頂點的最短途徑。除了使用拓撲排序的方法，尚有深度優(yōu)先搜索方法可以判斷出一個有向圖是否有回路。在用鄰接表表達圖時，拓撲排序算法的時間復雜度為On+e三、應用題已知如圖6.28所示的有向圖，請給出該圖的123123456圖6.28有向圖(1)每個頂點的出/入度；(2)鄰接矩陣；(3)鄰接表；(4)逆鄰接表。答：(1)每個頂點的出/入度是：出度入度103222321431512632(2)鄰接矩陣：(3)鄰接表：4401231234Λ503Λ124565Λ5Λ0Λ014Λ(4)逆鄰接表：4401231234525Λ3Λ1Λ56323Λ145Λ5Λ試對如圖6.29所示的非連通圖，畫出其廣度優(yōu)先生成森林。圖圖STYLEREF1\s6.29非連通圖GIKHEDACFBLJM答：GGIKHEDACFBLJM已知圖的鄰接矩陣如圖6.30所示。試分別畫出自頂點A出發(fā)進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。A圖圖STYLEREF1\s6.30鄰接矩陣答：IHEIHEDABFGJCIHDABFGJCE請對如圖6.31所示的無向網(wǎng)：(1)寫出它的鄰接矩陣，并按克魯斯卡爾算法求其最小生成樹；(2)寫出它的鄰接表，并按普里姆算法求其最小生成樹。5534655圖STYLEREF1\s6.31無向網(wǎng)5437ABEFDC9GH526答：(1)A克魯斯卡爾算法求其最小生成樹克魯斯卡爾算法求其最小生成樹ABEFDCGH23ABEFDCGH23ABEFDCGH23343ABEFDCGH23443ABEFDCGH234543ABEFDCGH234543ABEFDC9GH52(2)AABCD0123EFGH456714Λ32042535Λ941525475665Λ47031535Λ571937Λ353643Λ263552Λ672534Λ66普里姆算法求其最小生成樹普里姆算法求其最小生成樹，從A開始3ABEFDCGH43ABEFDCGH543ABEFDCGH4543ABEFDCGH4543ABEFDCGH54543ABEFDCGH5234543ABEFDCGH52試列出圖6.32中所有也許的拓撲有序序列。aabce圖6.32有向圖fd答：abcdef、abcef、abecdf、bacdef、bacedf、baecdf、beacdf四、算法設計題編寫算法，從鍵盤讀入有向圖的頂點和弧，創(chuàng)建有向圖的鄰接表存儲結構。參考答案:publicstaticALGraphcreateDG(){ Scannersc=newScanner(System.in); System.out.println("請分別輸入有向圖的頂點數(shù)和邊數(shù):"); intvexNum=sc.nextInt(); intarcNum=sc.nextInt(); VNode[]vexs=newVNode[vexNum]; System.out.println("請分別輸入有向圖的各個頂點:"); for(intv=0;v<vexNum;v++) //構造頂點向量 vexs[v]=newVNode(sc.next()); ALGraphG=newALGraph(GraphKind.DG,vexNum,arcNum,vexs); System.out.println("請輸入各個邊的起點和終點:"); for(intk=0;k<arcNum;k++){ intv=G.locateVex(sc.next()); intu=G.locateVex(sc.next()); G.addArc(v,u,0); } returnG; }無向圖采用鄰接表存儲結構，編寫算法輸出圖中各連通分量的頂點序列。參考答案:publicstaticvoidCC_BFS(IGraphG)throwsException{ boolean[]visited=newboolean[G.getVexNum()];//訪問標志數(shù)組 for(intv=0;v<G.getVexNum();v++) //訪問標志數(shù)組初始化 visited[v]=false; LinkQueueQ=newLinkQueue();//輔助隊列Q LinkQueueP=newLinkQueue();//輔助隊列P,用于記錄連通分量的頂點 inti=0;//用于記數(shù)連通分量的個數(shù) for(intv=0;v<G.getVexNum();v++){ P.clear();//隊列清空 if(!visited[v]){//v尚未訪問 visited[v]=true; P.offer(G.getVex(v)); Q.offer(v);//v入隊列 while(!Q.isEmpty()){ intu=(Integer)Q.poll();//隊頭元素出隊列并賦值給u for(intw=G.firstAdjVex(u);w>=0;w=G.nextAdjVex(u, w)){ if(!visited[w]){//w為u的尚未訪問的鄰接頂點 visited[w]=true; P.offer(G.getVex(w)); Q.offer(w); } } } System.out.println("圖的第"+++i+"個連通分量為："); while(!P.isEmpty()) System.out.print(P.poll().toString()+""); System.out.println(); } } }編寫算法判別以鄰接表方式存儲的無向圖中是否存在由頂點QUOTEuu到頂點v的途徑（QUOTEu≠vu≠v）?？梢圆捎蒙疃葍?yōu)先搜索遍歷策略。當頂點u和頂點v在無向圖的同一連通分量中時，從頂點u到頂點v一定有途徑，可從頂點u（v）進行深度優(yōu)先搜索，一定可以遍歷至頂點v（u）。否則，遍歷不能成功，不存在由頂點u到頂點v的途徑。參考答案: privateboolean[]visited;//訪問標志數(shù)組 privatebooleanfind=false;//標示是否已找到了指定長度的途徑 publicvoidfindPath(IGraphG,intu,intv)throwsException{ visited=newboolean[G.getVexNum()]; for(intw=0;w<G.getVexNum();w++) //訪問標志數(shù)組初始化 visited[w]=false; find_DFS(G,u,v); if(find) System.out.println(G.getVex(u)+"和"+G.getVex(v)+"之間至少存在一條途徑！"); else System.out.println(G.getVex(u)+"和"+G.getVex(v)+"之間不存在途徑！"); } privatevoidfind_DFS(IGraphG,intu,intv)thro