南工大第四章-圖(共39頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)與算法上機(jī)作業(yè)第四章 圖一、選擇題1、在一個(gè)無(wú)向圖中，所有頂點(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è)非連通無(wú)向圖，共有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條邊的無(wú)向圖，采用鄰接表表示，則表頭數(shù)組大小至少為（假設(shè)下標(biāo)為0的數(shù)組參與使用） A 。A. n

2、-1B. n+1C. nD. n+e6、下列說(shuō)法正確的是 C 。A. 有向圖的鄰接矩陣一定是不對(duì)稱的B. 有向圖的鄰接矩陣一定是對(duì)稱的C. 無(wú)向圖的鄰接矩陣一定是對(duì)稱的D. 無(wú)向圖的鄰接矩陣可以不對(duì)稱7、深度優(yōu)先遍歷類似與二叉樹(shù)的 A ：A. 先根遍歷B. 中根遍歷C. 后根遍歷D. 層次遍歷8、廣度優(yōu)先遍歷類似與二叉樹(shù)的 D ：A. 先根遍歷B. 中根遍歷C. 后根遍歷D. 層次遍歷9、下列關(guān)于開(kāi)放樹(shù)(Free Tree)的說(shuō)法錯(cuò)誤的是 C ： A. 具有n個(gè)結(jié)點(diǎn)的開(kāi)放樹(shù)包含n-1條邊 B. 開(kāi)放樹(shù)沒(méi)有回路 C. 開(kāi)放樹(shù)可以是非連通圖 D. 在開(kāi)放樹(shù)中任意加一條邊，一定會(huì)產(chǎn)生回路10、在如下

3、圖所示的圖中，從頂點(diǎn)a出發(fā)，按深度優(yōu)先遍歷，則可能得到的一種頂點(diǎn)的序列為 。 A. a, b, e, c, d, fB. a, c, f, e, b, d C. a, e, b, c, f, dD. a, e, d, f, c, b11、在如上圖所示的圖中，從頂點(diǎn)a出發(fā)，按廣度優(yōu)先遍歷，則可能得到的一種頂點(diǎn)的序列為 。A. a, b, e, c, d, fB. a, b, e, c, f, dC. a, e, b, c, f, dD. a, e, d, f, c, b12、設(shè)網(wǎng)(帶權(quán)的圖)有n個(gè)頂點(diǎn)和e條邊，則采用鄰接表存儲(chǔ)時(shí)，求最小生成樹(shù)的Prim算法的時(shí)間復(fù)雜度為 C 。A. O(n)B.

4、 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、最小生成樹(shù)是指 C 。A. 由連通網(wǎng)所得到的邊數(shù)最少的生成樹(shù)。B. 由連通網(wǎng)所得到的頂點(diǎn)數(shù)相對(duì)較少的生成樹(shù)。C. 連通網(wǎng)中所有生成樹(shù)中權(quán)值之和為最小的生成樹(shù)。D. 連通網(wǎng)的極小連通子圖。15、下面關(guān)于工程計(jì)劃的AOE網(wǎng)的敘述中，不正確的是 B 。A. 關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間。B. 任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成。C. 所有關(guān)鍵活動(dòng)都提前完成，那么整個(gè)工程將會(huì)提

5、前完成。D. 某些關(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、在下圖所示的無(wú)向圖中，從頂點(diǎn)v1開(kāi)始采用Prim算法生成最小生成樹(shù)，算法過(guò)程中產(chǎn)生的頂點(diǎn)次序?yàn)?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, v518、在上圖所示的途中，采用Cruskal算法生成最小生成樹(shù)，過(guò)程中產(chǎn)生的邊的

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)19、如下圖所示的圖中，其中一個(gè)拓?fù)渑判虻慕Y(jié)果是 A 。A. v1v2v3v6v4v5v7v8B. v1v2v3v4v5v6v7v8C. v1v6v4v5v2v3v7v8D. v1v6v2v3v7v8v4v520、在下圖所示的AOE網(wǎng)中，活動(dòng)a9的最早開(kāi)始時(shí)

