第六次作業一、選擇題1、深度優先遍歷類似與二叉樹的 A： A.先根遍歷B,中根遍歷C.后根遍歷D,層次遍歷2、廣度優先遍歷類似與二叉樹的 D： A.先根遍歷B.中根遍歷C.后根遍歷D,層次遍歷3、下列關于開放樹(FreeTree)的說法錯誤的是 C：A.具有n個結點的開放樹包含n-1條邊B.開放樹沒有回路 C.開放樹可以是非連通圖D.在開放樹中任意加一條邊，一定會產生回路4、關于最小生成樹，下列說法錯誤的是C：A.最小生成樹是一棵開放樹B.最小生成樹各邊的和是所有生成樹中最小的C.任何圖都只有一個最小生成樹D,能夠產生最小生成樹的圖，其邊一定有權值5、任何一個無向連通圖的最小生成樹 B：A,只有1棵B,1棵或多棵C.一定有多棵D,可能不存在6、在如下圖所示的圖中，從頂點a出發，按深度優先遍歷，則可能得到的一種頂點的序列為A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,bA.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b7、在如上圖所示的圖中，從頂點a出發，按廣度優先遍歷，則可能得到的一種頂點的序列為A。A.a,b,e,c,d,fB.a,b,e,c,f,dC.a,e,b,c,f,dD.a,e,d,f,c,b8、設網(帶權的圖)有n個頂點和e條邊，則采用鄰接表存儲時，求最小生成樹的Prim算法的時間復雜度為CC。 23A.O(n)B,O(n+e)C.O(n)D,O(n)9、設圖有n個頂點和e條邊，求解最短路徑的Floyd算法的時間復雜度為D。 23A.O(n)B,O(n+e)C.O(n)D,O(n)10、最小生成樹是指C。A.由連通網所得到的邊數最少的生成樹。B.由連通網所得到的頂點數相對較少的生成樹。C.連通網中所有生成樹中權值之和為最小的生成樹。D.連通網的極小連通子圖。11、下面關于工程計劃的AOE網的敘述中，不正確的是B。 A.關鍵活動不按期完成就會影響整個工程的完成時間。B.任何一個關鍵活動提前完成，那么整個工程將會提前完成。C.所有關鍵活動都提前完成，那么整個工程將會提前完成。D.某些關鍵工程若提前完成，那么整個工程將會提前完成。12、在AOE網中，始點和匯點的個數為DA.1個始點，若干個匯點B.若干個始點，若干個匯點C.若干個始點，1個匯點D.1個始點，1個匯點13、在下圖所示的無向圖中，從頂點^開始采用Prim算法生成最小生成樹，算法過程中產生的頂點次序為B。A.v1,v3,v4,v2,v5,v6B.v1,v3,v6,v2,v5,v4C.v1,v2,v3,v4,v5,v6D.v1,v3,v6,v4,v2,v514、在整理范本上圖所示的途中，采用6「央卜如算法生成最小生成樹，過程中產生的邊的次序是C。A.(v1,v2),(v2,v3),(v5,v6),(v1,v5)B.(v1,v3),(v2,v6),(v2,v5),(v1,v4)C.(v1,v3),(v2,v5),(v3,v6),(v4,v5)D.(v2,v5),(v1,v3),(v5,v6),(v4,v5)15、如下圖所示的圖中，其中一個拓撲排序的結果是A。A.v1*v2*v3*v6*v4*v5*v7*v8B.v1*v2*v3*v4*v5*v6*v7*v8C.v1*v6*v4*v5*v2*v3*v7*v8D.v1*v6*v2*v3*v7*v8*v4*v516、在下圖所示的AOE網中，活動a9的最早開始時間為B。A.13B.14C.15D.16 17、在上圖所示的AOE網中，活動a4的最遲開始時間為DA.4B.5C.6D.7二、填空題1、圖的遍歷有深度優先遍歷和廣度優先遍歷等方法。2、在深度優先搜索和廣度優先搜索中，都采用司虹?g]=false的方式設置第i個頂點為小卬，而采用水送4國=true的方式標識第i個結點為。也。3、由于深度優先算法的特點，深度優先往往采用遞歸的方式實現。4、由于廣度優先算法的特點，在廣度優先實現過程中，往往要借助于另一種數據結構 隊列實現。5、在深度優先搜索和廣度優先搜索中，在搜索過程中所經過的邊都稱為樹邊。6、連通而且無環路的無向圖稱為開放樹 。7、對于含有n個頂點。條邊的連通圖，利用Prim算法求其最小生成樹的時間復雜度為 2O(n)利用Kruscal算法求最小生成樹的時間復雜度是O(n)8、頂點表示活動的網簡稱為 AOV；邊表示活動的網簡稱為AOE。 9、一個含有n個頂點的無向連通圖，其整理范本每條邊的權重都是a(a>0),則其最小生成樹的權重等于(n-1)*a 。三、已知一個連通圖如下圖所示，分別給出一個按深度優先遍歷和廣度優先遍歷的頂點序列(假設從頂點^出發)。并編程分別實現該圖的鄰接矩陣表示和鄰接表表示，要求編寫相關基本操作，并在主函數中求出深度優先序列和廣度優先序列。v1v2v3v4v5v6010101v1101110v20100 10v3 110 011v401 1100v510010 0v6HEADv1 v2v4v6八v2v1v3v4v5八v3v2v5人v4v1v2v5v6人v5v2v3v4人v6v1v4人 深度優先：v1v2v3v5v4v6廣度優先：v1v2v4v6v3v5#include<iostream>#include<string>usingnamespacestd;typedefcharVertexData;typedefintEdgeData;typedefstructnode{intadjvex;EdgeDatacost;structnode*next;}EdgeNode;typedefstruct{VertexDatavertex;EdgeNode*firstedge;}VertexNode;typedefstruct{VertexNodevexlist[NumVertices+1];intn,e;}AdjGraph;//鄰接表表示BOOLEANvisited[NumVertices];intdfn[NumVertices];//深度優先voidDFSTraverse(AdjGraphG){inti,count=1;for(i=0;i<G.n;i++)visited[i]=FALSE;for(i=0;i<G.n;i++)if(!visited[i])DFS1(&G,i+1);}voidDFS1(AdjGraph*G,inti){staticintcount=0;EdgeNode*p;cout<<G->vexlist[i].vertex;visited[i]=TRUE;dfn[i]=count++;p=G->vexlist[i].firstedge;while(1){if(!visited[p->adjvex])DFS1(G,p->adjvex);p=p->next;if(p==NULL)break;}}intbfn[NumVertices];//廣度優先voidBFS1(AdjGraph*G,intk){EdgeNode*p;QUEUEQ;MAKENULL(Q);cout<<G->vexlist[k].vertex;visited[k]=true;整理范本ENQUEUE(k,Q);while(!EMPTY(Q)){i=FRONT(Q)->element;DEQUEUE(Q); p=G->vexlist[i].firstedge;while(p){if(!visited[p->adjvex]){ cout<<G->vexlist[p->adjvex].vertex;visited[p->adjvex]=TRUE;ENQUEUE(p->adjvex,Q); } p=p->next;} }}intmain。{AdjGraphG;IniADJGraph(&G);VertexDatav[6]={'a','b','c','d','e','￡};EdgeDatae[6][NumVertices]={{0,1,0,1,0,1}, {1,0,1,1,1,0}, {0,1,0,0,1,0}, {1,1,0,0,1,1}, {0,1,1,1,0,0}, {1,0,0,1,0,0}};CreateADJGraph(&G,v,e,6);DFSTraverse(G);cout<<endl;BFS1(&G,1);cout<<endl;}〃連接矩陣表示BOOLEANvisited[NumVertices];intdfn[NumVertices];//深度優先voidDFSTraverse(MTGraphG){inti,count=1;for(i=0;i<G.n;i++)visited[i]=FALSE;for(i=0;i<G.n;i++)if(!visited[i])DFS2(&G,i);}voidDFS2(MTGraph*G,inti){intj;staticintcount=0;cout<<G->vexlist[i];visited[i]=TRUE;dfn[i]=count;count++;for(j=0;j<G->n;j++)if((G->edge[i][j]==1)&&!visited[j])DFS2(G,j);}intbfn[NumVertices];〃廣度優先voidBFS2(MTGraph*G,intk){inti,j;QUEUEQ;MAKENULL(Q);cout<<G->vexlist[k];visited[k]=TRUE;ENQUEUE(k,Q);while(!EMPTY(Q)) {i=FRONT(Q)->element;DEQUEUE(Q);for(j=0;j<G->n;j++){ if(G->edge[i][j]==1&&!visited[j]){ cout<<G->vexlist[j];visited[j]=TRUE;ENQUEUE(j,Q);} } } }intmain。{MTGraphG;IniMGraph(&G);VertexDatav[6]={'a','b','c','d','e','f};EdgeDatae[6][NumVertices]={{0,1,0,1,0,1}, {1,0,1,1,1,0}, {0,1,0,0,1,0},{1,1,0,0,1,1}, {0,1,1,1,0,0}, {1,0,0,1,0,0}};CreateMGraph(&G,v,e,6);PrintMT(&G);DFSTraverse(G);整理范本cout<<endl;BFS2(&G,0);cout<<endl;}四、基于深度優先搜索算法，寫出求無向圖連通分量的算法。typedefcharVertexData;typedefintEdgeData;typedefstruct{VertexDatavexlist[NumVertices];EdgeDataedge[NumVertices][NumVertices];intn;inte;}MTGraph;boolvisited[NumVertices];intdfn[NumVertices];voidDFS2(MTGraph*G,inti){intcount=0;cout<<G->vexlist[i];visited[i]=true;dfn[i]=count;count++;for(intj=0;j<G->n;j++)if((G->edge[i][j]==1)&&!visited[j])DFS2(G,j);}voidDFSTraverse(MTGraphG){for(inti=0;i<G.n;i++)visited[i]=false;intcount=0;for(inti=0;i<G.n;i++)if(!visited[i]){ count++;cout<<count<<":";DFS2(&G,i); }}intmain。{MTGraphG;EdgeDatae[NumEdges][NumVertices];intn;cin>>n;for(inti=0;i<n;i++)for(intj=0;j<n;j++)cin>>e[i][j];VertexDatav[NumEdges];for(inti=0;i<n;i++)v[i]='a'+i-0;CreateMGraph(&G,v,e,n);DFSTraverse(G);cout<<endl;reuturn0;}五、網絡G的鄰接矩陣如下，試畫出該圖，并畫出它的一棵最小生成樹。六、下圖是一個無向帶權圖，請給出該圖的鄰接矩陣，并分別按Prim算法和Kruskal算法求最小生成樹(包括算法代碼和畫圖)。鄰接矩陣如下：abcdef 06 3000a 60 0105b 30 0660c01 6005 d0060 02e0505 20f最小生成樹：Prim算法voidPrim(MTGraphG,TREE_ARRAYT){inti,j,k;EdgeDatamin;EdgeDataLOWCOST[NumVertices];intCLOSSET[NumVertices];intn=G.n;for(i=1;i<n;i++){LOWCOST[i]=G.edge[0][i];CLOSSET[i]=0;T[i+1].data=G.vexlist[i];T[i+1].parent=0;}T[1].data=G.vexlist[0];整理范本

