軟件綜合實習報告合集(完整版)

　　

【正文】 邊通分量的查詢與合并的過程中，采用廣度優先搜索算法（ BreadthFirstSearch）、深度優先搜索算法 (DepthFirstSearch)和并查集（ UnionFindSet）這三種方法，并進行分析和比較算法時間復雜度。 對于運用圖形學的知識實現算法的動態運行效果。 對于算法運行時的動態顯示運行過程這一要求主要通過將相關的畫圓、畫線等相關畫圖 的操作扦插到相關的算法中，在算法的運行過程中再通過對相關條件的判斷從而決定是否執行畫圓、畫線等操作。然后，依次選出 n1 條符合以下條件的邊(vi,vj)。 （ 3）集合 V(MST)此時已經有三個頂點了，即 3，找到與之相連的符合條件的邊 (v2,v4)將權值為 2 的邊添加到 E(MST)中，并將頂點 4 添加到 V(MST)中并畫出此邊。 （ 2） MST頂點初始值 ={序號為 0的頂點 }，其邊所在的結構體數組 E[n1]的值也為空。每次挑選邊成功了即畫出此邊。 （ 4）在圖 G 的邊的集合 E 中選擇權值最小的邊（ 4,5）并畫出此邊，其權重為 3。 （ 3）判斷找到的邊的數目是否小于頂點的數目減一，即 n1，如果是則從沒有被選中的邊中選取權值最小的邊，如果放入存儲邊的集合中不構成回路則添加進去，否則舍去此邊。 下面通過題目的例子（如圖 1）對 kruskal 算法利用并查集實現過程中相應集合的變化進行了詳細的解析： （ 1）最初的集合有 7個，這 7個集合中均只有一個元素分別為 {1}、{2}、 {3}、 {4}、 {5}、 {6}、 {7}。 （ 4）在圖 G 的邊的集合 E 中選擇權值最小的邊（ 2,4）并 畫出此邊，其權重為 2。通過判斷畫出發生改變的集合 { 7}。 （ 1）對所畫區域進行刷新。這樣處理可以減少樹中深層次元素的個數，減少后續查找時間。同時通過深度優先搜索對這兩個結點分別進行判斷及標記已經訪問過了。同時通過深度優先搜索對著兩個結點分別進行判斷是否需要標記則知均不 需要。由于對棧已經 比較熟悉，在這里僅作簡要的說明。 廣度優先搜索實現 lKruskal算法動態演示模塊 基本思 想廣度優先搜索主要是在圖的遍歷中使用此方法對整個圖進行遍歷來訪問整個圖中所有節點的一種遍歷方法。 廣度優先搜索的實現主要利用隊列這一數據結構來實現。 （ 4）選擇下一條沒有被訪問過的邊重新進行（ 1）、（ 2）的判斷，直到所有的頂點均已被訪問過且在同一個集合中，即已經添加到了最小生成樹中則最小生成樹生成完畢。通過觀察可知這六條邊應為（ 2,3）、（ 6,7）、（ 2,4）、（ 4,5）、（ 4,6）、（ 1,2）。由此也說明一個問題，即對于使用不同的方法來實現這一算法，改變的只是其效率，但是整體的運行情況是不會發生改變的。 Kruskal 運用并查集實現中使用了路徑壓縮， Find 和 UNION 函數幾乎是常數假設可能對幾乎所有邊都判斷過了，則最壞情況下算法時間代價為 O(eloge)，即堆排序的時間通常情況下只找了接近頂點數目那么多邊的情況下， MST就已經生成，時間代價接近于 O(nloge) 深度優先搜索對每一條邊處理一次，每個頂點訪問一次以鄰接矩陣作存儲結構：處理所有的邊需 O(nn^2)的時間，故總代價為 O(n^2)。在實現在邊通分量的查詢與合并的過 程中，采用廣度優先搜索算法（ Breadth FirstSearch）、深度優先搜索算法 (DepthFirstSearch)和并查集（ UnionFindSet）三種方法來實現對此例中圖的最小生成樹的求解，這一方面最初也是相當的糾結，不知道該從什么方面下手。例如：要在 n 個城市之間鋪設光纜，主要目標是要使這 n 個城市的任意兩個之間都可以通信，但鋪設光纜的費用很高，且各個城市之 間鋪設光纜的費用不同；另一個目標是要使鋪設光纜的總費用最低。 為了更好、更生動的表示這些算法的運算過程，在這里如果使用動態顯示算法的求 解過程將會是最好的選擇。 在深度優先搜索算法（ BreadthFirstSearch）中使用 了棧這一數據結構來實現邊的連通分量的查詢，對廣度優先搜索算法(DepthFirstSearch)的實現使用了隊列這一數據結構，這里的隊列和棧都是通過編程實現。 對于無向連通圖 G（ V,E），在 prime 算法中，將圖 G 頂點集合分為兩個集合 V1（ G）和 V2（ G）， V1（ G）用來存儲當前已經遍歷到的頂點，即最小生成樹中的頂點 V(MST)， V2（ G） 用來存儲還沒有遍歷到的頂點。 （ 2） (vi,vj)是關聯于 V(MST)中頂點的邊中權值最小的邊。 至此圖 G中所有的點均已添加到了 V(MST)，最小生成樹生成完畢，其 權值為 16。 存 第 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]中的權值。 （ 3）如此反復下去，直到所有頂點在同一個連通分量上為止。 模塊設計與實現 Kruskal 算法的實現主要包含兩個部分，即帶權值的邊的排序和判斷選取的邊的兩個頂點是否屬于同一個連通分量。最初把每一個對象看做是一個單元集合，然后依次按順序讀入一個等價對后，將等價對中的兩個元素所在的集合合并。通過判斷畫出發生改變的集合 { 3}。此時集合變為 {1}、 { 5}、 { 7}。 至此 kruskal 算法利用并查集查找、合并的過程結束，通過kruskal算法得到最小生成樹及生成過程，其最小生成樹的權值為 16。在此函數中如果只靠一個循環來得到結果，則對于合并中得到的層次比 較深的集合，查找會很費時。其基本思想是：對于一個無向連通圖，從某一個起始結點 vi 出發，訪問與它相連的一個結點 vj，且 vi、 vj這兩個結點之間的邊（ vi、 vj）是所有以 vi 為連接結點的邊中權值最小的；然后再從 vj 出發尋找與 vj 相連的頂點，且它們之間的邊是所有以 vi 為連接結點的邊中權值最小的，不斷的重復直到找到訪問完所有的結點為止。同時通過。對于深度優先搜索方法的實現這里使用的方法是通過利用棧這一數據結構來實現的。 （ 4）合并：兩個集合合并時，任何一方均可作為另一方的子孫。在 Kruskal 使用并查集時首先對其進行邊集合的排序，接著利用并查集對圖 G 中的頂點進行初始化，每一個頂點當做一個集合，同時給其一個相關的變量標志其集合中頂點的數目；然后利用并查集判斷此時的頂點所在集合是不是相同，如果不相同則合并這兩個頂點所在的集合。 （ 6）在圖 G 的邊的集合 E 中選擇權值最小的邊（ 4,6）并畫出此邊，其權重為 4。此時集合變為 {1}、 { 3}、 {4}、 {5}、 { 7}。 在此處實現 Kruskal 算法時主要使用并查集對相關頂點進行搜索和合并，從而實現了使用并查集實現 Kruskal 算法。 kruskal 算法的設計與實現如下所述（具 體的代碼實現見附錄）： （ 1）對所畫區域進行刷新。 （ 2）在圖 G的邊的集合 E中按存儲次序選擇權值最小的邊，即（ 6,7）由于邊（ 6,7）在（ 2,3）后面存儲，所以后選擇邊（ 6,7）并畫出此邊，其權重為 1。 動態演示模塊 Kruskal 算法通常是在已知 V(MST)=V(G)， E(MST)的初態為空時對圖 G 進行相關處理的到最小生成樹的。這里僅給出語言描述的實現過程，源代碼的實現在后面的附錄中將會給出。 下面主要通過題目中給出的例子（如圖 1）對 prime 算法進行詳細的解析： （ 1）將 1 作為起始頂點添加到 V(MST)，找到與之相連的符合條件的邊 (v1,v2)，將權值為 5 的邊添加到 E(MST)中，并將頂點 2 添加到V(MST)中并畫出此邊。 Prime算法的具體過程如下： 設最小生成樹中點的集合 V(MST)和邊的集合 E(MST)的初態均為空。設計與實現中由于所體現的重點不同，因此下面的說明主要圍繞著此題的重點，即最小生成樹的生成過程。 方案選擇通過對題目的分析，對于如何將廣度優先搜索算法（ BreadthFirstSearch）、深度優先搜 1325465652447 3171 索算法 (DepthFirstSearch)和并查集（ UnionFindSet）這三種方法運用到對邊通分量進行查詢和合并中有不同的結合方法。 基本的要求是實現兩種算法：通過實現 Kruskal 算法和 Prim 算法來得到圖的最小生成樹。 這讓我意識到學習到的知識一定要活用才能創造出更好的方法，只是使用它通常的用途是遠遠不夠的。 四．總結這個題目的主要要求是通過使用不同的算法求出圖的最小生成樹，并且通過畫圖動態的顯示出來其不同的算法在求解最小生成樹時的運行步驟。 對于廣度優先搜索每個頂點至多進一次隊列。 圖 (4) 通過上面 kruskal 算法的解析結果和運行結果發 現其運行結果與分析中應該得到的結果是一致的，由于畫圖和判斷中采用的有延長運行時間的函數，因此這里只通過理論分析得出 kruskal 算法的運行效率。 畫圖模塊 這一模塊主要是實現如何動態的演示程序運行的效果，主要涉及的有三個方面，第一個方面是使用不同的算法實現最小生成樹的繪制過程，第二個方面是畫圖區域的刷新，第三個方面是并查集的繪制過程。由于對隊列已經比較熟悉，在這里僅作簡要的說明。其基本思想是：對于一個無向連通圖，從某一個起始結點 vi 出發，依次訪問與它相連的所有未訪問過的結點 vj vj2?? vjn，然后在順序訪問 vj vj2?? vjn的所有還未訪問過的鄰接頂點；再從這些鄰接頂點出發，再訪問它們的所有未訪問過的鄰接頂點，??，不斷重復直到圖 G 中所有的頂點都被訪問過為止。 （ 2）查找與合并：在深度優先搜索中首先判斷是否需要標記此節點，如果需要標記此節點則將此節點標記為以訪問過，并添加到已經訪問過的結點的集合中，并將相應的邊存入 E[]中；如果是要進行判斷兩個結點是不是都已經訪問 過了，及是否屬于同一個集合利用棧來不斷的搜索其中一個結點所在的集合中是否有另一個結點，如果存在則舍棄當前所選擇的邊，否則選擇此邊為最小生成樹的一邊。 （ 7）繼續向下查找得到邊（ 1,2），判斷點 1 和點 2 是否已經訪問過了得知點 2 已經被 訪問過了，點 1 沒有，因此得到新的集合 { 2,、 7}。同時通過深度優先搜索對這兩個結點分別進行判斷及標記已經訪問過了。 深度優先搜索實現 lKruskal算法動態演示模塊 基本思想深度優先搜索主要是在圖 的遍歷中使用此方法對整個圖進行遍歷來訪問整個圖中所有節點的一種遍歷方法。這里定義一個 parent[n]的數組， parent[i]中存儲的就是結點i 所在的樹中的結點 i父親結點的序號，并查集的初始化中所有的 結點的 parent值均為 1，即每個結點就是根節點，只包含它本身這一個元素。此時集合變為 { 7}。通過判斷畫出發生改變的集合 { 4}。 （ 2）在圖 G的邊的集合 E中按存儲次序選擇權值 最小的邊，即（ 2,3）由于邊（ 2,3）在（ 6,7）前面存儲，所以此處選擇的邊（ 2,3）其權重為 1。 （ 5）當最小生成樹生成完畢時，則調用 Draw（ E）函數畫出生成的過程。 （ 6）在圖 G 的邊的集合 E 中選擇權值最小的邊（ 1,2）并畫出此邊，其權重為 5。具體如下： （ 1） 構造一個只有 n 個頂點沒有邊的非連通圖 T，圖中的每個頂點為一個連通分量。 （ 3）循環 n1次 lowCost 中尋找具有最小權值的邊。 （ 5）集合 V(MST)此時已經有五個頂點了，即 5，找到與之相連的符合條件的邊 (v4,v6)將權值為 4 的邊添加到 E(MST)中，并將頂點 6 添加到 V(MST)中并畫出此邊。此時 (vi,vj)一定均未加入 E(MST)。 二．詳細設計與實現 Prime 算法的基本思想是以圖中的某一個頂點作為起始頂點，然后從起始頂點出發不斷的從還沒有遍歷到的頂點中選擇與已經遍歷到的頂點存在之間權值最小邊的頂點，并將新遍歷的點不斷的添加到已經遍歷的頂點集合中。 Windows07，開