數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)題目：改進(jìn)的最小生成樹算法專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：（一）班學(xué)號(hào)：1362810118，1362810107，1362810108學(xué)生姓名：王洪，汪妍，羅林芳目錄一、 問(wèn)題描述 1二、 需求分析 11. 性能需求 12. 功能需求 13. 問(wèn)題假設(shè) 2三、 準(zhǔn)備知識(shí) 21. 歐拉圖定義： 22. 歐拉圖相關(guān)定理： 33. 歐拉圖應(yīng)用： 3四、 算法和數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 41. 算法分析 42. 建立模型 41) 前期準(zhǔn)備 42) 確定模型 63. 具體算法實(shí)現(xiàn) 84. 時(shí)間復(fù)雜度分 95. 題目拓展 10五、 程序測(cè)試 111. 測(cè)試1（測(cè)試沒有度數(shù)為奇數(shù)的頂點(diǎn)） 112. 測(cè)試2（測(cè)試度數(shù)為奇數(shù)的定點(diǎn)有4個(gè)） 12六、 總結(jié) 121. 已完成部分 122. 后期設(shè)想 133. 課程設(shè)計(jì)思考與體會(huì) 13七、 參考文獻(xiàn) 13數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)摘要最小生成樹是數(shù)據(jù)結(jié)構(gòu)中圖的一種重要應(yīng)用，在圖中對(duì)于n個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹，最小生成樹就是在所有生成樹中總的代價(jià)最小的生成樹。本課程設(shè)計(jì)是以java語(yǔ)言來(lái)編寫，主要運(yùn)用了鄰接矩陣的存儲(chǔ)形式，和實(shí)現(xiàn)Collection接口的類來(lái)簡(jiǎn)化程序，實(shí)現(xiàn)生成最小生成樹。最小生成樹的應(yīng)用非常的廣，如礦井通風(fēng)設(shè)計(jì)和改造最優(yōu)化方面以及如何搭建最短的網(wǎng)絡(luò)線纜,構(gòu)建造價(jià)最低的通訊網(wǎng)絡(luò)。關(guān)鍵詞：java，最小生成樹；破圈法問(wèn)題描述一般都采用prim算法或者kruskal算法,兩個(gè)算法都很直接。prim算法其實(shí)就是disj算法的變形,只是更新策略和判斷策略不同而已。kruskal采用了不相交集和堆,寫出的算法也很簡(jiǎn)潔并且很好理解。而這兩者都是通過(guò)添加邊來(lái)構(gòu)造樹，最小生成樹還有一種大類就是破圈法。本文我們探究的是用破圈法來(lái)構(gòu)造樹，即連續(xù)刪除某些邊，從而破壞圖中的回路，直到圖中不存在回路為止，此時(shí)的圖就是生成樹。需求分析根據(jù)提示使用刪除邊的方法，我們想到了破圈算法。破圈算法是1975年由我國(guó)數(shù)學(xué)家管梅谷教授提出來(lái)的。破圈法基本思想：在給定的圖中任意找出一個(gè)回路，刪去該回路中權(quán)最大的邊。然后在余下的圖中再任意找出一個(gè)回路，再刪去這個(gè)新找出的回路中權(quán)最大的邊，……一直重復(fù)上述過(guò)程，直到剩余的圖中沒有回路。這個(gè)沒有回路的剩余圖便是最小生成樹。算法的基本思想：先將圖G的邊按權(quán)的遞減順序排列后,依次檢驗(yàn)每條邊,在保持連通的情況下,每次刪除最大權(quán)邊,直到余下n-1條邊為止。性能需求構(gòu)造數(shù)據(jù)的輸入形式和范圍輸入頂點(diǎn)數(shù)為int類型，范圍為0-100。數(shù)據(jù)結(jié)構(gòu)采用鄰接矩陣存儲(chǔ)圖。功能需求在給定的賦權(quán)的連通圖上任意找一個(gè)圈。在所找的圈中去掉一條權(quán)數(shù)最大的邊（若有兩條或者兩條以上權(quán)數(shù)相等的邊，則任意去掉其中一條）。重復(fù)1、2操作，直至余下的圖為最小生成樹。問(wèn)題假設(shè)假設(shè)本題涉及的無(wú)向圖是一個(gè)連通圖。準(zhǔn)備知識(shí)算法的理論基礎(chǔ)：定理1:任意圖G有支撐樹的充分必要條件是圖G是連通的。定理2:圖G=(V,E)是一個(gè)樹的充分必要條件是G是連通圖,且e=n-1。最小生成樹最小生成樹：一個(gè)有n個(gè)結(jié)點(diǎn)的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有n個(gè)結(jié)點(diǎn)，并且有保持圖連通的最少的邊，如圖1所示。圖1最小生成樹示意圖設(shè)G=(V,E)是無(wú)向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。E中的每一條邊（v,w）的權(quán)為W(v,w)。如果G的子圖G’是一棵包含G的所有頂點(diǎn)的樹，則稱G’為G的生成樹。生成樹上各邊權(quán)的總和稱為生成樹的耗費(fèi)。在G的所有生成樹中，耗費(fèi)最小的生成樹稱為G的最小生成樹。避圈法避圈法的主要思想就是：開始選一條最小權(quán)的邊，以后每一步中，總從與已選邊不構(gòu)成圈的那些未選邊中，選擇一條權(quán)最小的（每一步中，如果有兩條或兩條以上的邊都是權(quán)值最小的邊，則從中任選一條）。避圈法主要分為兩種：Prim算法和Kruskal算法，下面分別進(jìn)行介紹。Prim算法設(shè)G=(V,E)是連通帶權(quán)圖，V={1,2,…,n}。構(gòu)造G的最小生成樹Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就進(jìn)行如下的貪心選擇：選取滿足條件i∈S,j∈V–S，且c[i][j]最小的邊，將頂點(diǎn)j添加到S中。這個(gè)過(guò)程一直進(jìn)行到S=V時(shí)為止。在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。圖2顯示了某一帶權(quán)圖。最小生成樹的生成過(guò)程如下：13;c16;c;c3;c2;c最終得到的最小生成樹如圖3所示。圖2帶權(quán)圖G圖3帶權(quán)圖G的最小生成樹示意圖Kruskal算法給定無(wú)向連通帶權(quán)圖G=(V,E),V={1,2,...,n}。Kruskal算法構(gòu)造G的最小生成樹的基本思想是：(1)將G的n個(gè)頂點(diǎn)看成n個(gè)孤立的連通分支，并將所有的邊按權(quán)從小到大排序；(2)從第一條邊開始，依據(jù)每條邊的權(quán)值遞增的順序檢查每一條邊，并按照下述方法連接兩個(gè)不同的連通分支：當(dāng)查看到第k條邊(v,w)時(shí)，如果端點(diǎn)v和w分別是當(dāng)前兩個(gè)不同的連通分支T1和T2的端點(diǎn)時(shí)，就用邊(v,w)將T1和T2連接成一個(gè)連通分支，然后繼續(xù)查看第k+1條邊；如果端點(diǎn)v和w在當(dāng)前的同一個(gè)連通分支中，就直接查看第k+1條邊，這個(gè)過(guò)程一個(gè)進(jìn)行到只剩下一個(gè)連通分支時(shí)為止。此時(shí)，已構(gòu)成G的一棵最小生成樹。仍以圖2所示的帶權(quán)圖G為例說(shuō)明其最小生成樹的生成過(guò)程，生成過(guò)程如下所示：13;c146;c225;c336;c423;c5最終得到的最小生成樹和圖3所示是一樣的。破圈法破圈法可以描述如下：(1)如果我們給的連通圖G中沒有回路，那么G本身就是一棵生成樹；(2)若G中只有一個(gè)回路，則刪去G的回路上的一條邊（不刪除結(jié)點(diǎn)），則產(chǎn)生的圖仍是連通的且沒有回路，則得到的子圖就是圖G的一棵生成樹；(3)若G的回路不止一個(gè)，只要?jiǎng)h去每一個(gè)回路上的一條邊，直到G的子圖是連通沒有回路且與圖G有一樣的結(jié)點(diǎn)集，那么這個(gè)子圖就是一棵生成樹。由于我們破壞回路的方法可以不一樣，所以可得到不同的生成樹，但是在求最小生成樹的時(shí)候，為了保證求得的生成樹的樹權(quán)最小，那么在刪去回路上的邊的時(shí)候，總是在保證帶權(quán)圖仍連通的前提下刪掉權(quán)值較大的邊，保留權(quán)值較小的邊。破圈法就是在帶權(quán)圖的回路中找出權(quán)值最大的邊，將該邊去掉，重復(fù)這個(gè)過(guò)程，直到圖連通且沒有圈為止，保留下來(lái)的邊所組成的圖即為最小生成樹。下面仍利用圖1.1.2對(duì)破圈法進(jìn)行說(shuō)明。首先是去除權(quán)值大的邊，并且檢測(cè)去除該邊后整個(gè)圖是否連通，對(duì)于圖2來(lái)說(shuō)，即第一步去掉權(quán)值為6的邊，如圖4所示。圖4去掉權(quán)值為6的G的示意圖從圖中可以看出，去掉權(quán)值為6的邊后整個(gè)圖仍是連通的。所以接下來(lái)去除權(quán)值為5的邊，并且檢測(cè)去除該邊后圖是否連通，結(jié)果如圖5所示。由圖可知，去掉所有權(quán)值為5的邊會(huì)造成圖G不連通，因此23;c5這條邊是必須保留的。然后再去除權(quán)值為4的邊。由于權(quán)值為1、2、3、4的邊分別連接著獨(dú)立的節(jié)點(diǎn)，故都必須保留，得到的最小生成圖5去掉權(quán)值為5的G的示意圖樹結(jié)果與圖3也是一樣的。避圈法與破圈法比較Prim算法是從空?qǐng)D出發(fā)，將點(diǎn)進(jìn)行二分化，從而逐步加邊得到最小生成樹。它是近似求解算法，雖然對(duì)于大多數(shù)最小生成樹問(wèn)題都能求得最優(yōu)解，但相當(dāng)一部分求得的是近似最優(yōu)解，具體應(yīng)用時(shí)不一定很方便。但是它可以看作是很多種最小樹算法的概括，在理論上有一定的意義。Kruskal算法也是從空?qǐng)D出發(fā)。它是精確算法，即每次都能求得最優(yōu)解，但對(duì)于規(guī)模較大的最小生成樹問(wèn)題，求解速度較慢。破圈法是從圖G出發(fā)，逐步去邊破圈得到最小生成樹。它最適合在圖上工作，當(dāng)圖較大時(shí)，可以幾個(gè)人同時(shí)在各個(gè)子圖上工作，因此破圈法在實(shí)用上是很方便的。算法和數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)算法分析概要設(shè)計(jì)：當(dāng)仔細(xì)研究了課題并且考慮過(guò)后，我們都想到了破圈法，通過(guò)刪邊來(lái)構(gòu)造最小生成樹用拓?fù)浞诸愃惴?，找到圖中的圈。具體就是依次找到圖中度為1的頂點(diǎn)（可以保存在隊(duì)列里），刪除之（這里的刪除是暫時(shí)的，下次遍歷還要還原這些點(diǎn)），然后與其鄰接的頂點(diǎn)的入度-1，這樣往復(fù)操作，直到圖中已不存在入度為1的頂點(diǎn)，即所有的頂點(diǎn)的度都>=2，那么剩下的邊就都在環(huán)里了。當(dāng)然，如果沒剩下邊，說(shuō)明沒有環(huán)，算法結(jié)束。剩下的邊就都是環(huán)中的邊了，找一個(gè)權(quán)最大的刪去即可。再進(jìn)行1操作，直到圖中無(wú)圈，即所有的圈都已破掉，剩下的就是最小生成樹了。詳細(xì)設(shè)計(jì)：算法中的主要的主程序：voidintialGraph()：用于創(chuàng)建圖publicbooleanIsConnect()：并查集判斷圖連通性publicbooleanIsConnectedGraph()：檢查是否為連通圖publicvoidcreateGraph(Edge[]d)：根據(jù)邊集組創(chuàng)建一個(gè)圖publicList<Edge>createEdgeList()：由鄰接矩陣生成邊集列表intvertices()：返回圖的定點(diǎn)數(shù)intedges()：返回圖的邊數(shù)voidputEdge(Edgee)：填點(diǎn)邊voidremoveEdge(inti,intj)：刪除邊booleanfindEdge(inti,intj)：查找邊voidoutput()：輸出圖publicList<Integer>depthFirstSearch(intv)：深度優(yōu)先遍歷voidbreakLoopBST()：刪邊獲得最小生成樹 主程序main()的基本流程創(chuàng)建圖對(duì)象，自動(dòng)調(diào)用構(gòu)造方法初始化，輸入鄰接矩陣調(diào)用破圈法方法breakLoopBST()，生成最小生成樹調(diào)用output()輸出最小生成樹的鄰接矩陣程序結(jié)束建立模型先將圖G的邊按權(quán)的遞減順序排列,Ei為刪除邊集。具體步驟為第1步:令i=1,E0=Φ,G0=G;第2步:取邊ei∈E(Gi-1)即E\Ei-1,令Ei=Ei-1∪{ei},使得Gi=G[E\Ei]連通,且W(ei)權(quán)盡可能大;第3步:若i<e-n+1,令i=i+1,返回第2步,否則,Gi=G[E\Ei]把Ei中的邊全部刪除,即是所求的最小支撐樹數(shù)學(xué)模型如圖：算法的偽代碼實(shí)現(xiàn)算法：AdjacencyGraph(intn)輸入：圖的階數(shù)n輸出：任意的一個(gè)構(gòu)造圖1->a=newint[n][n];2->forinti=0;i<n;i++;3->for(inti=0;i<n;i++){For(intj=0;j<i+1;j++)}判斷圖的連通性算法：booleanIsConnectedGraph()輸入：圖輸出：true或者false1->for(inti=0;i<n;i++){set1.add(i);}，圖頂點(diǎn)集合2->if(!set1.equals(set2))，深搜得到便利點(diǎn)的集合，與圖頂點(diǎn)集合比較Returnfalse;,返回比較結(jié)果為連通性判斷。elsereturntrue;算法：深度優(yōu)先遍歷ArrayList<Integer>depthFirstSearch(intv)輸入節(jié)點(diǎn)數(shù)n輸出：是否訪問(wèn)過(guò)1->boolean[]visited=newboolean[n]2->for(i=0;i<n;i++)3->returndsplist算法;輸出圖breakLoopBST()輸入:排序后的列表輸出:最小生成樹1->collection.sort(1)，邊按升序排序2->collection.reserve(1)，邊排序反轉(zhuǎn)成降序3->for(i=0;i<n;i++)，遍歷刪除每條邊，若保持連通性，刪除之，否則保留。4->break深度搜索盡管能得到結(jié)果，但效率卻比prim算法差了更多，借鑒prim算法并查集判斷圖的連通性的思想，對(duì)算法進(jìn)行優(yōu)化，將連通性判斷改為并查集，提高效率，給出算法偽代碼如下：核心算法的優(yōu)化采用并查集判斷連通性算法

