軟件綜合實習報告合集(存儲版)

　　

【正文】 ??????????????? .2 基 本 思想???????????????????????????????????????? 2 設 計 與 實現?????????????????????????????????????? ..3 Kruskal 算 法 動 態 演 示 模塊?? ????????????????????????? .4 基 本 思想???????????????????????????????????????? 4 設 計 與 實現??????????????????????????????????????? 4 并 查 集 實 現 kruskal 算 法 動 態 演 示 模塊?????????????????? ..4 基 本 思想???????????????????????????????????????? 5 設 計 與 實現??????????????????????????????????????? 5 深 度 優 先 搜 索 實 現 Kruskal 算 法 動 態 演 示 模塊???????????? .6 基 本 思想???????????????????????????????????????? 6 設 計 與 實現??????????????????????????????????????? 7 廣度優先搜索實現 Kruskal 算法動態演示模塊???????????? .7 基 本 思想???????????????????????????????????????? 7 設 計 與 實現??????????????????????????????????????? 8 畫 圖 模塊?????????????????????????????????????????? ..8 三．系統測試 ..................................................................................................................9 測 試 數據?????????????????????????????? 9 的 測 試 結果???????????????? .???????? 9 算 法 的 測 試 結果???????????????? .??? ..? .10 并 查 集 實 現 Kruskal 算 法 的 測 試 結果?????????????? .10 深 度 優 先 搜 索 實 現 Kruskal 算 法 的 測 試 結果????? ????? .11 廣 度 優 先 搜 索 實 現 Kruskal 算 法 的 測 試 結果?????????? .11 效 率 分析?????????????????????????????.12 四．總結 ...........................................................................................................................12 參 考 資料????????????? ??????????????????????????????? .13 一．系統需求分析與總體設計 需求分析 問題描述在一個具有幾個頂點的連通圖 G 中，如果存在子圖 G包含 G 中所有頂點和一部分邊，且不形成回路，則稱 G為圖 G 的生成樹，代價最小生成樹則稱為最小生成樹（ MinimalSpanningTree）。通過這些利用知識實現Kruskal 算法和 Prim 算法從而得到圖的最小生成樹。 Windows07，開發工具 VC++系統總體設計 由于這是對圖進行相關的操作，因此涉及圖的存儲問題，在這里使用的是鄰接矩陣這一數據結構來實現圖的存儲。 二．詳細設計與實現 模塊 Prime 算法的基本思想是以圖中的某一個頂點作為起始頂點，然后從起始頂點出發不斷的從還沒有遍歷到的頂點中選擇與已經遍歷到的頂點存在之間權值最小邊的頂點，并將新遍歷的點不斷的添加到已經遍歷的頂點集合中。此時 (vi,vj)一定均未加入 E(MST)。 （ 5）集合 V(MST)此時已經有五個頂點了，即 5，找到與之相連的符合條件的邊 (v4,v6)將權值為 4 的邊添加到 E(MST)中，并將頂點 6 添加到 V(MST)中并畫出此邊。 （ 3）循環 n1次 lowCost 中尋找具有最小權值的邊。具體如下： （ 1） 構造一個只有 n 個頂點沒有邊的非連通圖 T，圖中的每個頂點為一個連通分量。 （ 6）在圖 G 的邊的集合 E 中選擇權值最小的邊（ 1,2）并畫出此邊，其權重為 5。 （ 5）當最小生成樹生成完畢時，則調用 Draw（ E）函數畫出生成的過程。 （ 2）在圖 G的邊的集合 E中按存儲次序選擇權值最小的邊，即（ 2,3）由于邊（ 2,3）在（ 6,7）前面存儲，所以此處選擇的邊（ 2,3）其權重為 1。通過判斷畫出發生改變的集合 { 4}。此時集合變為 { 7}。這里定義一個 parent[n]的數組， parent[i]中存儲的就是結點i 所在的樹中的結點 i父親結點的序號，并查集的初始化中所有的 結點的 parent值均為 1，即每個結點就是根節點，只包含它本身這一個元素。 深度優先搜索實現 lKruskal算法動態演示模塊 基本思想深度優先搜索主要是在圖的遍歷中使用此方法對整個圖進行遍歷來訪問整個圖中所有節點的一種遍歷方法。同時通過深度優先搜索對這兩個結點分別進行判斷及標記已經訪問過了。同時通過深度優先搜索對這兩個結點分別進行判斷及標記已經訪問過了。這樣處理可以減少樹中深層次元素的個數，減少后續查找時間。 （ 1）對所畫區域進行刷新。通過判斷畫出發生改變的集合 { 7}。 （ 4）在圖 G 的邊的集合 E 中選擇權值最小的邊（ 2,4）并畫出此邊，其權重為 2。 下面通過題目的例子（如圖 1）對 kruskal 算法利用并查集實現過程中相應集合的變化進行了詳細的解析： （ 1）最初的集合有 7個，這 7個集合中均只有一個元素分別為 {1}、{2}、 {3}、 {4}、 {5}、 {6}、 {7}。 （ 3）判斷找到的邊的數目是否小于頂點的數目減一，即 n1，如果是則從沒有被選中的邊中選取權值最小的邊，如果放入存儲邊的集合中不構成回路則添加進去，否則舍去此邊。 （ 4）在圖 G 的邊的集合 E 中選擇權值最小的邊（ 4,5）并畫出此邊，其權重為 3。每次挑選邊成功了即畫出此邊。 （ 2） MST頂點初始值 ={序號為 0的頂點 }，其邊所在的結構體數組 E[n1]的值也為空。 （ 3）集合 V(MST)此時已經有三個頂點了，即 3，找到與之相連的符合條件的邊 (v2,v4)將權值為 2 的邊添加到 E(MST)中，并將頂點 4 添加到 V(MST)中并畫出此邊。然后，依次選出 n1 條符合以下條件的邊(vi,vj)。 對于算法運行時的動態顯示運行過程這一要求主要通過將相關的畫圓、畫線等相關畫圖的操作扦插到相關的算法中，在算法的運行過程中再通過對相關條件的判斷從而決定是否執行畫圓、畫線等操作。 對于運用圖形學的知識實現算法的動態運行效果。較高的要求是在邊通分量的查詢與合并的過程中，采用廣度優先搜索算法（ BreadthFirstSearch）、深度優先搜索算法 (DepthFirstSearch)和并查集（ UnionFindSet）這三種方法，并進行分析和比較算法時間復雜度。雖然最后做的和自己最初設想的有所差異，但是題目中的要求我都完成了，還是小有成就感的。 雖然通過例子實現了使用題目中要求的算法來求解最小生成樹，但是沒能實現給用戶一個友好的界面來方便求解各種不同的圖的最小生成樹，只能通過改變程序里面相關的存儲變量來實現對不同圖的最小生成樹的求解。因此廣度優先搜索遍歷圖的時間復雜度和深度優先搜索遍歷相同，兩者不同之處僅在于對頂點訪問的順序不同。通過此圖并結合上面對并查集的分析可知與其運行一致。 畫圖區域的刷新主要是為了實現同一塊區域可以畫多次不同的運行過程，有兩個函數承擔。 （ 2）查找與合并：在廣度優先搜索中首先判斷是否需要標記此節點，如果需要標記此節點則將此節點標記為以訪問過，并添加到已經訪問過的結點的集合中；如果是要進行判斷兩個結點是不是都已經訪問過了，及是否屬于同一個集合利用棧來不斷的搜索其中一個結點所在的集合中是否有另一個結點，如果存在則舍棄當前所選擇的邊，否則選擇此邊為最小生成樹的一邊。對于廣度優先搜索方法的實現這里使用的方法是通過利用隊列這一數據結構來實現的。 （ 2）對已經排好序的邊進行選擇，對沒有訪問過的最小權值的邊的兩個結點進行判斷，檢查是否已經被訪問過了，如果有一個沒有被訪問過，則將和此邊相應的頂點進行深度優先搜索的判斷之后進行標記，同時存儲所選擇的這個邊 和相應的頂點。 至此通過利用深度優先搜索進行邊通分量查詢的 kruskal 算法運行完畢，通過對比可知和使用普通的查 找算法得到的運行結果是一致的。同時通過深度優先搜索對著兩個 結點分別進行判斷是否需要標記，可知點 4 此時被標記訪問過了。其基本思想是：對于一個無向連通圖，從某一個起始結點 vi 出發，訪問與它相連的一個結點 vj，且 vi、 vj這兩個結點之間的邊（ vi、 vj）是所有以 vi 為連接結點的邊中權值最小的；然后再從 vj 出發尋找與 vj 相連的頂點，且它們之間的邊是所有以 vi 為連接結點的邊中權值最小的，不斷的重復直到找到訪問完所有的結點為止。在此函數中如果只靠一個循環來得到結果，則對于合并中得到的層次比較深的集合，查找會很費時。 至此 kruskal 算法利用并查集查找、合并的過程結束，通過kruskal算法得到最小生成樹及生成過程，其最小生成樹的權值為 16。此時集合變為 {1}、 { 5}、 { 7}。通過判斷畫出發生改變的集合 { 3}。最初把每一個對象看做是一個單元集合，然后依次按順序讀入一個等價對后，將等價對中的兩個元素所在的集合合并。 模塊設計與實現 Kruskal 算法的實現主要包含兩個部分，即帶權 值的邊的排序和判斷選取的邊的兩個頂點是否屬于同一個連通分量。 （ 3）如此反 復下去，直到所有頂點在同一個連通分量上為止。 存第 k 個頂點的數據和相應邊的權值到 MST 中，并將lowCost[k]置為 1，表示第 k 個頂點從集合 V(G)－ V(MST)加入了集合V(MST)中 當第 k 個頂點加入到集合 V(MST)后，若存 在一條邊 (k,j)，其中 k 是集合 V(MST)的頂點， j是集合 V(G)－ V(MST)的頂點，且邊 (k,j)權值較原先 lowCost[j]的代價更小，則用這個權值修正原先 lowCost[j]中的權值。 至此圖 G中所有的點均已添加到了 V(MST)，最小生成樹生成完畢，其權值為 16。 （ 2） (vi,vj)是關聯于 V(MST)中頂點的邊中權值最小的邊。 對于無向連通圖 G（ V,E），在 prime 算法中，將圖 G 頂點集合分為兩個集合 V1（ G）和 V2（ G）， V1（ G）用來存儲當前已經遍歷到的頂點，即最小生成樹中的頂點 V(MST)， V2（ G） 用來存儲還沒有遍歷到的頂點。 在深度優先搜索算法（ BreadthFirstSearch）中使用了棧這一數據結構來實現邊的連通分量的查詢，對廣度優先搜索算法(DepthFirstSearch)的實現使用了隊列這一數據結構，這里的隊列和棧都是通過編程實現。 為了更好、更生動的表示這些算法的運算過程，在這里如果使用動態顯示算法的求解過程將會是最好的選擇。例如：要在 n 個城市之間鋪設光纜，主要目標是要使這 n 個城市的任意兩個之間都可以通信，但鋪設光纜的費用很高，且各個城市之間鋪設光纜的費用不同；另一個目標是要使鋪設光纜的總費用最低。并對兩種算法進行分析和比較。在這里我選擇了將這三種搜索算法融合到 Kruskal算法，因為我覺得在 Kruskal算法對邊通分量進行查詢和合并中使用這三種方法 更合理且更容易實現，因此也實現了將這三種搜索算法融合到 Kruskal 算法從而實現對圖的最小生成樹的查找。