7、間為 B 。A. 13B. 14C. 15D. 1621、在上圖所示的AOE網(wǎng)中，活動(dòng)a4的最遲開(kāi)始時(shí)間為 D A. 2B. 3C. 4D. 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、若無(wú)向圖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 的頂

8、點(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、無(wú)論是有向圖還是無(wú)向圖，頂點(diǎn)數(shù)n 、邊數(shù)e 和各頂點(diǎn)的度D(vi)之間的關(guān)系為： 。7、若路徑上第一個(gè)頂點(diǎn)v1 與最后一個(gè)頂點(diǎn)vm 重合, 則稱這樣的簡(jiǎn)單路徑為 回路或環(huán) 。8、如果圖中任意一對(duì)頂點(diǎn)都是連通的, 則稱此圖是 連通圖 ；非連通圖的極大連通子圖叫做 連通分量 。9、創(chuàng)建一個(gè)鄰接矩陣圖的復(fù)雜度是 O（n*n） ；創(chuàng)建一個(gè)鏈接表圖的復(fù)雜度是 O(n

9、+e) 。10、圖的遍歷有 深度優(yōu)先遍歷 和廣度優(yōu)先遍歷等方法。11、在深度優(yōu)先搜索和廣度優(yōu)先搜索中，都采用visitedi= 0(false) 的方式設(shè)置第i個(gè)頂點(diǎn)為new，而采用visitedi= 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)過(guò)程中，往往要借助于另一種數(shù)據(jù)結(jié)構(gòu) 隊(duì)列 實(shí)現(xiàn)。14、在深度優(yōu)先搜索和廣度優(yōu)先搜索中，在搜索過(guò)程中所經(jīng)過(guò)的邊都稱為 搜索邊 。15、連通而且無(wú)環(huán)路的無(wú)向圖稱為 開(kāi)放數(shù) 。16、對(duì)于含有n個(gè)頂點(diǎn)e條邊的連通圖，利用Prim算法求其最小生成樹(shù)的時(shí)