T[1].parent=0;for(i=1;i<n;i++){min=LOWCOST[i];k=i;for(j=1;j<n;j++)if(LOWCOST[j]<min){min=LOWCOST[j];k=j;}cout<<"("<<G.vexlist[CLOSSET[k]]<<","<<G.vexlist[k]<<"):"<<G.edge[CLOSSET[k]][k]<<endl;T[k].parent=CLOSSET[k];LOWCOST[k]=INT_MAX;for(j=1;j<n;j++)if(G.edge[k][j]<LOWCOST[j]&&LOWCOST[j]!=INT_MAX){LOWCOST[j]=G.edge[k][j];CLOSSET[j]=k;}}}voidmain。{MTGraphG;IniMGraph(&G);VertexDatav[6]={'a','b','c','d','e','f};EdgeDatae[6][NumVertices]={{INT_MAX-1,6,3,INT_MAX-1,INT_MAX-1,INT_MAX-1},{6,INT_MAX-1,INT_MAX-1,1,INT_MAX-1,5}, {3,INT_MAX-1,INT_MAX-1,6,6,INT_MAX-1},{INT_MAX-1,1,6,INT_MAX-1,INT_MAX-1,5},{INT_MAX-1,INT_MAX-1,6,INT_MAX-1,INT_MAX-1,2},{INT_MAX-1,5,INT_MAX-1,5,2,INT_MAX-1}};CreateMGraph(&G,v,e,6);TREE_ARRAYT;Prim(G,T);PreOrder(T,1);cout<<endl;}Kruskal算法structnode_tmp