南工大第四章-圖

1、學(xué)習(xí)文檔僅供參考數(shù)據(jù)結(jié)構(gòu)與算法上機(jī)作業(yè)第四章圖學(xué)習(xí)文檔僅供參考、選擇題1 在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的C 倍。A. 1/2B. 1 C. 2 D. 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)為

2、 0 的數(shù)組參與使用A。6、以下說(shuō)法正確的選項(xiàng)是7、深度優(yōu)先遍歷類(lèi)似與二叉樹(shù)的8、廣度優(yōu)先遍歷類(lèi)似與二叉樹(shù)的9、以下關(guān)于開(kāi)放樹(shù)(Free Tree)的說(shuō)法錯(cuò)誤的選項(xiàng)是A. 具有 n 個(gè)結(jié)點(diǎn)的開(kāi)放樹(shù)包含n-1 條邊B. 開(kāi)放樹(shù)沒(méi)有回路A. n-1B. n+1C. n D. n+eA. 有向圖B. 有向圖的鄰接矩陣一定是對(duì)稱的C.無(wú)向圖的鄰接矩陣一定是對(duì)稱的D. 無(wú)向圖的鄰接矩陣可以不對(duì)稱A.先根遍歷B.中根遍歷C.后根遍歷D.層次遍歷A.先根遍歷B.中根遍歷C.后根遍歷D.層次遍歷學(xué)習(xí)文檔僅供參考C.開(kāi)放樹(shù)可以是非連通圖學(xué)習(xí)文檔僅供參考D.在開(kāi)放樹(shù)中任意加一條邊，一定會(huì)產(chǎn)生回路10、在如以下圖所

3、示的圖中，從頂點(diǎn)列為_(kāi)A. a, b, e, c, d, fC. a, e, b, c, f, d11、在如上圖所示的圖中，從頂點(diǎn) 為a 出發(fā)，按廣度優(yōu)先遍歷，則可能得到的一種頂點(diǎn)的序列。C. 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ù)雜度為_(kāi) C。A. 0( n)B. O(n+e)C. 0( n2)13、 設(shè)圖有 n 個(gè)頂點(diǎn)和 e 條邊，求解最短路徑的A. O( n)B. O(n+e)C. O( n2)14、 最小生成樹(shù)是指 _ C 。A. 由連通網(wǎng)所得到的邊

4、數(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)的表達(dá)中，不正確的選項(xiàng)是 _ BB. a, c, f, e, b, dD. a, e, d, f, c, bA. a, b, e, c, d, fB. a, b, e, c, f, dD. O(n3)Floyd 算法的時(shí)間復(fù)雜度為OD. O(n3)b學(xué)習(xí)文檔僅供參考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)鍵工程假設(shè)提前完成，那么整個(gè)工程將會(huì)提前完成。16、 在 AOE 網(wǎng)中，始點(diǎn)和匯點(diǎn)的個(gè)數(shù)為C 。A. 1 個(gè)始點(diǎn)，假設(shè)干個(gè)匯點(diǎn)B.假設(shè)干個(gè)始點(diǎn)，假設(shè)干個(gè)匯點(diǎn)C假設(shè)干個(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)锽。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 算法生成最

6、小生成樹(shù)，過(guò)程中產(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。A. v1Tv2Tv3Tv6Tv4 v5 v7 v8B. v1Tv2TV3Tv4TV5Tv6TV7Tv8C. v1Tv6TV4Tv5TV2Tv3TV7Tv8D. v1Tv6Tv2

7、Tv3TV7Tv8Tv4Tv520、在以下圖所示的 AOE 網(wǎng)中，活動(dòng) a9 的最早開(kāi)始時(shí)間為 _BA. 13B. 14C. 15D. 1621、 在上圖所示的 AOE 網(wǎng)中，活動(dòng) a4 的最遲開(kāi)始時(shí)間為DA. 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)二、填空題v 的頂點(diǎn)數(shù)目或邊數(shù)目稱為頂點(diǎn)v 的_ 入的頂點(diǎn)數(shù)目或邊數(shù)目稱為頂點(diǎn) v 的_出4、已知一個(gè)圖的鄰接矩陣表示，計(jì)算第j 個(gè)頂點(diǎn)的入度的方法是第 j 行非 0 元素