boolean

IsConnect()1->for(int

i

=

0

;i

<

n

;

i

++)

，初始化父親節(jié)點(diǎn)

2->ArrayList<Edge>

l

=new

ArrayList<Edge>(createEdgeList())，以邊關(guān)系更新父親節(jié)點(diǎn)

3->for(int

j=0;j<l.size();j++)4->for(int

k=0;k<n;k++)，尋找父節(jié)點(diǎn)的父節(jié)點(diǎn)，直至更新至根節(jié)點(diǎn)

5->for(inti=0;i<n;i++)，判斷圖中節(jié)點(diǎn)的父親節(jié)點(diǎn)是否統(tǒng)一6->returntrueorfalse

，輸入圖的連通性b.算法的具體實(shí)現(xiàn)：見附錄1：

算法復(fù)雜度分析經(jīng)分析，影響算法主要決定因素是深度遍歷和并查集的遞歸次數(shù)，分別對(duì)采用不同方法效率進(jìn)行分析如下：該算法采用深度搜索判斷圖的連通性的時(shí)間復(fù)雜度為：O（n2）；算法采用并查集判斷圖的連通性的時(shí)間復(fù)雜度為：O（n（n+1）/2）；由此可知，并查集極大的改進(jìn)了算法效率。以頂點(diǎn)為4的無(wú)向圖為例（鄰接矩陣）：047827647041638241072 7663720最小生成樹（鄰接矩陣）：047∞∞4704163∞410∞∞63∞0在生成最小生成樹的過(guò)程中采用深度搜索判斷圖的連通性遞歸次數(shù)為：3+3+3=9次，而使用并查集的方法判斷圖的連通性遞歸次數(shù)為：1+2+3=6>9次。由此可以看出，使用并查集判斷連通性的效率遠(yuǎn)高于深度搜索。

