南工大第四章圖

**數(shù)據(jù)結(jié)構(gòu)與算法上機(jī)作業(yè)第四章圖**一、選擇題1、在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的C倍。A.1/2B.1C.2D.42、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的B倍。A.1/2B.1C.2D.43、G是一個(gè)非連通無向圖，共有28條邊，則該圖至少有D個(gè)頂點(diǎn)。A.6B.7C.8D.94、有n個(gè)頂點(diǎn)的圖的鄰接矩陣使用B數(shù)組存儲(chǔ)的。A.一維B.n行n列C.任意行n列D.n行任意列5、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，采用鄰接表表示，則表頭數(shù)組大小至少為（假感謝閱讀設(shè)下標(biāo)為0的數(shù)組參與使用） A 。A.n-1 B.n+1 C.n D.n+e6、下列說法正確的是 C 。有向圖的鄰接矩陣一定是不對(duì)稱的有向圖的鄰接矩陣一定是對(duì)稱的無向圖的鄰接矩陣一定是對(duì)稱的無向圖的鄰接矩陣可以不對(duì)稱7、深度優(yōu)先遍歷類似與二叉樹的 A ：A.先根遍歷 B.中根遍歷 C.后根遍歷 D.層次遍歷謝謝閱讀8、廣度優(yōu)先遍歷類似與二叉樹的 D ：A.先根遍歷 B.中根遍歷 C.后根遍歷 D.層次遍歷謝謝閱讀9、下列關(guān)于開放樹(FreeTree)的說法錯(cuò)誤的是 C ：感謝閱讀**具有n個(gè)結(jié)點(diǎn)的開放樹包含n-1條邊開放樹沒有回路開放樹可以是非連通圖在開放樹中任意加一條邊，一定會(huì)產(chǎn)生回路10、在如下圖所示的圖中，從頂點(diǎn)a出發(fā)，按深度優(yōu)先遍歷，則可能得到的一種頂點(diǎn)的序謝謝閱讀列為 。A.a,b,e,c,d,fC.a,e,b,c,f,d

B.a,c,f,e,b,dD.a,e,d,f,c,b11、在如上圖所示的圖中，從頂點(diǎn)a出發(fā)，按廣度優(yōu)先遍歷，則可能得到的一種頂點(diǎn)的序謝謝閱讀列為 。A.a,b,e,c,d,f B.a,b,e,c,f,d精品文檔放心下載C.a,e,b,c,f,d D.a,e,d,f,c,b感謝閱讀12、設(shè)網(wǎng)(帶權(quán)的圖)有n個(gè)頂點(diǎn)和e條邊，則采用鄰接表存儲(chǔ)時(shí)，求最小生成樹的Prim算感謝閱讀法的時(shí)間復(fù)雜度為 C 。A.O(n) B.O(n+e) C.O(n2) D.O(n3)感謝閱讀13、設(shè)圖有n個(gè)頂點(diǎn)和e條邊，求解最短路徑的Floyd算法的時(shí)間復(fù)雜度為 O 。精品文檔放心下載A.O(n) B.O(n+e) C.O(n2) D.O(n3)感謝閱讀14、最小生成樹是指 C 。**由連通網(wǎng)所得到的邊數(shù)最少的生成樹。由連通網(wǎng)所得到的頂點(diǎn)數(shù)相對(duì)較少的生成樹。連通網(wǎng)中所有生成樹中權(quán)值之和為最小的生成樹。連通網(wǎng)的極小連通子圖。15、下面關(guān)于工程計(jì)劃的AOE網(wǎng)的敘述中，不正確的是 B 。感謝閱讀關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間。任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成。精品文檔放心下載所有關(guān)鍵活動(dòng)都提前完成，那么整個(gè)工程將會(huì)提前完成。某些關(guān)鍵工程若提前完成，那么整個(gè)工程將會(huì)提前完成。16、在AOE網(wǎng)中，始點(diǎn)和匯點(diǎn)的個(gè)數(shù)為 C 。A.1個(gè)始點(diǎn)，若干個(gè)匯點(diǎn) B.若干個(gè)始點(diǎn)，若干個(gè)匯點(diǎn)感謝閱讀C.若干個(gè)始點(diǎn)，1個(gè)匯點(diǎn) C.1個(gè)始點(diǎn)，1個(gè)匯點(diǎn)感謝閱讀17、在下圖所示的無向圖中，從頂點(diǎn)v1開始采用Prim算法生成最小生成樹，算法過程中感謝閱讀產(chǎn)生的頂點(diǎn)次序?yàn)?B 。A.v1,v3,v4,v2,v5,v6 B.v1,v3,v6,v2,v5,v4謝謝閱讀C.v1,v2,v3,v4,v5,v6 D.v1,v3,v6,v4,v2,v5謝謝閱讀18、在上圖所示的途中，采用Cruskal算法生成最小生成樹，過程中產(chǎn)生的邊的次序是謝謝閱讀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)謝謝閱讀19、如下圖所示的圖中，其中一個(gè)拓?fù)渑判虻慕Y(jié)果是 A 。感謝閱讀v1→v2→v3→v6→v4→v5→v7→v8v1→v2→v3→v4→v5→v6→v7→v8v1→v6→v4→v5→v2→v3→v7→v8v1→v6→v2→v3→v7→v8→v4→v520、在下圖所示的AOE網(wǎng)中，活動(dòng)a9的最早開始時(shí)間為精品文檔放心下載

