軟件綜合實(shí)習(xí)報(bào)告合集-文庫(kù)吧在線文庫(kù)

　　

【正文】 對(duì)于最小生成樹生成過程中邊相關(guān)變量的存儲(chǔ)均是通過定義一個(gè)邊（ edge）的結(jié)構(gòu)體變量進(jìn)行存儲(chǔ)的，而關(guān)于點(diǎn)的存儲(chǔ)則是通過定義數(shù)組進(jìn)行相應(yīng)的存儲(chǔ)，由于不同的實(shí)現(xiàn)方法采用的初始值不一樣，因此使用的數(shù)組會(huì)有所不同。首先從圖 G 的頂點(diǎn)集 V(G)中任選一個(gè)頂點(diǎn)，把它加到最小生成樹MST 的頂點(diǎn)集 V(MST)中。 （ 2）集合 V(MST)此時(shí)已經(jīng)有兩個(gè)頂點(diǎn)了，即 2，找到與之相連的符合條件的邊 (v2,v3)將權(quán)值為 1的邊添加到 E(MST)中，并將頂點(diǎn)3 添加到 V(MST)中并畫出此邊。 Prime算法的設(shè)計(jì)與實(shí)現(xiàn)如下所述： （ 1）對(duì)所畫區(qū)域刷新。首先將圖中所有邊按權(quán)值遞增順序排列，依次選定取 權(quán)值較小的邊，但要求后面選取的邊不能與前面選取的邊構(gòu)成回路，若構(gòu)成回路，則放棄該條邊，再去選后面權(quán)值較大的邊。 （ 3）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 2,4）并畫出此邊，其權(quán)重為 2。 （ 2）設(shè)置查找到的頂點(diǎn)集合 find[n]所有的值為 1，存儲(chǔ)邊的集合 E[n1]為空集。在程序中也實(shí)現(xiàn)了并查集的動(dòng)態(tài)演示，通過 Kruskal 算法調(diào)用并查集的函數(shù)，在函數(shù)中對(duì)相關(guān)的頂點(diǎn)信息進(jìn)行判斷從而實(shí)施相應(yīng)的畫圖操作。通過判斷畫出發(fā)生改變的集合 { 7}。此時(shí)集合變?yōu)?{1}、 { 7}。 并查集的實(shí)現(xiàn)主要包含三個(gè)方面，即并查集的初始化、查找和集合的合并，下面主要介紹并查集這三個(gè)過程的設(shè)計(jì)與實(shí)現(xiàn)。在這里采用的是加權(quán)合并，即把兩個(gè)集合中元素個(gè)數(shù)少的根結(jié)點(diǎn)作為元素個(gè)數(shù)多的根節(jié)點(diǎn)的子結(jié)點(diǎn)。下面僅給出在邊已經(jīng)通過權(quán)值大小進(jìn)行排序之后，邊通分量的查找的過程和查找之后集合的合并情況（ 1）得到圖 G 中最小權(quán)值的邊（ 2,3），因?yàn)椋?2,3）排在（ 6,7）的前面，所以先判斷它的兩個(gè)結(jié)點(diǎn)，判斷點(diǎn) 2 和點(diǎn) 3 是否已經(jīng)訪問過了，由于數(shù)組 check 中相應(yīng)的值為 0，說 明沒有被訪問過，因此合并這兩個(gè)結(jié)點(diǎn)為一個(gè)集合 { 3}。 （ 5）繼續(xù)向下查找得到邊（ 4,6），判斷點(diǎn) 4 和點(diǎn) 6 是否已經(jīng)訪問過了得知點(diǎn) 4 已經(jīng)被訪問過了，點(diǎn) 6沒有，因此得到新的集合 {2,、 7}。因此主要包含兩個(gè)方面，即棧這一數(shù)據(jù)結(jié)構(gòu)中相關(guān)函數(shù)的設(shè)計(jì)與實(shí)現(xiàn)，以及如何實(shí)現(xiàn)深度優(yōu)先搜索算法判斷變量通分量的設(shè)計(jì)與實(shí)現(xiàn)。 （ 5）當(dāng)最小生成樹生成完畢時(shí)，則調(diào)用 Draw（ E）函數(shù)畫出生成的過程。 設(shè)計(jì)與實(shí)現(xiàn)在這里采用 Kruskal 算法得到最小生成樹的過程中，在對(duì)邊連通分量的查詢時(shí)使用了廣度優(yōu)先搜索的方法來查詢當(dāng)前得到的具有最下權(quán)值的邊的兩個(gè)頂 點(diǎn)是不是已經(jīng)存在于被訪問過的結(jié)點(diǎn)的集合中，如果是的則進(jìn)行下一次查詢，否則的話則將沒有訪問過的結(jié)點(diǎn)加入已經(jīng)訪問過的結(jié)點(diǎn)的集合中。 （ 3）如果都已經(jīng)被訪問過了，則利用廣度優(yōu)先搜索判斷這兩個(gè)節(jié)點(diǎn)是否屬于同一個(gè)集合，如果是的話則拋棄此邊，如果不是的話則對(duì)其進(jìn)行標(biāo)記，并畫出此邊和相對(duì)應(yīng)的點(diǎn)。通過這些 可知其生成的最小生成樹只能有七個(gè)頂點(diǎn)、六條邊。 廣度優(yōu)先搜索實(shí)現(xiàn) Kruskal算法的測(cè)試結(jié)果 圖（ 7） 通過與其他方法實(shí)現(xiàn) kruska 算法進(jìn)行對(duì)比，可知結(jié)果是一致的。 Kruskal 算法的時(shí)間復(fù)雜度與選取的排序函數(shù)有關(guān)，這里采用的是不是對(duì)其進(jìn)行排序而是在每一次循環(huán)中找余下的邊中權(quán)值最小的邊，找到最小的邊之后將對(duì)其相應(yīng)的點(diǎn)進(jìn)行標(biāo)記，已知點(diǎn)的個(gè)數(shù)為 n 邊的個(gè)數(shù)為 e，所以它的時(shí)間復(fù)雜度為最壞的情況下為 O(e^2)，如果邊已經(jīng)很有序的話，也就是最好的情況下的時(shí)間復(fù)雜度為 O(n^2)。 在最初選擇題目的時(shí)候，總是覺得自己對(duì)使用 MFC 來畫圖這一方面不是很熟悉，擔(dān)心自己做不出來。 許多應(yīng)用問題都是一個(gè)求無(wú)向連通圖的最小生成樹問題。除此之外，在最小生成樹的求解過程中會(huì)對(duì)邊通分量進(jìn)行查詢和合并，由題可知要對(duì)邊 通 分 量 進(jìn) 行 查 詢 和 合 并 要 使 用 廣 度 優(yōu) 先 搜 索 算 法（ BreadthFirstSearch）、深度優(yōu)先搜索算法 (DepthFirstSearch)和并查集（ UnionFindSet）這三種方法。在對(duì)圖進(jìn)行相關(guān)操作尋找最小生成樹時(shí)，得到的生成樹中的邊采用的是結(jié)構(gòu)體的存儲(chǔ)方式，在實(shí)現(xiàn)的過程中相關(guān)變量和數(shù)據(jù)的存儲(chǔ)也主要通過數(shù)組、結(jié)構(gòu)體來實(shí)現(xiàn)了。通過這樣的一個(gè)遍歷過程與畫圖的相關(guān)操作結(jié)合來實(shí)現(xiàn)最小生成樹生成過程的動(dòng)態(tài)演示。通過判斷先找出所有這樣的邊。 （ 6）集合 V(MST)此時(shí)已經(jīng)有六個(gè)頂點(diǎn)了，即 6，找到與之相連的符合條件的邊 (v6,v7)將權(quán)值為 1 的邊添加到 E(MST)中，并將頂點(diǎn) 7 添加到 V(MST)中并畫出此邊。根據(jù)lowCost 的定義，這樣的邊其一個(gè)頂點(diǎn)必然為集合 V(MST)中的頂點(diǎn)，其另一個(gè)頂點(diǎn)（設(shè)第 k 個(gè)頂點(diǎn)）必然為集合 V(G)－ V(MST)中的頂點(diǎn)，將相應(yīng)的邊添加到 E[n1]中。 （ 2） 在原 圖 G 中的邊中選擇具有最小權(quán)值的邊，若該邊的兩個(gè)頂點(diǎn)落在不同的連通分量上，則將此邊加入到 T 中；否則，則將此邊舍去（此后永不選入此邊），重新選擇一條權(quán)值最小的邊并進(jìn)行畫圖的操作處理。 至此通過 kruskal 算法得到最小生成樹及生成過程，其最小生成樹的權(quán)值為 16。 lkruskal算法動(dòng)態(tài)演示模塊 基本思想并查集處理問題的主要思想是在處理時(shí)使用搜索與合并運(yùn)算對(duì)相關(guān)集合進(jìn)行處理。此時(shí)集合變?yōu)?{1}、 { 3}、 {4}、 {5}、 {6}、 {7}。 （ 5）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 4,5）并畫出此邊，其權(quán)重為 3。通過判斷畫出發(fā)生改變的集合 { 7}。 （ 3）查找：主要是查找并返回結(jié)點(diǎn) i 所屬集合的根節(jié)點(diǎn)。通常是利用遞歸來實(shí)現(xiàn)圖中結(jié)點(diǎn)的遍歷。 （ 3）繼續(xù)向下查找得到邊（ 2,4），判斷點(diǎn) 2 和點(diǎn) 4 是否已經(jīng)訪問過了得知點(diǎn) 2 已經(jīng)被訪問過了，點(diǎn) 4沒有，因此得到新的集合 {2,、 4}。下面僅給出在邊已經(jīng)通過權(quán)值大小進(jìn)行排序之后，邊通分量的查找的過程和查找之后集合的合并情況（ 1）得到圖 G 中最小權(quán)值的邊（ 2,3），因?yàn)椋?2,3）排在（ 6,7）的前面，所以先判斷它的兩個(gè)結(jié)點(diǎn)，判斷點(diǎn) 2 和點(diǎn) 3 是否已經(jīng)訪問過了，由于數(shù)組 check 中相應(yīng)的值為 0，說明沒有被訪問過，因此合并這兩個(gè)結(jié)點(diǎn)為一個(gè)集合 { 3}。在這里采用的是加權(quán)合并，即把兩個(gè)集合中元素個(gè)數(shù)少的根結(jié)點(diǎn)作為元素個(gè)數(shù)多的根節(jié)點(diǎn)的子結(jié)點(diǎn)。 并查集的實(shí)現(xiàn)主要包含三個(gè)方面，即并查集的初始化、查找和集合的合并，下面主要介紹并查集這三個(gè)過程的設(shè)計(jì)與實(shí)現(xiàn) 。此時(shí)集合變?yōu)?{1}、 { 7}。通過判斷畫出發(fā)生改變的集合 { 7}。在程序中也實(shí)現(xiàn)了并查集的動(dòng)態(tài)演示，通過 Kruskal 算法調(diào)用并查集的函數(shù)，在函數(shù)中對(duì)相關(guān)的頂點(diǎn)信息進(jìn)行判斷從而實(shí)施相應(yīng)的畫圖操作。 （ 2）設(shè)置查找到的頂點(diǎn)集合 find[n]所有的值為 1，存儲(chǔ)邊的集合 E[n1]為空集。 （ 3）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 2,4）并畫出此邊，其權(quán)重為 2。首先將圖中所有邊按權(quán)值遞增順序排列，依次選定取權(quán)值較小的邊，但要求后面選取的邊不能與前面選取的邊構(gòu)成回路，若構(gòu)成回路，則放棄該條邊，再去選后面權(quán)值較大的邊。 Prime算法的設(shè)計(jì)與實(shí)現(xiàn)如下所述： （ 1）對(duì)所畫區(qū)域刷新。 （ 2）集合 V(MST)此時(shí)已經(jīng)有兩個(gè)頂點(diǎn)了，即 2，找到與之相連的符合條件的邊 (v2,v3)將權(quán)值為 1的邊添加到 E(MST)中，并將頂點(diǎn)3 添加到 V(MST)中并畫出此邊。首先從圖 G 的頂點(diǎn)集 V(G)中任選一個(gè)頂點(diǎn)，把它加到最小生成樹MST 的頂點(diǎn)集 V(MST)中。 對(duì)于最小生成樹生 成過程中邊相關(guān)變量的存儲(chǔ)均是通過定義一個(gè)邊（ edge）的結(jié)構(gòu)體變量進(jìn)行存儲(chǔ)的，而關(guān)于點(diǎn)的存儲(chǔ)則是通過定義數(shù)組進(jìn)行相應(yīng)的存儲(chǔ)，由于不同的實(shí)現(xiàn)方法采用的初始值不一樣，因此使用的數(shù)組會(huì)有所不同。在這里我選擇了將這三種搜索算法融合到 Kruskal算法，因?yàn)槲矣X得在 Kruskal算法對(duì)邊通分量進(jìn)行查詢和合并中使用這三種方法更合理且更容易實(shí)現(xiàn)，因此也實(shí)現(xiàn)了將這三種搜索算法融合到 Kruskal 算法從而實(shí)現(xiàn)對(duì)圖的最小生成樹的查找。并對(duì)兩種算法進(jìn)行分析和比較。 雖然做的時(shí)候還是很多都不熟悉，但是我知道如果我不嘗試這去做的話就真的什么也做不出來了。在我的程序中已經(jīng)實(shí)現(xiàn)了對(duì)給出的這一例子使用Prime 算法、 Kruskal算法求解最小生成樹的運(yùn)算過程的動(dòng)態(tài)顯示，除此 之外，對(duì)于還實(shí)現(xiàn)了在邊通分量的查詢與合并的過程中，采用廣度優(yōu) 先 搜 索 算 法 （ BreadthFirstSearch ）、 深 度 優(yōu) 先 搜 索 算 法(DepthFirstSearch)和并查集（ UnionFindSet）三種方法來實(shí)現(xiàn)對(duì)此例中圖的最小生成樹的求解，主要是將這三種搜索方法與 Kruakal 結(jié)合來實(shí)現(xiàn)對(duì)最小生成樹的求解。遍歷圖的過程實(shí)質(zhì)上是通過邊或弧找鄰接點(diǎn)的過程。 并查集實(shí)現(xiàn) Kruskal算法的測(cè)試結(jié)果 圖 (5) 此圖中首先給出了最初集合的狀況，緊接著給出了每一次進(jìn)行邊通分量查找合并過程中發(fā)生變化的集合的狀況。 對(duì)于最小生成樹的繪制過程有一個(gè)函數(shù)承擔(dān)，主要是實(shí)現(xiàn)程序在調(diào)用 prime 算法、 kruskal 算法、 深度優(yōu)先搜索實(shí)現(xiàn)的 kruskal 算法和廣度優(yōu)先搜索實(shí)現(xiàn)的 kruskal算法的過程中 相關(guān)運(yùn)行過程的繪制，此處主要通過判斷最小生成樹中所存儲(chǔ)的邊來進(jìn)行繪制。 （ 1）隊(duì)列： 這里使用到的與隊(duì)列相關(guān)的操作主要有棧中數(shù)據(jù)的初始化QueueInitiate、將數(shù)據(jù)存入隊(duì)列的操作 QueueAppend、將數(shù)據(jù) 從隊(duì)列中刪除的操作 QueueDelete、判斷隊(duì)列是否為空的操作 QueueNotEmpty。 kruskal 算法利用廣度優(yōu)先搜索進(jìn)行邊通分量的查詢和合并的的實(shí)現(xiàn)過程中，邊通分量的查找和合并雖然是廣度優(yōu)先搜索為主，但是總體是以最小生成樹的的生成過程為主，因此 這里所采用的畫圖操做運(yùn)行的情況和使用一般的方法實(shí)現(xiàn)kruskal 算法的運(yùn)行過程是一樣的，在這里不再給予詳細(xì)的說明，如有必要?jiǎng)t可以參照 kruskal 的生成最小生成樹的過程。 下面給出 kruakal 算法利用深度優(yōu)先搜索進(jìn)行邊連通分量查詢和合并從而得到最小生成樹的的設(shè)計(jì)與實(shí)現(xiàn)步驟： （ 1）對(duì)所畫區(qū)域進(jìn)行刷新。同時(shí)通過深度優(yōu)先搜索對(duì)著兩個(gè)結(jié)點(diǎn)分別進(jìn)行判斷是否需要標(biāo)記，可知點(diǎn) 1 此時(shí)被標(biāo)記訪問過了。 （ 3）繼續(xù)向下查找得到邊（ 2,4），判斷點(diǎn) 2 和點(diǎn) 4 是否已經(jīng)訪問過了得知點(diǎn) 2 已經(jīng)被訪問過了，點(diǎn) 4沒有，因此得到新的集合 {2,、 4}。通常是利用遞歸來實(shí)現(xiàn)圖中結(jié)點(diǎn)的遍歷。 （ 3）查找：主要是查找并返回結(jié)點(diǎn) i 所屬集合的根節(jié)點(diǎn)。通過判斷畫出發(fā)生改變的集合 { 7}。 （ 5）在圖 G 的邊的集合 E 中選擇權(quán)值最小的邊（ 4,5）并畫出此邊，其權(quán)重為 3。此時(shí)集合變?yōu)?{1}、 { 3}、 {4}、 {5}、 {6}、 {7}。 lkruskal算法動(dòng)態(tài)演示模塊 基本思想并查集處理問題的主要思想是在處理時(shí)使用搜索與合并運(yùn)算對(duì)相關(guān)集合進(jìn)行處理。 至此通過 kruskal 算法得到最小生成樹及生成過程，其最小生成樹的權(quán)值為 16。 （ 2） 在原圖 G 中的邊中選擇具有最小權(quán)值的邊，若該邊的兩個(gè)頂點(diǎn)落在不同的連通分量上，則將此邊加入到 T 中；否則，則將此邊舍去（此后永不選入此邊），重新選擇一條權(quán)值最小的邊并進(jìn)行畫圖的操作處理。根據(jù)lowCost 的定義，這樣的邊其一個(gè)頂點(diǎn)必然為集合 V(MST)中的頂點(diǎn)，其另一個(gè)頂點(diǎn)（設(shè)第 k 個(gè)頂點(diǎn)）必然為集合 V(G)－ V(MST)中的頂點(diǎn)，將相應(yīng)的邊添加到 E[n1]中。 （ 6）集合 V(MST)此時(shí)已經(jīng)有六個(gè)頂點(diǎn)了，即 6，找到與之相連的符合條件的邊 (v6,v7)將權(quán)值為 1 的邊添加到 E(MST)中，并將頂點(diǎn) 7 添加到 V(MST)中并畫出此邊。通過判斷先找出所有這樣的邊。通過這樣的一個(gè)遍歷過程與畫圖的相 關(guān)操作結(jié)合來實(shí)現(xiàn)最小生成樹生成過程的動(dòng)態(tài)演示。在對(duì)圖進(jìn)行相關(guān)操作尋找最小生成樹時(shí)，得到的生成樹中的邊采用的是結(jié)構(gòu)體的存儲(chǔ)方式，在實(shí)現(xiàn)的過程中相關(guān)變量和數(shù)據(jù)的存儲(chǔ)也主要通過數(shù)組、結(jié)構(gòu)體來實(shí)現(xiàn)了。除此之外，在最小生成樹的求解過程中會(huì)對(duì)邊通分量進(jìn)行查詢和合并，由題可知要對(duì)邊 通 分 量 進(jìn) 行 查 詢 和 合 并 要 使 用 廣 度 優(yōu) 先 搜 索 算 法（ BreadthFirstSearch）、深度優(yōu)先搜索算法 (DepthFirstSearch)和并查集（ UnionFindSet）這三種方法。 許多應(yīng)用問題都是一個(gè)求無(wú)向連通圖的最小生成樹問題。較高的要求是在