題目拓展提出問(wèn)題對(duì)于我們已經(jīng)實(shí)現(xiàn)的算法的結(jié)果，執(zhí)行的算法效率依然有待高，有沒有更簡(jiǎn)單的優(yōu)化算法來(lái)實(shí)現(xiàn)生成最小生成樹。算法分析可以采用鄰接多重表的方式來(lái)進(jìn)行動(dòng)態(tài)優(yōu)化算法：首先初始化數(shù)組和頂點(diǎn)遍歷數(shù)組，將滿足條件的頂點(diǎn)加入集合循環(huán)判斷在其他頂點(diǎn)中選擇滿足條件的權(quán)值最小的邊五程序測(cè)試測(cè)試1（測(cè)試不能構(gòu)成圖時(shí)能否得到最小生成樹）頂點(diǎn)數(shù)必須大于大于等于2才會(huì)有邊輸入信息：預(yù)測(cè)結(jié)果至少可以得到一條邊實(shí)際輸出結(jié)果如圖4.1所示圖4.1測(cè)試1實(shí)際輸出結(jié)果結(jié)果分析 根據(jù)輸出結(jié)果分析，當(dāng)頂點(diǎn)數(shù)為2時(shí)只能有一條邊，構(gòu)不成圖，由于我們是采用刪除邊的方法，當(dāng)只有一條邊的時(shí)候也不用刪除，直接輸出。測(cè)試2（測(cè)試頂點(diǎn)數(shù)是3最小并且為最小連通圖時(shí)的情況）輸入信息預(yù)測(cè)結(jié)果至少需要機(jī)器狗的數(shù)目為2應(yīng)該只剩下其中的兩條邊，并且滿足是最小生成樹實(shí)際輸出如圖4.2所示圖4.2測(cè)試2實(shí)際輸出結(jié)果結(jié)果分析 得到的結(jié)果確實(shí)為只有兩條邊構(gòu)成的生成樹，而且是最小生成樹滿足要求，符合題意。測(cè)試3（測(cè)試頂點(diǎn)數(shù)為其他數(shù)防止偶然的情況發(fā)生）輸入信息預(yù)測(cè)結(jié)果至少輸出的結(jié)果應(yīng)該為只有5條邊構(gòu)成的最小生成樹實(shí)際輸出如圖4.2所示圖4.2測(cè)試2實(shí)際輸出結(jié)果結(jié)果分析 得到的經(jīng)過(guò)將矩陣轉(zhuǎn)換為圖形，滿足我們所要求的是最小生成樹，并且只有5條邊符合題意。六總結(jié)后期設(shè)想已完成部分完成題目要求，采用刪除某些邊，破壞圖中的回路，直到圖中不存在回路為止，此時(shí)得到的生成樹就是最小生成樹。這種方法與老師上課講的prime和kruskal算法在思想上有很大的不同，后兩者采用的是加邊的方法，將邊一條一條加入生成一棵最小生成樹，而我們采用的這種俗稱叫做破圈法，既是將邊一條一條刪除最后得到一棵最小生成樹。通過(guò)實(shí)驗(yàn)讓我們更加懂得有時(shí)候解決問(wèn)題可以從相反的方向去思考，不能墨守成規(guī)，一成不變，要有創(chuàng)新后期設(shè)想我們能不能再進(jìn)一步改進(jìn)算法，實(shí)現(xiàn)更加高效的程序，學(xué)習(xí)算法的目的也是在于優(yōu)化程序，在采用刪除邊的方法的同時(shí)更主要實(shí)現(xiàn)效率的提高，這也促使我們對(duì)于這個(gè)問(wèn)題要有更深的理解和認(rèn)識(shí)，以及在解決問(wèn)題的時(shí)候我們應(yīng)該考慮的更加全面，更加具體和詳細(xì)。程序設(shè)計(jì)思考與體會(huì)經(jīng)過(guò)我們不懈的努力我們終于完成了本次課程設(shè)計(jì)，通過(guò)這次課程設(shè)計(jì)，我感覺到要真正做出一個(gè)程序并不很容易，但只要用心去做，總會(huì)有收獲，特別是當(dāng)我遇到一個(gè)問(wèn)題，想辦法去解決，最后終于找到方法時(shí)，心里的那份喜悅之情真是難以形容。編寫程序中遇到問(wèn)題再所難免，應(yīng)耐心探究其中的原因，從出現(xiàn)問(wèn)題的地方起，并聯(lián)系前后程序，仔細(xì)推敲，逐個(gè)排查。直到最終搞清為止。我們本次做的是圖的最小生成樹問(wèn)題，該算法主要側(cè)重于找邊、刪邊的過(guò)程，通過(guò)這個(gè)方法求到的最小生成樹和別的算法相比，主要是算法簡(jiǎn)單，結(jié)構(gòu)清晰，在程序?qū)崿F(xiàn)中只是用到了數(shù)組和循環(huán)語(yǔ)句的知識(shí)，程序簡(jiǎn)單明了。因?yàn)槠迫Ψㄅc避圈法是兩種不同的解題思維，通過(guò)本次課程設(shè)計(jì)讓我更加知道“條條大路通羅馬”，平時(shí)應(yīng)該變換角度得來(lái)思考問(wèn)題。七參考文獻(xiàn)[1]屈婉玲.離散數(shù)學(xué)[M].北京：高等教育出版社，2008.[2]葉核亞.數(shù)據(jù)結(jié)構(gòu)（Java版）[M].北京：電子工業(yè)出版社，2011.[3]屈婉玲.算法設(shè)計(jì)與分析[M].北京：高等教育出版社，2008.[4]Java編程思想第四版，BruceEckel著陳昊鵬譯，機(jī)械工業(yè)出版社，2012.11[5]龍亞.圖的連通性算法探討[J].畢節(jié)師范高等?？茖W(xué)校學(xué)報(bào)，2002附錄1：a.Graph.java:importjava.util.*;publicinterfaceGraph{//圖的接口，包含圖的操作 voidintialGraph();//創(chuàng)建圖 publicbooleanIsConnectedGraph();//檢查是否為連通圖 publicvoidcreateGraph(Edge[]d);//根據(jù)邊集組創(chuàng)建一個(gè)圖 publicList<Edge>createEdgeList();//由鄰接矩陣生成邊集列表 intvertices();//返回圖的定點(diǎn)數(shù) intedges();//返回圖的邊數(shù) voidputEdge(Edgee);//填點(diǎn)邊 voidremoveEdge(inti,intj);//刪除邊 booleanfindEdge(inti,intj);//查找邊 voidoutput();//輸出圖 publicList<Integer>depthFirstSearch(intv);//深度優(yōu)先遍歷 voidbreakLoopBST();//刪邊獲得最小生成樹 }publicclassEdgeimplementsComparable<Edge>{//邊元素 intfromvex;intendvex;intweight;//邊的兩個(gè)點(diǎn)與權(quán)重 publicEdge(intv1,intv2,intwgt) { fromvex=v1; endvex=v2; weight=wgt; } publicintgetFromvex() { returnfromvex; } publicintgetEndvex(){returnendvex;} publicintgetWeight(){returnweight;} @Override//邊集元素的構(gòu)造方法//獲取邊元素的點(diǎn)和權(quán)重?cái)?shù)據(jù) publicintcompareTo(Edgee){//覆蓋comparaTo方法returnweight>e.weight?1:(weight<e.weight?-1:0);} @OverridepublicStringtoString() {return"("+fromvex+","+endvex+")"+weight;}//覆蓋toString方法 }AdjacencyGraphy.javaimportjava.util.ArrayList;importjava.util.Collections;importjava.util.HashSet;importjava.util.List;//importjava.util.Random;importjava.util.Scanner;publicclassAdjacencyGraphyimplementsGraph{ finalintMaxValue=1000;//一個(gè)不存在的邊的權(quán)值 intn;//頂點(diǎn)數(shù) inte;//邊數(shù) int[][]a;//鄰接矩陣publicAdjacencyGraphy(intn){//初始化 this.n=n; e=0; a=newint[n][n]; for(inti=0;i<n;i++) for(intj=0;j<n;j++) { if(i==j)a[i][j]=0; else a[i][j]=MaxValue; } }publicintgetMaxValue(){returnMaxValue;}publicAdjacencyGraphy(){intialGraph();}/**********************實(shí)現(xiàn)接口中的方法*********************************/publicvoidintialGraph(){ System.out.print("請(qǐng)輸入圖的頂點(diǎn)數(shù)：");Scanners=newScanner(System.in);n=s.nextInt();a=newint[n][n];//Randomrandom1=newRandom(100);//System.out.println("請(qǐng)輸入圖鄰接矩陣（無(wú)邊的權(quán)值為1000）：");for(intk=0;k<n;k++) a[k][k]=0;for(inti=0;i<n;i++) for(intj=i+1;j<n;j++) { a[i][j]=a[j][i]=(int)(Math.random()*100)+1; }s.close();}publicbooleanIsConnect(){//并查集判斷連通性 int[]father=newint[n]; for(inti=0;i<n;i++) father[i]=i; ArrayList<Edge>l=newArrayList<Edge>(createEdgeList()); for(intj=0;j<l.size();j++) { intstart=l.get(j).getFromvex(); intdest=l.get(j).getEndvex(); father[dest]=start; } for(intk=0;k<n;k++) { father[k]=get_father(k,father); } for(inti=0;i<n;i++) if(father[i]!=0) returnfalse; returntrue;}privateintget_father(intk,int[]father){ if(k==father[k]) returnk; else returnget_father(father[k],father);}publicbooleanIsConnectedGraph(){//檢查是否為連通圖 HashSet<Integer>set1=newHashSet<Integer>(); for(inti=0;i<n;i++){set1.add(i);} intm=(int)Math.random()*n; HashSet<Integer>set2=newHashSet<Integer>(depthFirstSearch(m)); if(!set1.equals(set2)) returnfalse; else returntrue; }publicvoidcreateGraph(Edge[]d){//根據(jù)邊集組創(chuàng)建一個(gè)圖 for(intt=0;t<d.length;t++) {putEdge(d[t]);} }publicList<Edge>createEdgeList(){//由鄰接矩陣生成邊集列表 ArrayList<Edge>l=newArrayList<Edge>(); for(inti=0;i<n;i++) for(intj=i+1;j<n;j++) {if(a[i][j]<MaxValue) { l.add(newEdge(i,j,a[i][j])); } } returnl; }publicintvertices(){returnn;}publicintedges(){returne;}//返回圖的定點(diǎn)數(shù)//返回圖的邊數(shù)publicvoidputEdge(Edgee){//填點(diǎn)邊 inti=e.getFromvex(); intj=e.getEndvex(); intw=e.getWeight(); if(a[i][j]!=0&&a[i][j]!=MaxValue) System.out.println("已經(jīng)存在該邊，不能繼續(xù)添加"); else {a[i][j]=w; a[j][i]=w; }}publicvoidremoveEdge(inti,intj){//刪除邊 a[i][j]=MaxValue;a[j][i]=MaxValue; }publicbooleanfindEdge(inti,intj){//查找邊 if(a[i][j]>0&&a[i][j]<MaxValue) returntrue; else returnfalse; }publicvoidoutput(){//輸出圖 for(inti=0;i<n;i++) { for(intj=0;