8、的個(gè)數(shù)_ ，計(jì)算第 j 個(gè)頂點(diǎn)的出度的方法是 第 j 列非 0 元素的個(gè)數(shù)_。5、假設(shè)將圖中的每條邊都賦予一個(gè)權(quán)，則稱這種帶權(quán)的圖為_(kāi) 網(wǎng)學(xué)習(xí)文檔僅供參考1、 假設(shè)無(wú)向圖G 中頂點(diǎn)數(shù)為n(n-1)n,則圖條邊。G 至多有n(n_1)/2條邊；假設(shè) G 為有向圖,2、 圖的存儲(chǔ)結(jié)構(gòu)主要有兩種， 分別是 陣鄰接表鄰接矩3、假設(shè) G 是有向圖，則把鄰接到頂點(diǎn) 度_；把鄰接于頂點(diǎn)學(xué)習(xí)文檔僅供參考6、 無(wú)論是有向圖還是無(wú)向圖，頂點(diǎn)數(shù)n、邊數(shù) e 和各頂點(diǎn)的度D(vi)之間的關(guān)系為：_ 。7、 假設(shè)路徑上第一個(gè)頂點(diǎn)V1與最后一個(gè)頂點(diǎn) Vm重合，則稱這樣的簡(jiǎn)單路徑為回路或環(huán)。8、 如果圖中任意一對(duì)頂點(diǎn)都是連

9、通的，則稱此圖是連通圖_ ;非連通圖的極大連通子圖叫做 _連通分量_ 。9、 創(chuàng)建一個(gè)鄰接矩陣圖的復(fù)雜度是On*n_ ;創(chuàng)建一個(gè)鏈接表圖的復(fù)雜度是O(n+e)_ 。10、 圖的遍歷有深度優(yōu)先遍歷_和廣度優(yōu)先遍歷等方法。11、 在深度優(yōu)先搜索和廣度優(yōu)先搜索中，都采用visitedi= 0(false) 的方式設(shè)置第 i 個(gè)頂點(diǎn)為 new,而采用 visitedi= 1true的方式標(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)_ 實(shí)現(xiàn)。14、 在深度優(yōu)先搜索和廣度優(yōu)先搜索

10、中，在搜索過(guò)程中所經(jīng)過(guò)的邊都稱為搜索邊_ 。15、 連通而且無(wú)環(huán)路的無(wú)向圖稱為開(kāi)放數(shù)_ 。16、 對(duì)于含有 n 個(gè)頂點(diǎn) e 條邊的連通圖，利用Prim 算法求其最小生成樹(shù)的時(shí)間復(fù)雜度為O(n*n)_ ，利用 Kruscal 算法求最小生成樹(shù)的時(shí)間復(fù)雜度是_。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(a0)，則其最小生成樹(shù)的權(quán)重等于 n-1*a_ 。18、 具有 n 個(gè)頂點(diǎn)的有向圖，如果采用鄰接矩陣表示該圖， 則求某頂點(diǎn)到其他各頂點(diǎn)的最短 路徑的Dijkstra 算法的時(shí)間復(fù)雜度是 O(n*n)_;如

11、果采用鄰接表表示該圖，則時(shí)間復(fù)雜度為_(kāi) O(e) 。19、 在用 Dijkstra 算法求單源最短路徑的過(guò)程中，將頂點(diǎn)集合V 劃分為兩個(gè)集合 S 和 V-S，其中 S 中的點(diǎn)為 _ 最短路徑已確定的頂點(diǎn)集合_ ，V-S 中的點(diǎn)為最短路徑未確定的頂點(diǎn)集合_ 。學(xué)習(xí)文檔僅供參考20、求每一對(duì)頂點(diǎn)之間的最短路徑，可以用兩種方法，一種是分別對(duì)每個(gè)頂點(diǎn)采用算法，另一種方法是 _。21、 假設(shè)有向圖的鄰接矩陣C 的傳遞閉包為 A，則 Aij=1 表示_22、 有向圖的中心點(diǎn)是指具有最小偏心度的頂點(diǎn)_。三、已知一個(gè)無(wú)向圖如以下圖所示，試給出該圖的鄰接矩陣和鄰接表存儲(chǔ)示意圖畫(huà)圖，分別用矩陣和數(shù)組鏈表圖表示，并