10、間復(fù)雜度為 O(n*n) ，利用Kruscal算法求最小生成樹(shù)的時(shí)間復(fù)雜度是 O(e*lg e) 。3、頂點(diǎn)表示活動(dòng)的網(wǎng)簡(jiǎn)稱為 AOV ；邊表示活動(dòng)的網(wǎng)簡(jiǎn)稱為 AOE 。17、一個(gè)含有n個(gè)頂點(diǎn)的無(wú)向連通圖，其每條邊的權(quán)重都是a(a>0)，則其最小生成樹(shù)的權(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算法求單源最短路徑的過(guò)程中，將頂點(diǎn)集合V劃分為兩個(gè)集合S和V-S，其中S中的點(diǎn)為 最短路徑已確

11、定的頂點(diǎn)集合 ，V-S中的點(diǎn)為 最短路徑未確定的頂點(diǎn)集合 。20、求每一對(duì)頂點(diǎn)之間的最短路徑，可以用兩種方法，一種是分別對(duì)每個(gè)頂點(diǎn)采用 算法，另一種方法是 。21、假設(shè)有向圖的鄰接矩陣C的傳遞閉包為A，則Aij=1表示 。22、有向圖的中心點(diǎn)是指 具有最小偏心度的頂點(diǎn) 。三、已知一個(gè)無(wú)向圖如下圖所示，試給出該圖的鄰接矩陣和鄰接表存儲(chǔ)示意圖（畫(huà)圖，分別用矩陣和數(shù)組鏈表圖表示），并編程分別實(shí)現(xiàn)該圖的鄰接矩陣表示和鄰接表表示，要求編寫(xiě)兩種表示方法的存儲(chǔ)結(jié)構(gòu)、相關(guān)基本操作，并在主函數(shù)中創(chuàng)建該圖。代碼：#include<iostream>using namespace std;#define

12、 max_vexNum 26 / 最大頂點(diǎn)個(gè)數(shù) typedef struct int vex_num, arc_num; / 頂點(diǎn)數(shù) ,邊數(shù) int count; /記錄當(dāng)前頂點(diǎn)數(shù) char vexsmax_vexNum; / 頂點(diǎn)向量 double arcsmax_vexNummax_vexNum; / 鄰接矩陣 Graph;/添加一個(gè)新的頂點(diǎn) char NewNode(Graph *G,char v)G->vexsG->count=v;G->count+;return v;/尋找某個(gè)頂點(diǎn)的位置int FindPosition(Graph *G,char v)for( in

13、t i=0;i<G->count;i+)if(v=G->vexsi)return i; void Delete(Graph *G,char v)/先刪除點(diǎn)int i,j;int temp_count= G->count; i=FindPosition(G,v);for(j=i;j<temp_count;j+) G->vexsj=G->vexsj+1; G->count-; / 刪除邊/先刪除行int p=i;/記住位置 for(i=p;i<temp_count-1;i+) for(j=0;j<temp_count;j+) G->

14、arcsij=G->arcsi+1j; /再刪除列 for(i=p;i<temp_count-1;i+) for(j=0;j<temp_count;j+) G->arcsji=G->arcsji+1; /建立v1與v2的一條邊 void SetSoucc(Graph * G,char v1,char v2)/先找到對(duì)應(yīng)的定的位置 int i,j;int temp_count= G->count;i=FindPosition(G,v1);j=FindPosition(G,v2);if(i=temp_count|j=temp_count) /沒(méi)有找到 retur

15、n ;/找到后 ，Aij=0;vexsji=0;G-> arcsij=1;G-> arcsji=1; void DelSucc(Graph * G,char v1,char v2)int i,j;int temp_count= G->count;i=FindPosition(G,v1);j=FindPosition(G,v2);if(i=temp_count|j=temp_count) /沒(méi)有找到 return ;/找到后 ，Aij=0;vexsji=0;G-> arcsij=0;G-> arcsji=0;/判斷v1y與v2是否連接 bool isEdge(Gra

16、ph * G,char v1,char v2)int i,j;int temp_count= G->count;i=FindPosition(G,v1);j=FindPosition(G,v2);if(i=temp_count|j=temp_count) /沒(méi)有找到 return -1;if(G->arcsij=1)return true;return false;void Print(Graph * G)int i,j; for( i=0;i<G->count;i+)for(j=0;j<G->count;j+) cout<<G->arcs

17、ij<<" "cout<<endl; cout<<endl;Graph *G=new Graph;/初始化 int main()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',&

18、#39;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;return 0; 四、已知一個(gè)有向圖如下圖所示，試給出圖的鄰接矩陣和鄰接表存儲(chǔ)示意圖（畫(huà)圖，分別用矩陣和數(shù)組鏈表圖表示），并編程分別實(shí)現(xiàn)該圖的鄰接矩陣表示和鄰接表表示，要求編寫(xiě)兩種表示方法的存儲(chǔ)結(jié)構(gòu)、相關(guān)基本操作，并在主

19、函數(shù)中創(chuàng)建該圖。代碼：#include<iostream>#include <stdio.h>#include<stdlib.h>using namespace std;#define max_n 20 struct ArcNode char adjvex='#' ArcNode * next=NULL; ;typedef struct VNodechar data;ArcNode * first_head; VNode ,AdjListmax_n;typedef struct AdjList vertices;int vexnum,arcn

20、um;int count=0; Graph;/新增一個(gè)頂點(diǎn) char NewNode(Graph * G,char v) G->verticesG->count.data=v;G->verticesG->count.first_head=new ArcNode;G->count+;return v;/尋找某個(gè)頂點(diǎn)的位置int FindPosition(Graph *G,char v)for( int i=0;i<G->count;i+)if(v=G->verticesi.data)return i; /刪除一個(gè)頂點(diǎn)void DelNode(Gra

21、ph * G,char v)int i=FindPosition(G,v);/去頭ArcNode *p=G-> verticesi.first_head;/現(xiàn)在 vertices中刪除int j;for(j=i;j<G->count-1;j+) G->verticesj=G->verticesj+1; G->verticesj.data='#' G->verticesj.first_head=NULL; G->count-; /刪除邊ArcNode *q; while(p!=NULL) q=p; p=p->next; q=N

22、ULL; /設(shè)置v1到v2直接的一條邊 void SetSucc(Graph * G,char v1,char v2)int i=FindPosition(G,v1);ArcNode *p; p=G->verticesi.first_head; while(p->next!=NULL)p=p->next; ArcNode *q=new ArcNode; q->adjvex=v2;p->next=q;ArcNode * FindNode(ArcNode * p,char v2) for(;p;p=p->next) if(p->next->adjve

23、x=v2) break; return p;void Detele(Graph * G,char v1,char v2)int i=FindPosition(G,v1);ArcNode *p;/沒(méi)有找到 if(i=-1)return ;p=FindNode(G->verticesi.first_head,v2);/因?yàn)閜是上一個(gè)節(jié)點(diǎn)的位置，用q來(lái)保存 /要?jiǎng)h除的節(jié)點(diǎn)的地址 ArcNode *q = p->next; /通過(guò)將上一個(gè)節(jié)點(diǎn)的next指針指向要?jiǎng)h除節(jié)點(diǎn)的next指 /針志向的節(jié)點(diǎn)實(shí)現(xiàn)斷開(kāi)要?jiǎng)h除節(jié)點(diǎn)的目的/ p->adjvex=p->next->adjve