B

。A.13 B.14 C.15 D.1621、在上圖所示的AOE網(wǎng)中，活動(dòng)a4的最遲開始時(shí)間為 D精品文檔放心下載A.2 B.3 C.4 D.522、設(shè)圖有n個(gè)頂點(diǎn)和e條邊，當(dāng)用鄰接表表示該圖時(shí)，則求解最短路徑的Dijkstra算法感謝閱讀的時(shí)間復(fù)雜度為 O 。A.O(n) B.O(n+e)

C.O(e)

D.O(n2)**二、填空題1、若無向圖G中頂點(diǎn)數(shù)為n，則圖G至多有n(n-1)/2條邊；若G為有向圖，則圖G至多有n(n-1)條邊。2、圖的存儲(chǔ)結(jié)構(gòu)主要有兩種，分別是鄰接表和鄰接矩陣。3、若G是有向圖，則把鄰接到頂點(diǎn)v的頂點(diǎn)數(shù)目或邊數(shù)目稱為頂點(diǎn)v的入度；把鄰接于頂點(diǎn)v的頂點(diǎn)數(shù)目或邊數(shù)目稱為頂點(diǎn)v的出度。4、已知一個(gè)圖的鄰接矩陣表示，計(jì)算第j個(gè)頂點(diǎn)的入度的方法是 第j行非0元素的個(gè)感謝閱讀數(shù)，計(jì)算第j個(gè)頂點(diǎn)的出度的方法是第j列非0元素的個(gè)數(shù)。5、若將圖中的每條邊都賦予一個(gè)權(quán)，則稱這種帶權(quán)的圖為網(wǎng)絡(luò)。6、無論是有向圖還是無向圖，頂點(diǎn)數(shù)n、邊數(shù)e和各頂點(diǎn)的度D(vi)之間的關(guān)系為：。7、若路徑上第一個(gè)頂點(diǎn)v1與最后一個(gè)頂點(diǎn)vm重合,則稱這樣的簡單路徑為回路或環(huán)。8、如果圖中任意一對(duì)頂點(diǎn)都是連通的,則稱此圖是連通圖；非連通圖的極大連通子圖叫做連通分量。9、創(chuàng)建一個(gè)鄰接矩陣圖的復(fù)雜度是O（n*n）；創(chuàng)建一個(gè)鏈接表圖的復(fù)雜度是O(n+e)。10、圖的遍歷有深度優(yōu)先遍歷和廣度優(yōu)先遍歷等方法。**11、在深度優(yōu)先搜索和廣度優(yōu)先搜索中，都采用visited[i]=0(false)的方式設(shè)置第i個(gè)頂點(diǎn)為new，而采用visited[i]=1（true）的方式標(biāo)識(shí)第i個(gè)結(jié)點(diǎn)為old。12、由于深度優(yōu)先算法的特點(diǎn)，深度優(yōu)先往往采用遞歸的方式實(shí)現(xiàn)。謝謝閱讀13、由于廣度優(yōu)先算法的特點(diǎn)，在廣度優(yōu)先實(shí)現(xiàn)過程中，往往要借助于另一種數(shù)據(jù)結(jié)構(gòu)感謝閱讀隊(duì)列 實(shí)現(xiàn)。14、在深度優(yōu)先搜索和廣度優(yōu)先搜索中，在搜索過程中所經(jīng)過的邊都稱為 搜索感謝閱讀邊 。15、連通而且無環(huán)路的無向圖稱為 開放數(shù) 。16、對(duì)于含有n個(gè)頂點(diǎn)e條邊的連通圖，利用Prim算法求其最小生成樹的時(shí)間復(fù)雜度為謝謝閱讀O(n*n)，利用Kruscal算法求最小生成樹的時(shí)間復(fù)雜度是O(e*lge)。3、頂點(diǎn)表示活動(dòng)的網(wǎng)簡稱為AOV；邊表示活動(dòng)的網(wǎng)簡稱為AOE。精品文檔放心下載17、一個(gè)含有n個(gè)頂點(diǎn)的無向連通圖，其每條邊的權(quán)重都是a(a>0)，則其最小生成樹的權(quán)謝謝閱讀重等于 （n-1）*a 。18、具有n個(gè)頂點(diǎn)的有向圖，如果采用鄰接矩陣表示該圖，則求某頂點(diǎn)到其他各頂點(diǎn)的最謝謝閱讀短路徑的Dijkstra算法的時(shí)間復(fù)雜度是O(n*n)；如果采用鄰接表表示該圖，則時(shí)間復(fù)雜度為O(e)。謝謝閱讀19、在用Dijkstra算法求單源最短路徑的過程中，將頂點(diǎn)集合V劃分為兩個(gè)集合S和V-S，謝謝閱讀其中S中的點(diǎn)為最短路徑已確定的頂點(diǎn)集合，V-S中的點(diǎn)為最短路徑未確定的頂點(diǎn)集合。精品文檔放心下載、求每一對(duì)頂點(diǎn)之間的最短路徑，可以用兩種方法，一種是分別對(duì)每個(gè)頂點(diǎn)采用謝謝閱讀算法，另一種方法是。**21、假設(shè)有向圖的鄰接矩陣C的傳遞閉包為A，則A[i][j]=1表示 。謝謝閱讀22、有向圖的中心點(diǎn)是指 具有最小偏心度的頂點(diǎn) 。三、已知一個(gè)無向圖如下圖所示，試給出該圖的鄰接矩陣和鄰接表存儲(chǔ)示意圖（畫圖，分別謝謝閱讀用矩陣和數(shù)組鏈表圖表示），并編程分別實(shí)現(xiàn)該圖的鄰接矩陣表示和鄰接表表示，要求編寫感謝閱讀兩種表示方法的存儲(chǔ)結(jié)構(gòu)、相關(guān)基本操作，并在主函數(shù)中創(chuàng)建該圖。感謝閱讀代碼：#include<iostream>usingnamespacestd;#definemax_vexNum26 //最大頂點(diǎn)個(gè)數(shù)精品文檔放心下載typedefstruct{intvex_num,arc_num; //頂點(diǎn)數(shù),邊數(shù)精品文檔放心下載intcount; //記錄當(dāng)前頂點(diǎn)數(shù)charvexs[max_vexNum]; //頂點(diǎn)向量感謝閱讀doublearcs[max_vexNum][max_vexNum]; //鄰接矩陣感謝閱讀}Graph;**//添加一個(gè)新的頂點(diǎn)charNewNode(Graph*G,charv){感謝閱讀G->vexs[G->count]=v;G->count++;returnv;}//尋找某個(gè)頂點(diǎn)的位置intFindPosition(Graph*G,charv){謝謝閱讀for(inti=0;i<G->count;i++){精品文檔放心下載if(v==G->vexs[i])returni;}}voidDelete(Graph*G,charv){精品文檔放心下載//先刪除點(diǎn)inti,j;**inttemp_count= G->count;i=FindPosition(G,v);for(j=i;j<temp_count;j++)G->vexs[j]=G->vexs[j+1];G->count--;// 刪除邊//先刪除行intp=i;//記住位置for(i=p;i<temp_count-1;i++)精品文檔放心下載for(j=0;j<temp_count;j++)G->arcs[i][j]=G->arcs[i+1][j];精品文檔放心下載//再刪除列for(i=p;i<temp_count-1;i++)感謝閱讀for(j=0;j<temp_count;j++)G->arcs[j][i]=G->arcs[j][i+1];感謝閱讀}**//建立v1與v2的一條邊voidSetSoucc(Graph*G,charv1,charv2){謝謝閱讀//先找到對(duì)應(yīng)的定的位置inti,j;inttemp_count=G->count;i=FindPosition(G,v1);j=FindPosition(G,v2);if(i==temp_count||j==temp_count)//沒有找到感謝閱讀return;//找到后，A[i][j]=0;vexs[j][i]=0;感謝閱讀G->arcs[i][j]=1;G->arcs[j][i]=1;}voidDelSucc(Graph*G,charv1,charv2){精品文檔放心下載inti,j;inttemp_count=G->count;i=FindPosition(G,v1);**j=FindPosition(G,v2);if(i==temp_count||j==temp_count)//沒有找到感謝閱讀return;//找到后，A[i][j]=0;vexs[j][i]=0;感謝閱讀G->arcs[i][j]=0;G->arcs[j][i]=0;}//判斷v1y與v2是否連接boolisEdge(Graph*G,charv1,charv2){精品文檔放心下載inti,j;inttemp_count=G->count;i=FindPosition(G,v1);j=FindPosition(G,v2);if(i==temp_count||j==temp_count)//沒有找到精品文檔放心下載return-1;**if(G->arcs[i][j]==1)returntrue;returnfalse;}voidPrint(Graph*G){inti,j;for(i=0;i<G->count;i++){for(j=0;j<G->count;j++)cout<<G->arcs[i][j]<<"";cout<<endl;}cout<<endl;}Graph*G=newGraph;//初始化intmain(){G->count=0;**NewNode(G,'A');NewNode(G,'B');NewNode(G,'C');NewNode(G,'D');//插入邊SetSoucc(G,'A','B');SetSoucc(G,'A','D');SetSoucc(G,'C','B');Print(G);//刪除一個(gè)頂點(diǎn)Delete(G,'C');Print(G);//刪除邊DelSucc(G,'A','D');Print(G);if(isEdge(G,'A','B'))cout<<"A與B右邊"<<endl;**return0;}四、已知一個(gè)有向圖如下圖所示，試給出圖的鄰接矩陣和鄰接表存儲(chǔ)示意圖（畫圖，分別用謝謝閱讀矩陣和數(shù)組鏈表圖表示），并編程分別實(shí)現(xiàn)該圖的鄰接矩陣表示和鄰接表表示，要求編寫兩謝謝閱讀種表示方法的存儲(chǔ)結(jié)構(gòu)、相關(guān)基本操作，并在主函數(shù)中創(chuàng)建該圖。精品文檔放心下載代碼：#include<iostream>#include<stdio.h>#include<stdlib.h>usingnamespacestd;#define max_n 20structArcNode{charadjvex='#';ArcNode*next=NULL;};**typedefstructVNode{chardata;ArcNode *first_head;}VNode,AdjList[max_n];typedefstruct{AdjList vertices;int vexnum,arcnum;intcount=0;}Graph;//新增一個(gè)頂點(diǎn)charNewNode(Graph*G,charv){感謝閱讀G->vertices[G->count].data=v;感謝閱讀G->vertices[G->count].first_head=newArcNode;精品文檔放心下載G->count++;returnv;}//尋找某個(gè)頂點(diǎn)的位置**intFindPosition(Graph*G,charv){精品文檔放心下載for(inti=0;i<G->count;i++){謝謝閱讀if(v==G->vertices[i].data)感謝閱讀returni;}}//刪除一個(gè)頂點(diǎn)voidDelNode(Graph*G,charv){感謝閱讀inti=FindPosition(G,v);//去頭ArcNode*p=G->vertices[i].first_head;感謝閱讀//現(xiàn)在vertices中刪除intj;for(j=i;j<G->count-1;j++)G->vertices[j]=G->vertices[j+1];精品文檔放心下載G->vertices[j].data='#';G->vertices[j].first_head=NULL;感謝閱讀G->count--;**//刪除邊ArcNode*q;while(p!=NULL){q=p;p=p->next;q=NULL;}}//設(shè)置v1到v2直接的一條邊voidSetSucc(Graph*G,charv1,char v2){謝謝閱讀inti=FindPosition(G,v1);ArcNode*p;p=G->vertices[i].first_head;精品文檔放心下載while(p->next!=NULL){p=p->next;**}ArcNode*q=newArcNode;q->adjvex=v2;p->next=q;}ArcNode*FindNode(ArcNode*p,charv2){精品文檔放心下載for(;p;p=p->next){if(p->next->adjvex==v2)break;}returnp;}voidDetele(Graph*G,charv1,char v2){感謝閱讀inti=FindPosition(G,v1);**ArcNode*p;//沒有找到if(i==-1)return;p=FindNode(G->vertices[i].first_head,v2);感謝閱讀//因?yàn)閜是上一個(gè)節(jié)點(diǎn)的位置，用q來保存//要?jiǎng)h除的節(jié)點(diǎn)的地址ArcNode*q=p->next;//通過將上一個(gè)節(jié)點(diǎn)的next指針指向要?jiǎng)h除節(jié)點(diǎn)的next指謝謝閱讀//針志向的節(jié)點(diǎn)實(shí)現(xiàn)斷開要?jiǎng)h除節(jié)點(diǎn)的目的// p->adjvex=p->next->adjvex;謝謝閱讀p->next=p->next->next;//刪除要?jiǎng)h除的節(jié)點(diǎn)qdeleteq;}//輸出領(lǐng)接表**voidPrint(Graph*G){ArcNode*p;for(inti=0;i<G->count;i++){精品文檔放心下載//先將datacout<<G->vertices[i].data<<"->";感謝閱讀//從每個(gè)頂點(diǎn)的頭結(jié)點(diǎn)開始遍歷if(G->vertices[i].first_head->next!=NULL){謝謝閱讀p=G->vertices[i].first_head->next;感謝閱讀while(p!=NULL){cout<<p->adjvex<<"->";p=p->next;}}cout<<endl;}cout<<endl;}**Graph*G=newGraph;intmain(){NewNode(G,'A');NewNode(G,'B');NewNode(G,'C');NewNode(G,'D');Print(G);SetSucc(G,'A','D');SetSucc(G,'A','B');SetSucc(G,'A','C');SetSucc(G,'B','C');SetSucc(G,'C','D');SetSucc(G,'D','B');Print(G);Detele(G,'A','C');**Detele(G,'D','B');Print(G);SetSucc(G,'D','C');Print(G);return0;}五、已知一個(gè)圖的頂點(diǎn)集為{a,b,c,d,e}，其鄰接矩陣如下圖，考慮圖為無向圖和有向圖兩精品文檔放心下載種情況，分別畫出該圖。六、已知一個(gè)連通圖如下圖所示，分別給出一個(gè)按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點(diǎn)序列精品文檔放心下載（假設(shè)從頂點(diǎn)v1出發(fā)）。并編程分別實(shí)現(xiàn)該圖的鄰接矩陣表示和鄰接表表示，要求編寫相謝謝閱讀關(guān)基本操作，并在主函數(shù)中求出深度優(yōu)先序列和廣度優(yōu)先序列。感謝閱讀代碼：#include<iostream>#include<stdio.h>**#include<stdlib.h>#include<queue>usingnamespacestd;#define max_n 20structArcNode{charadjvex='#';ArcNode*next=NULL;};typedefstructVNode{chardata;ArcNode *first_head;}VNode,AdjList[max_n];typedefstruct{AdjList vertices;int visit[max_n]={0};//記錄是否被訪問過精品文檔放心下載int vexnum,arcnum;intcount=0;**}Graph;//新增一個(gè)頂點(diǎn)charNewNode(Graph*G,charv){精品文檔放心下載G->vertices[G->count].data=v;謝謝閱讀G->vertices[G->count].first_head=newArcNode;謝謝閱讀G->count++;returnv;}//尋找某個(gè)頂點(diǎn)的位置intFindPosition(Graph*G,charv){精品文檔放心下載for(inti=0;i<G->count;i++){精品文檔放心下載if(v==G->vertices[i].data)謝謝閱讀returni;}}//刪除一個(gè)頂點(diǎn)voidDelNode(Graph*G,charv){感謝閱讀inti=FindPosition(G,v);**//去頭ArcNode*p=G->vertices[i].first_head;感謝閱讀//現(xiàn)在vertices中刪除intj;for(j=i;j<G->count-1;j++)感謝閱讀G->vertices[j]=G->vertices[j+1];謝謝閱讀G->vertices[j].data='#';G->vertices[j].first_head=NULL;謝謝閱讀G->count--;//刪除邊ArcNode*q;while(p!=NULL){q=p;p=p->next;q=NULL;}}**//設(shè)置v1到v2直接的一條邊voidSetSucc(Graph*G,charv1,char v2){感謝閱讀inti=FindPosition(G,v1);ArcNode*p;p=G->vertices[i].first_head;精品文檔放心下載while(p->next!=NULL){p=p->next;}ArcNode*q=newArcNode;q->adjvex=v2;p->next=q;}//對(duì)于無向圖**voidSetSucc1(Graph*G,charv1,char v2){謝謝閱讀SetSucc(G,v1,v2);SetSucc(G,v2,v1);}ArcNode*FindNode(ArcNode*p,charv2){謝謝閱讀for(;p;p=p->next){if(p->next->adjvex==v2)break;}returnp;}voidDetele(Graph*G,charv1,char v2){精品文檔放心下載inti=FindPosition(G,v1);ArcNode*p;//沒有找到if(i==-1)return;**p=FindNode(G->vertices[i].first_head,v2);謝謝閱讀//因?yàn)閜是上一個(gè)節(jié)點(diǎn)的位置，用q來保存//要?jiǎng)h除的節(jié)點(diǎn)的地址ArcNode*q=p->next;//通過將上一個(gè)節(jié)點(diǎn)的next指針指向要?jiǎng)h除節(jié)點(diǎn)的next指感謝閱讀//針志向的節(jié)點(diǎn)實(shí)現(xiàn)斷開要?jiǎng)h除節(jié)點(diǎn)的目的// p->adjvex=p->next->adjvex;謝謝閱讀p->next=p->next->next;//刪除要?jiǎng)h除的節(jié)點(diǎn)qdeleteq;}//輸出領(lǐng)接表voidPrint(Graph*G){ArcNode*p;for(inti=0;i<G->count;i++){感謝閱讀//先將data**cout<<G->vertices[i].data<<"->";感謝閱讀//從每個(gè)頂點(diǎn)的頭結(jié)點(diǎn)開始遍歷if(G->vertices[i].first_head->next!=NULL){感謝閱讀p=G->vertices[i].first_head->next;謝謝閱讀while(p!=NULL){cout<<p->adjvex<<"->";p=p->next;}}cout<<endl;}cout<<endl;}voidmakeVisitNull(Graph*G){精品文檔放心下載for(inti=0;i<max_n;i++)G->visit[i]=0;**}voidDfs_part(Graph*G,inti){精品文檔放心下載ArcNode*p=G->vertices[i].first_head->next;精品文檔放心下載for(;p;p=p->next){inti=FindPosition(G,p->adjvex);精品文檔放心下載if(!G->visit[i]){G->visit[i]=1;cout<<p->adjvex<<"->";Dfs_part(G,i);}}}//深度優(yōu)先遍歷void DFS(Graph*G,inti){精品文檔放心下載cout<<G->vertices[i].data<<"->";精品文檔放心下載G->visit[i]=1;Dfs_part(G,i);**//恢復(fù)makeVisitNull(G);cout<<endl;}queue<int>qList;voidBfs_part(Graph*G){感謝閱讀intt= qList.front();cout<<G->vertices[t].data<<"->";精品文檔放心下載qList.pop();ArcNode*p=G->vertices[t].first_head->next;精品文檔放心下載for(;p;p=p->next){inti=FindPosition(G,p->adjvex);謝謝閱讀if(!G->visit[i]){G->visit[i]=1;qList.push(i);**}}if(!qList.empty())Bfs_part(G);}//void BFS(Graph*G,inti){感謝閱讀G->visit[i]=1;qList.push(i);Bfs_part(G);//恢復(fù)makeVisitNull(G);cout<<endl;}Graph*G=newGraph;intmain(){**NewNode(G,'1');NewNode(G,'2');NewNode(G,'3');NewNode(G,'4');NewNode(G,'5');NewNode(G,'6');Print(G);SetSucc1(G,'1','2');SetSucc1(G,'1','4');SetSucc1(G,'1','6');SetSucc1(G,'2','3');SetSucc1(G,'2','4');SetSucc1(G,'2','5');SetSucc1(G,'3','5');SetSucc1(G,'4','6');SetSucc1(G,'4','5');**Print(G);cout<<"DFS:"<<endl;DFS(G,0);cout<<"BFS:"<<endl;BFS(G,0);return0;}七、基于深度優(yōu)先搜索算法，寫出求無向圖所有連通子圖的算法，并求連通分量。精品文檔放心下載提示：對(duì)于無向圖，從任一個(gè)頂點(diǎn)出發(fā)進(jìn)行DFS遍歷，當(dāng)本次遍歷完成后，其所訪問的結(jié)謝謝閱讀點(diǎn)構(gòu)成一個(gè)連通子圖；如果還存在沒有訪問過的結(jié)點(diǎn)，則從中任一個(gè)結(jié)點(diǎn)出發(fā)進(jìn)行DFS遍謝謝閱讀歷，……，直到所有結(jié)點(diǎn)都被訪問。每一次調(diào)用DFS后都得到此非連通圖的一個(gè)連通子圖，謝謝閱讀調(diào)用DFS的次數(shù)就是連通子圖的個(gè)數(shù)。八、網(wǎng)絡(luò)G的鄰接矩陣如下，試畫出該圖，并畫出它的一棵最小生成樹。感謝閱讀解：九、下圖是一個(gè)無向帶權(quán)圖，請給出該圖的鄰接矩陣，并分別按Prim算法和Kruskal算法感謝閱讀**求最小生成樹（包括算法代碼和畫圖）。十、代碼：#include<iostream>#include<vector>#include<queue>#include<algorithm>usingnamespacestd;#defineINFINITE0xFFFFFFFF謝謝閱讀#defineVertexDataunsignedint //頂點(diǎn)數(shù)據(jù)感謝閱讀#defineUINT unsignedint#definevexCounts6 //頂點(diǎn)數(shù)量感謝閱讀charvextex[]={'A','B','C','D','E','F'};感謝閱讀structnode{VertexDatadata;unsignedintlowestcost;}closedge[vexCounts];//Prim算法中的輔助信息謝謝閱讀typedefstruct{VertexDatau;**VertexDatav;unsignedintcost; //邊的代價(jià)}Arc;//原始圖的邊信息voidAdjMatrix(unsignedintadjMat[][vexCounts]){//鄰接矩陣表示法謝謝閱讀for(inti=0;i<vexCounts;i++) //初始化鄰接矩陣精品文檔放心下載for(intj=0;j<vexCounts;j++){感謝閱讀adjMat[i][j]=INFINITE;}}intMinmum(structnode*closedge){//返回最小代價(jià)邊謝謝閱讀unsignedintmin=INFINITE;謝謝閱讀intindex=-1;for(inti=0;i<vexCounts;i++){謝謝閱讀if(closedge[i].lowestcost<min&&closedge[i].lowestcost!=0){謝謝閱讀min=closedge[i].lowestcost;精品文檔放心下載index=i;}}returnindex;}voidMiniSpanTree_Prim(unsignedintadjMat[][vexCounts],VertexDatas){感謝閱讀**for(inti=0;i<vexCounts;i++){精品文檔放心下載closedge[i].lowestcost=INFINITE;精品文檔放心下載}closedge[s].data=s; //從頂點(diǎn)s開始精品文檔放心下載closedge[s].lowestcost=0;謝謝閱讀for(inti=0;i<vexCounts;i++){//初始化輔助數(shù)組精品文檔放心下載if(i!=s){closedge[i].data=s;closedge[i].lowestcost=adjMat[s][i];精品文檔放心下載}}for(inte=1;e<=vexCounts-1;e++){//n-1條邊時(shí)退出謝謝閱讀intk=Minmum(closedge); //選擇最小代價(jià)邊感謝閱讀cout<<vextex[closedge[k].data]<<"--"<<vextex[k]<<endl;//加入到最謝謝閱讀小生成樹closedge[k].lowestcost=0;//代價(jià)置為0精品文檔放心下載for(inti=0;i<vexCounts;i++){//更新v中頂點(diǎn)最小代價(jià)邊信息謝謝閱讀if(adjMat[k][i]<closedge[i].lowestcost){精品文檔放心下載closedge[i].data=k;closedge[i].lowestcost=adjMat[k][i];謝謝閱讀}}**}}voidReadArc(unsignedint adjMat[][vexCounts],vector<Arc>&vertexArc){//保存謝謝閱讀圖的邊代價(jià)信息Arc*temp=NULL;for(unsignedinti=0;i<vexCounts;i++){謝謝閱讀for(unsignedintj=0;j<i;j++){謝謝閱讀if(adjMat[i][j]!=INFINITE){謝謝閱讀temp=newArc;temp->u=i;temp->v=j;temp->cost=adjMat[i][j];精品文檔放心下載vertexArc.push_back(*temp);謝謝閱讀}}}}boolcompare(Arc A,Arc B){謝謝閱讀returnA.cost<B.cost?true:false;感謝閱讀}boolFindTree(VertexDatau,VertexDatav,vector<vector<VertexData>>&Tree){感謝閱讀unsignedintindex_u=INFINITE;感謝閱讀**unsignedintindex_v=INFINITE;精品文檔放心下載for(unsignedinti=0;i<Tree.size();i++){//檢查u,v分別屬于哪顆樹感謝閱讀if(find(Tree[i].begin(),Tree[i].end(),u)!=Tree[i].end())謝謝閱讀index_u=i;if(find(Tree[i].begin(),Tree[i].end(),v)!=Tree[i].end())精品文檔放心下載index_v=i;}if(index_u!=index_v){//u,v不在一顆樹上，合并兩顆樹謝謝閱讀for(unsignedinti=0;i<Tree[index_v].size();i++){謝謝閱讀Tree[index_u].push_back(Tree[index_v][i]);感謝閱讀}Tree[index_v].cle