單元5一、選擇題12345ABCAA678910ADCDB1112131415ACBAB16A二、簡答題1．答：=1\*GB3①是強(qiáng)連通圖。=2\*GB3②ID(A)=1,OD(A)=2,ID(B)=1,OD(B)=1,ID(C)=1,OD(C)=1,ID(D)=2,OD(D)=1.2．答：n個頂點(diǎn)的無向圖n個頂點(diǎn)的有向圖問題11的個數(shù)除以2非0非無窮的數(shù)值個數(shù)問題2A[i][j]或A[j][i]是否為1A[i][j]或A[j][i]是否非0非無窮問題3第i行或第i列1的個數(shù)第i行非0非無窮的數(shù)值個數(shù)為其出度，第i列非0非無窮的數(shù)值個數(shù)為其入度3．深度優(yōu)先遍歷：頂點(diǎn)序列ABCDEF邊的序列(A,B)(B,C)(C,D)(D,E)(E,F)廣度優(yōu)先遍歷：頂點(diǎn)序列ABCFED邊的序列(A,B)(A,C)(A,F)(A,E)(B,D)4．答：用Prim和Kruskal求最小生成樹的時間復(fù)雜度分別為O(n2)和O(elge),前者適合于稠密圖，后者適合于稀疏圖。5．答：最小生成樹如下圖所示。6．答:最短路徑如下圖所示。三、算法設(shè)計題1.publicclassExample{ staticfinalintmaxWeight=10000;//權(quán)值無窮大 publicstaticvoidcreateGraph(AMGraphg,Object[]v,intn,Edge[]edge,inte)throwsException{ //構(gòu)建有向圖 for(intk=0;k<n;k++){ g.insertVertex(v[k]); } for(intk=0;k<e;k++){ g.insertEdge(edge[k].i,edge[k].j,edge[k].weight); } } publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub intn=7,e=11; AMGraphg=newAMGraph(n); Character[]v={'A','B','C','D','E','F','G'}; Edge[]edge={newEdge(0,1,4), newEdge(0,2,5),newEdge(1,3,1), newEdge(1,4,2),newEdge(3,0,2), newEdge(3,2,8),newEdge(3,6,2), newEdge(4,3,3),newEdge(4,6,10), newEdge(5,2,1),newEdge(6,5,8) }; try{ createGraph(g,v,n,edge,e); int[]inDegree=newint[n]; int[][]matrix=g.getMatrix(); for(inti=0;i<matrix.length;i++){ for(intj=0;j<matrix.length;j++){ if(matrix[j][i]>0&&matrix[j][i]<maxWeight){ inDegree[i]++; } } } System.out.print("各頂點(diǎn)的出度為："); for(inti=0;i<inDegree.length;i++){ System.out.println(inDegree[i]+"\t"); } }catch(Exceptione1){ //TODOAuto-generatedcatchblock e1.printStackTrace(); } }}2.publicclassExample{ staticfinalintmaxWeight=10000;//權(quán)值無窮大 publicstaticvoidcreateGraph(AMGraphg,Object[]v,intn,Edge[]edge,inte)throwsException{ //構(gòu)建有向圖 for(intk=0;k<n;k++){ g.insertVertex(v[k]); } for(intk=0;k<e;k++){ g.insertEdge(edge[k].i,edge[k].j,edge[k].weight); } } publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub intn=7,e=11; AMGraphg=newAMGraph(n); Character[]v={'A','B','C','D','E','F','G'}; Edge[]edge={newEdge(0,1,4), newEdge(0,2,5),newEdge(1,3,1), newEdge(1,4,2),newEdge(3,0,2), newEdge(3,2,8),newEdge(3,6,2), newEdge(4,3,3),newEdge(4,6,10), newEdge(5,2,1),newEdge(6,5,8) }; try{ createGraph(g,v,n,edge,e); int[]outDegree=newint[n]; int[][]matrix=g.getMatrix(); for(inti=0;i<matrix.length;i++){ for(intj=0;j<matrix.length;j++){ if(matrix[i][j]>0&&matrix[i][j]<maxWeight){ outDegree[i]++; } } } System.out.print("各頂點(diǎn)的出度為："); for(inti=0;i<outDegree.length;i++){ System.out.println(outDegree[i]+"\t"); } }catch(Exceptione1){ //TODOAuto-generatedcatchblock e1.printStackTrace(); } }}3.importjava.util.LinkedList;importjava.util.Queue;//計算島嶼數(shù)量的類publicclassIslandCount{//計算島嶼數(shù)量的方法，接收一個二維字符矩陣作為參數(shù)publicstaticintnumIslands(char[][]grid){//如果輸入的網(wǎng)格為空、行數(shù)為0或者列數(shù)為0，則沒有島嶼，返回0if(grid==null||grid.length==0||grid[0].length==0){return0;}introws=grid.length;//獲取網(wǎng)格的行數(shù)intcols=grid[0].length;//獲取網(wǎng)格的列數(shù)intcount=0;//用于記錄島嶼的數(shù)量，初始化為0//遍歷二維矩陣的每一個元素for(inti=0;i<rows;i++){for(intj=0;j<cols;j++){if(grid[i][j]=='1'){//當(dāng)遇到陸地（值為1）時，表示發(fā)現(xiàn)一個新的島嶼//調(diào)用bfs方法進(jìn)行廣度優(yōu)先搜索，標(biāo)記所有與該陸地相連的陸地bfs(grid,i,j);count++;//島嶼數(shù)量加1}}}returncount;//返回島嶼的總數(shù)}//廣度優(yōu)先搜索方法，用于標(biāo)記與給定坐標(biāo)相連的所有陸地privatestaticvoidbfs(char[][]grid,introw,intcol){int[]dx={-1,0,1,0};//x方向的偏移量，用于表示上下左右四個方向int[]dy={0,1,0,-1};//y方向的偏移量，用于表示上下左右四個方向Queue<int[]>queue=newLinkedList<>();//創(chuàng)建一個整數(shù)數(shù)組隊列，用于存儲待訪問的坐標(biāo)queue.add(newint[]{row,col});//將起始坐標(biāo)加入隊列//將當(dāng)前陸地標(biāo)記為已訪問（這里標(biāo)記為2，避免重復(fù)訪問）grid[row][col]='2';while(!queue.isEmpty()){int[]curr=queue.poll();//取出隊列頭部的坐標(biāo)intx=curr[0];inty=curr[1];//遍歷四個方向for(intk=0;k<4;k++){intnewX=x+dx[k];//計算新的x坐標(biāo)intnewY=y+dy[k];//計算新的y坐標(biāo)//判斷新坐標(biāo)是否在網(wǎng)格范圍內(nèi)且對應(yīng)的值為陸地（1）if(newX>=0&&newX<grid.length&&newY>=0&&newY<grid[0].length&&grid[newX][newY]=='1'){//將新的陸地坐標(biāo)加入隊列queue.add(newint[]{newX,newY});//將新訪問的陸地標(biāo)記為已訪問grid[newX][newY]='2';}}}}publicstaticvoidmain(String[]args){char[][]grid={{'1','1','0','0','0'},