24、x; p->next = p->next->next; /刪除要?jiǎng)h除的節(jié)點(diǎn)q delete q;/輸出領(lǐng)接表 void Print(Graph * G)ArcNode *p;for(int i=0;i<G->count;i+)/先將 data cout<<G->verticesi.data<<"->"/從每個(gè)頂點(diǎn)的頭結(jié)點(diǎn)開(kāi)始遍歷 if(G->verticesi.first_head->next!=NULL)p=G->verticesi.first_head->next; while(p

25、!=NULL) cout<<p->adjvex<<"->" p=p->next; cout<<endl;cout<<endl;Graph * G=new Graph;int main() NewNode(G,'A');NewNode(G,'B');NewNode(G,'C');NewNode(G,'D'); Print(G); SetSucc(G,'A','D'); SetSucc(G,'A',&#

26、39;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);return 0;

27、五、已知一個(gè)圖的頂點(diǎn)集為a, b, c, d, e，其鄰接矩陣如下圖，考慮圖為無(wú)向圖和有向圖兩種情況，分別畫(huà)出該圖。六、已知一個(gè)連通圖如下圖所示，分別給出一個(gè)按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點(diǎn)序列（假設(shè)從頂點(diǎn)v1出發(fā)）。并編程分別實(shí)現(xiàn)該圖的鄰接矩陣表示和鄰接表表示，要求編寫(xiě)相關(guān)基本操作，并在主函數(shù)中求出深度優(yōu)先序列和廣度優(yōu)先序列。代碼：#include<iostream>#include <stdio.h>#include<stdlib.h>#include<queue>using namespace std;#define max_n 20st

28、ruct ArcNode char adjvex='#'ArcNode * next=NULL; ;typedef struct VNode char data;ArcNode * first_head; VNode ,AdjListmax_n;typedef struct AdjList vertices;int visitmax_n = 0; /記錄是否被訪問(wèn)過(guò)int vexnum,arcnum;int count=0; Graph;/新增一個(gè)頂點(diǎn)char NewNode(Graph * G,char v) G->verticesG->count.data=v;

29、G->verticesG->count.first_head=new ArcNode;G->count+;return v;/尋找某個(gè)頂點(diǎn)的位置int FindPosition(Graph *G,char v) for( int i=0; i<G->count; i+) if(v=G->verticesi.data)return i;/刪除一個(gè)頂點(diǎn)void DelNode(Graph * G,char v) int i=FindPosition(G,v);/去頭ArcNode *p=G-> verticesi.first_head;/現(xiàn)在 vertic