12、編程分別實(shí)現(xiàn)該圖的鄰接矩陣表示和鄰接表表示，要求編寫(xiě)兩種表示方法的存儲(chǔ)結(jié)構(gòu)、相關(guān)基本操作，并在主函數(shù)中創(chuàng)建該圖。代碼:#in clude using n amespace std; #defi nemax_vexNum 26 typedef structint vex_num, arc_num;int count;char vexsmax_vexNum;double arcsmax_vexNummax_vexNum; Graph;/添加一個(gè)新的頂點(diǎn)char NewNode(Graph *G,char v)/最大頂點(diǎn)個(gè)數(shù)/頂點(diǎn)數(shù)，邊數(shù)/記錄當(dāng)前頂點(diǎn)數(shù)/頂點(diǎn)向量/鄰接矩陣學(xué)習(xí)文檔 僅供參考G-ve

13、xsG -count=v;G-count+;return v;/尋找某個(gè)頂點(diǎn)的位置int FindPosition(Graph *G,char v) for( int i=0;icount;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;jvexsj=G -vexsj+1;G-count - ;/ 刪除邊/先刪除行int p=i;/ 記住位置for(i=p;itemp_count -1;i+)學(xué)習(xí)文檔

14、 僅供參考for(j=0;jarcsij=G -arcsi+1j;/再刪除列for(i=p;itemp_count -1;i+)for(j=0;jarcsji=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)有找到return ;/找到后 ， Aij=0;vexsji=0;

15、G- arcsij=1;G- arcsji=1;學(xué)習(xí)文檔 僅供參考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(Graph * G,char v1,char v2)int i,j;

16、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)學(xué)習(xí)文檔 僅供參考return true;return false;void Print(Graph * G)int i,j;for( i=0;icount;i+)for(j=0;jcount;j+)coutarcsij coutendl;學(xué)習(xí)文檔僅供參考coutcount=0;NewNode(G,A);NewNode(G,B);NewNod

17、e(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);學(xué)習(xí)文檔 僅供參考刪除邊DelSucc(G,A,D);Prin t(G);if(isEdge(G,A,B)coutA 與 B 右邊endl;return 0;四、已知一個(gè)有向圖如以下圖所示，試給出圖的鄰接矩陣和鄰接表存儲(chǔ)示意圖畫(huà)圖,用矩陣和數(shù)組鏈表圖表示，并編程分別實(shí)現(xiàn)該圖的鄰接矩陣表示和鄰接表表示， 兩種表示方法的存儲(chǔ)結(jié)構(gòu)、相關(guān)基本操作，并在主函數(shù)中創(chuàng)建該圖。代碼：#in cl

18、ude#i nclude #in clude using n amespace std;#defi ne max_n 20struct ArcNode char adjvex=#;分別要求編寫(xiě)學(xué)習(xí)文檔僅供參考ArcNode * next=NULL; ;typedef struct VNodechar data;ArcNode * first_head; VNode ,AdjListmax_n;typedef struct AdjList vertices;int vexnum,arcnum;int count=0; Graph;/新增一個(gè)頂點(diǎn)char NewNode(Graph * G,cha

19、r 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)學(xué)習(xí)文檔 僅供參考for( int i=0;icount;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)

20、在 vertices 中刪除int j;for(j=i;jcount -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;學(xué)習(xí)文檔 僅供參考q=NULL;/設(shè)置 v1 到 v2 直接的一條邊void SetSucc(Graph * G,char v1,charint i=FindPosition(G,v1);ArcNode *p;p=G-verticesi.first_head;wh

21、ile(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-adjvex=v2) break;v2)學(xué)習(xí)文檔 僅供參考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.firs

22、t_head,v2);/因?yàn)?p 是上一個(gè)節(jié)點(diǎn)的位置，用 q 來(lái)保存/要?jiǎng)h除的節(jié)點(diǎn)的地址學(xué)習(xí)文檔 僅供參考ArcNode *q = p -next;/ 通過(guò)將上一個(gè)節(jié)點(diǎn)的 next 指針指向要?jiǎng)h除節(jié)點(diǎn)的/針志向的節(jié)點(diǎn)實(shí)現(xiàn)斷開(kāi)要?jiǎng)h除節(jié)點(diǎn)的目的/ p-adjvex=p -next-adjvex;p-next = p -next -next;/刪除要?jiǎng)h除的節(jié)點(diǎn) qdelete q;/輸出領(lǐng)接表void Print(Graph * G)ArcNode *p;for(int i=0;icount;i+)/先將 datacoutverticesi.data;/從每個(gè)頂點(diǎn)的頭結(jié)點(diǎn)開(kāi)始遍歷if(G -vert

23、icesi.first_head -next!=NULL)p=G-verticesi.first_head -next;while(p!=NULL)coutadjvex;next 指學(xué)習(xí)文檔 僅供參考p=p-next;coutendl;coutendl;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,B);SetSucc(G,A,C);SetSucc(G,B,C);SetSucc(G,C,D);SetSuc