30、es中刪除int j;for(j=i; j<G->count-1; j+)G->verticesj=G->verticesj+1;G->verticesj.data='#'G->verticesj.first_head=NULL;G->count-;/刪除邊ArcNode *q;while(p!=NULL) q=p;p=p->next;q=NULL;/設(shè)置v1到v2直接的一條邊void SetSucc(Graph * G,char v1,char v2) int i=FindPosition(G,v1);ArcNode *p;p=

31、G->verticesi.first_head;while(p->next!=NULL) p=p->next;ArcNode *q=new ArcNode;q->adjvex=v2;p->next=q;/對(duì)于無(wú)向圖void SetSucc1(Graph * G,char v1,char v2) SetSucc(G,v1,v2);SetSucc(G,v2,v1);ArcNode * FindNode(ArcNode * p,char v2) for(; p; p=p->next) if(p->next->adjvex=v2)break;return

32、 p;void Detele(Graph * G,char v1,char v2) int i=FindPosition(G,v1);ArcNode *p;/沒(méi)有找到if(i=-1)return ;p=FindNode(G->verticesi.first_head,v2);/因?yàn)閜是上一個(gè)節(jié)點(diǎn)的位置，用q來(lái)保存/要?jiǎng)h除的節(jié)點(diǎn)的地址ArcNode *q = p->next;/通過(guò)將上一個(gè)節(jié)點(diǎn)的next指針指向要?jiǎng)h除節(jié)點(diǎn)的next指/針志向的節(jié)點(diǎn)實(shí)現(xiàn)斷開(kāi)要?jiǎng)h除節(jié)點(diǎn)的目的/ p->adjvex=p->next->adjvex;p->next = p->ne

33、xt->next;/刪除要?jiǎng)h除的節(jié)點(diǎn)qdelete q;/輸出領(lǐng)接表void Print(Graph * G) ArcNode *p;for(int i=0; i<G->count; i+) /先將 datacout<<G->verticesi.data<<"->"/從每個(gè)頂點(diǎn)的頭結(jié)點(diǎn)開(kāi)始遍歷if(G->verticesi.first_head->next!=NULL) p=G->verticesi.first_head->next;while(p!=NULL) cout<<p->

34、;adjvex<<"->"p=p->next;cout<<endl;cout<<endl;void makeVisitNull(Graph * G)for(int i=0;i<max_n;i+)G->visiti=0;void Dfs_part(Graph * G,int i) ArcNode *p=G->verticesi.first_head->next;for(; p; p=p->next) int i=FindPosition(G,p->adjvex);if(!G->visit

35、i) G->visiti=1;cout<<p->adjvex<<"->"Dfs_part(G,i);/深度優(yōu)先遍歷void DFS(Graph * G,int i) cout<<G->verticesi.data<<"->"G->visiti=1;Dfs_part(G,i);/恢復(fù) makeVisitNull(G); cout<<endl;queue<int> qList;void Bfs_part(Graph * G) int t=qList.f