24、c(G,D,B);學(xué)習(xí)文檔僅供參考Prin t(G);Detele(G,A,C);Detele(G,D,B);Prin t(G);SetSucc(G,D,C);Prin t(G);return 0;五、已知一個(gè)圖的頂點(diǎn)集為a, b, c, d, e,其鄰接矩陣如以下圖，考慮圖為無(wú)向圖和有向圖兩種情況，分別畫(huà)出該圖。01001 r10010000I10I10101 10 J六、已知一個(gè)連通圖如以下圖所示，分別給出一個(gè)按深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點(diǎn)序列假設(shè)從頂點(diǎn) v1 出發(fā)。并編程分別實(shí)現(xiàn)該圖的鄰接矩陣表示和鄰接表表示，要求編寫(xiě) 相關(guān)基本操作，并在主函數(shù)中求出深度優(yōu)先序列和廣度優(yōu)先序列。代碼：

25、#in clude學(xué)習(xí)文檔僅供參考#i nclude #in clude#in cludeusing n amespace std;#defi ne max_n 20 struct ArcNode char adjvex=#;ArcNode * n ext=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

26、; Graph;/新增一個(gè)頂點(diǎn)char NewNode(Graph * G,char v) 學(xué)習(xí)文檔 僅供參考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; icount; i+) if(v=G -verticesi.data)return i;/刪除一個(gè)頂點(diǎn) void DelNode(Graph * G,char v) int i=FindPosition

27、(G,v);/去頭ArcNode *p=G - verticesi.first_head;/現(xiàn)在 vertices 中刪除int j;for(j=i; jcount -1; j+)G-verticesj=G -verticesj+1;G-verticesj.data=#;G-verticesj.first_head=NULL;學(xué)習(xí)文檔 僅供參考G- count - ;/刪除邊ArcNode *q; while(p!=NULL) q=p; p=p-next; q=NULL;學(xué)習(xí)文檔 僅供參考/設(shè)置 v1 到 v2 直接的一條邊void SetSucc(Graph * G,char v1,char

28、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;/對(duì)于無(wú)向圖void SetSucc1(Graph * G,char v1,charSetSucc(G,v1,v2);SetSucc(G,v2,v1);v2) v2) 學(xué)習(xí)文檔 僅供參考ArcNode * FindNode(ArcNode * p,char v2) for(; p; p=p -next) if(p -next

29、 -adjvex=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)?p 是上一個(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)的/針志向的節(jié)點(diǎn)實(shí)現(xiàn)斷開(kāi)要?jiǎng)h除節(jié)點(diǎn)的目的/ p-adjvex=p -next-adjvex; p-next = p -

30、next -next; /刪除要?jiǎng)h除的節(jié)點(diǎn) q delete q;next 指學(xué)習(xí)文檔 僅供參考/輸出領(lǐng)接表void Print(Graph * G) ArcNode *p;for(int i=0; icount; i+) /先將 datacoutverticesi.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) coutadjvex;p=p-next;coutendl;coutendl;void makeVisitNull(Gra

31、ph * G)for(int i=0;ivisiti=0;學(xué)習(xí)文檔 僅供參考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 -visiti) G-visiti=1;coutadjvex;Dfs_part(G,i);/深度優(yōu)先遍歷void DFS(Graph * G,int i) coutverticesi.data;G-visiti=1;Dfs_part(G,i);/恢復(fù)makeVi

32、sitNull(G);coutendl;queue qList;void Bfs_part(Graph * G) int t= qList.front();學(xué)習(xí)文檔 僅供參考coutverticest.data;qList.pop();ArcNode *p=G -verticest.first_head -next;for(; p; p=p -next) 學(xué)習(xí)文檔 僅供參考int i=FindPosition(G,p - adjvex);if(!G -visiti) G-visiti=1;qList.push(i);if(!qList.empty()Bfs_part(G);BFS(Graph

33、* G,int i) G-visiti=1;qList.push(i);Bfs_part(G);/恢復(fù)makeVisitNull(G);coutendl;Graph * G=new Graph;int main() /void學(xué)習(xí)文檔 僅供參考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,

34、2,5);SetSucc1(G,3,5);SetSucc1(G,4,6);SetSucc1(G,4,5);Prin t(G);coutDFS:e ndl;DFS(G,O);coutBFS:e ndl;學(xué)習(xí)文檔僅供參考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ù)就是連通子圖的

35、個(gè)數(shù)。八、網(wǎng)絡(luò) G 的鄰接矩陣如下，試畫(huà)出該圖，并畫(huà)出它的一棵最小生成樹(shù)。r081011803013103040110407013070丿解:九、以下圖是一個(gè)無(wú)向帶權(quán)圖，請(qǐng)給出該圖的鄰接矩陣，并分別按Prim 算法和 Kruskal 算法求最小生成樹(shù)包括算法代碼和畫(huà)圖。十、代碼：#in elude #in elude #in elude #i nclude using n amespaee std;#defi ne INFINITE OxFFFFFFFF#defi ne VertexData un sig ned int / 頂點(diǎn)數(shù)據(jù)#defi ne UINTun sig ned int#de

36、fi ne vexCou nts 6 / 頂點(diǎn)數(shù)量char vextex = A, B, C, D, E, F ;struct node VertexData data;un sig ned int lowesteost; closedgevexCounts; /Prim 算法中的輔助信息typedef struct VertexData u;VertexData v;un sig ned int cost; 邊的代價(jià) Arc; /原始圖的邊信息void AdjMatrix(u nsig ned int adjMatvexCou nts) / 鄰接矩陣表示法學(xué)習(xí)文檔僅供參考學(xué)習(xí)文檔 僅供參考f

37、or (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 !=0) min = closedgei.lowestcost;

38、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) closedgei.data = s;學(xué)習(xí)文檔 僅供參考closedgei.l

39、owestcost = 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; i+) / 更新 v 中頂點(diǎn)最小代價(jià)邊信息if ( adjMatki closedgei.lowestcost) closedgei.data = k;closed

40、gei.lowestcost = adjMatki;void ReadArc(unsigned int adjMatvexCounts,vector &vertexArc) / 保存圖的邊代價(jià) 信息Arc * temp = NULL;for (unsigned int i = 0; i vexCounts; i+) for (unsigned int j = 0; j u = i;temp-v = j;temp-cost = adjMatij;vertexArc.push_back(*temp);學(xué)習(xí)文檔 僅供參考bool compare(Arc A, Arc B) return A.

41、cost B.cost ? true : false;bool FindTree(VertexData u, VertexData v,vectorvector &Tree) unsigned int index_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 不在一