36、ront(); cout<<G->verticest.data<<"->" qList.pop(); ArcNode *p=G->verticest.first_head->next;for(; p; p=p->next) int i=FindPosition(G,p->adjvex);if(!G->visiti) G->visiti=1;qList.push(i); if(!qList.empty()Bfs_part(G);/void BFS(Graph * G,int i) G->visiti

37、=1;qList.push(i);Bfs_part(G);/恢復(fù) makeVisitNull(G);cout<<endl;Graph * G=new Graph;int main() 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&#

38、39;,'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

39、:"<<endl; DFS(G,0); cout<<"BFS:"<<endl; BFS(G,0);return 0;七、基于深度優(yōu)先搜索算法，寫(xiě)出求無(wú)向圖所有連通子圖的算法，并求連通分量。提示：對(duì)于無(wú)向圖，從任一個(gè)頂點(diǎn)出發(fā)進(jìn)行DFS遍歷，當(dāng)本次遍歷完成后，其所訪問(wèn)的結(jié)點(diǎn)構(gòu)成一個(gè)連通子圖；如果還存在沒(méi)有訪問(wèn)過(guò)的結(jié)點(diǎn)，則從中任一個(gè)結(jié)點(diǎn)出發(fā)進(jìn)行DFS遍歷，直到所有結(jié)點(diǎn)都被訪問(wèn)。每一次調(diào)用DFS后都得到此非連通圖的一個(gè)連通子圖，調(diào)用DFS的次數(shù)就是連通子圖的個(gè)數(shù)。八、網(wǎng)絡(luò)G的鄰接矩陣如下，試畫(huà)出該圖，并畫(huà)出它的一棵最小生成樹(shù)。解：9、

40、下圖是一個(gè)無(wú)向帶權(quán)圖，請(qǐng)給出該圖的鄰接矩陣，并分別按Prim算法和Kruskal算法求最小生成樹(shù)（包括算法代碼和畫(huà)圖）。10、代碼：#include <iostream>#include <vector>#include <queue>#include <algorithm>using namespace std;#define INFINITE 0xFFFFFFFF#define VertexData unsigned int /頂點(diǎn)數(shù)據(jù)#define UINT unsigned int#define vexCounts 6 /頂點(diǎn)數(shù)量char

41、 vextex = 'A', 'B', 'C', 'D', 'E', 'F' ;struct node VertexData data;unsigned int lowestcost; closedgevexCounts; /Prim算法中的輔助信息typedef struct VertexData u;VertexData v;unsigned int cost; /邊的代價(jià) Arc; /原始圖的邊信息void AdjMatrix(unsigned int adjMatvexCounts) /鄰接

42、矩陣表示法for (int i = 0; i < vexCounts; i+) /初始化鄰接矩陣for (int j = 0; j < vexCounts; j+) adjMatij = INFINITE;int Minmum(struct node * closedge) /返回最小代價(jià)邊unsigned int min = INFINITE;int index = -1;for (int i = 0; i < vexCounts; i+) if (closedgei.lowestcost < min && closedgei.lowestcost !

43、=0) min = closedgei.lowestcost;index = i;return index;void MiniSpanTree_Prim(unsigned int adjMatvexCounts, VertexData s) for (int i = 0; i < vexCounts; i+) closedgei.lowestcost = INFINITE;closedges.data = s; /從頂點(diǎn)s開(kāi)始closedges.lowestcost = 0;for (int i = 0; i < vexCounts; i+) /初始化輔助數(shù)組if (i != s)

44、 closedgei.data = s;closedgei.lowestcost = adjMatsi;for (int e = 1; e <= vexCounts -1; e+) /n-1條邊時(shí)退出int k = Minmum(closedge); /選擇最小代價(jià)邊cout << vextexclosedgek.data << "-" << vextexk << endl;/加入到最小生成樹(shù)closedgek.lowestcost = 0; /代價(jià)置為0for (int i = 0; i < vexCounts;

45、 i+) /更新v中頂點(diǎn)最小代價(jià)邊信息if ( adjMatki < closedgei.lowestcost) closedgei.data = k;closedgei.lowestcost = adjMatki;void ReadArc(unsigned int adjMatvexCounts,vector<Arc> &vertexArc) /保存圖的邊代價(jià)信息Arc * temp = NULL;for (unsigned int i = 0; i < vexCounts; i+) for (unsigned int j = 0; j < i; j+)

46、 if (adjMatij!=INFINITE) temp = new Arc;temp->u = i;temp->v = j;temp->cost = adjMatij;vertexArc.push_back(*temp);bool compare(Arc A, Arc B) return A.cost < B.cost ? true : false;bool FindTree(VertexData u, VertexData v,vector<vector<VertexData> > &Tree) unsigned int index

47、_u = INFINITE;unsigned int index_v = INFINITE;for (unsigned int i = 0; i < Tree.size(); i+) /檢查u,v分別屬于哪顆樹(shù)if (find(Treei.begin(), Treei.end(), u) != Treei.end()index_u = i;if (find(Treei.begin(), Treei.end(), v) != Treei.end()index_v = i;if (index_u != index_v) /u,v不在一顆樹(shù)上，合并兩顆樹(shù)for (unsigned int i = 0; i < Treeindex_v.size(); i+) Treeindex_u.push_back(Tree