軟件綜合實習報告合集-免費閱讀

　　

【正文】 （ 2）繼續向下查找得到邊（ 6,7），判斷點 6 和點 7 是否已經訪問過了，由于數組 check 中相應的值為 0，因此合并這兩個結點，得到新的集合 { 7}。在每一次的合并過程結束時，將會畫出合并之后的集合。 （ 2）初始化過程：為了方便并查集的描述與實現，通常把先后加入到一個集合中的元素表示成一個樹形結構，并用根節點來代表這個集合。 （ 7）在圖 G 的邊的集合 E 中選擇權值最小的邊（ 1,2）并畫出此邊，其權重為 5。此時集合變為 {1}、 { 4}、 {5}、 { 7}。畫出初始狀態。 （ 4）如果不符合（ 2）中的判斷則不斷的重復直到選取的邊等于n1。 （ 5）在圖 G 的邊的集合 E 中選擇權值最小的邊（ 4,6）并畫出此邊，其權重為 4。在 n 個頂點的圖中，選夠 n1條邊即可。 lowCost 的初始值為鄰接矩陣中第 0 行的值，這樣初始時lowCost 中就存放了從集合 V(MST)中頂點 0 到集合 V(G)－ V(MST)中各個頂點的權值。 （ 4）集合 V(MST)此時已經有四個頂點了，即 4，找到與之相連的符合條件的邊 (v4,v5)將權值為 3的邊添加到 E(MST)中 ，并將頂點 5 添加到 V(MST)中并畫出此邊。 （ 1） (vi,vj) E(G)， v是 V(MST)的頂點，而 vj是還未加入 V(MST)的頂點。在這些算法運行過程中實現的畫圖操作主要通過調用一個公用的函數進行畫圖的相關操作。可以知道使用MFC 通過單文檔畫圖來實現算法動態顯示運行效果或者使用對話框來實現算 法動態顯示運行效果，為了方便起見，我選擇的是通過 MFC 建立單文檔來實現這一效果。 測試數據如下： 圖（ 1） 問題分析通過問題的描述，可知這一道題目主要涉及，面向對象的分析與設計，數據結構和算法。所以通過 這次的實習，讓我認識到只要去嘗試，去努力沒有什么是不可以做的。同時由于對于作圖這方面不是很熟練，沒能實現對圖的動態擴充，所以只能是實現對一定數目，一定邊數的圖的求解。對于使用 kruskal 算法和深度優先搜索結合的算法，對邊的遍歷至多是 e 次，故其總代價為 O(n^2*e)。 深度優先搜索實現 Kruskal算法的測試結果 圖（ 6） 在這里沒有對深度優先搜索的過程給予動態顯示，主要是模擬了深度優先搜索實現 kruskal算法的過程，也即最小生成樹的生成過程。由于并查集的繪制和最小生成樹的繪制沒有太大的關聯，因此在這里采用了單獨繪制并查集實現 kruskal 算法中并查集的合并過程。 下面給出 kruakal 算法利用廣度優先搜索進行邊連通分量查詢和合并從而得 到最小生成樹的的設計與實現步驟： （ 1）對所畫區域進行刷新。 這里采用的廣度優先搜索主要是用來檢索邊的鄰接頂點是不是在同一個集合中，由于使 用 kruskal 算法時最初已經對邊進行了一個排序，所以每一次所選用的邊和通過廣度優先搜索對鄰接頂點進行判斷的結果是一樣的，在這里不再給予詳細的說明， kruskal 算法結合廣度優先搜索具體的運算過程和 kruskal 算法結合深度優先搜索的運算過程是一樣的，在這里不再列出。 （ 3）如果都已經被訪問過了，則利用深度優先搜索判斷這兩個節點是否屬于同一個集合，如果是的話則拋棄此邊，如果不是的話則對其進行標記，并畫出此邊和相對應的點。 設計與實現在這里采用 Kruskal 算法得到最小生成樹的過程中，在對邊連通分量的查詢時使用了深度優先搜索的方法來查詢當前得到的具有最下權值的邊的兩個頂點是不是已經存在于被訪問過的結點的集合中，如果是的則進行下一次查詢，否則的話則將沒有訪問過的結點加入已經訪問過的結點的集合中。 （ 4）繼續向下查找得到邊（ 4,5），判斷點 4 和點 5 是否已經訪問過了得知點 4 已經被訪問過了，點 5沒有，因此得到新的集合 {2,、 5}。 在這個算法的實現過程中，邊通分量的查找雖然是深度優先搜索為主，但是是以最小生成樹的的生成過 程為主，因此這里所采用的畫圖操做運行的情況和使用一般的方法實現 kruskal 算法的運行過程是一樣的，在這里不再給予詳細的說明，如有必要則可以參照 kruskal的生成最小生成樹的過程。這里通過壓縮路 徑的方法來加快后續的查找速度，主要是通過增加一個 while 循環，每次都把從結點 i 到集合根節點的路徑上經過的結點直接設置為根結點的子結點。 設計與實現 Kruskal 算法利用并查集實現查找、合并的設計與實現也是首先選擇權值最小的邊，其次是利用并查集來對所要選擇的那些頂點進行查找、合并。通過判斷畫出發生改變的集合 { 5}。 （ 3）在圖 G的邊的集合 E中按存儲次序選擇權值最小的邊，即（ 6,7）由于邊（ 6,7）在（ 2,3）后面存儲，所以后選擇邊（ 6,7），其權重為 1。在此過程中不斷的重復使用一個搜索運算，從而確定此元素在哪一個集合中，當讀入一個等價對 A≡ B 時，首先檢測 A 和 B是不是屬于同一個集合，如果是，則不用合并；如果不是，則使用一個合并運算把 A 和 B 合并到同一個集合中，使得這兩個集合中的任意兩個元素都是等價的（依據等價的傳遞性）。因此首先將圖 G 的頂點集合 V 分為 n 個等價類，每個等價類包括一個頂點；然后以權值的大小為順序處理各條邊，如果某條邊連接兩個不同等價類的頂點，則這條邊被添加到 MST（選取的邊不與前面選取的邊構成回路），兩個等價類被合并為一個；反復執行此過程，直到只剩下一個等價類。 下面主要通過題目中給出的例子（如圖 1）對 kruskal 算法進行詳細的解析： （ 1）在圖 G的邊的集合 E中按存儲次序選擇權值最小的邊，即（ 2,3）由于邊（ 2,3）在（ 6,7）前面存儲，所以此處選擇的邊（ 2,3）并畫出此邊，其權重為 1。 當最小生成樹生成完畢時，則調用 Draw（ E）函數畫出生成的過程。 設計與實現對于 prime 算法的動態演示，主要是關乎兩個函數的實現一個是畫圖函數的實現，另外一個就是如何判斷何時進行畫圖操作并進行 相關操作的畫圖函數，在這里主要通過兩個函數實現一個是與 Kruskal 算法動態實現的公用的畫圖操作函數，另外一個就是 prime 算法尋找最小生成樹的實現。選出滿足該條件的邊，將 vj 加入 V(MST)， (vi,vj)加入 E(MST)，之后畫出相應的邊和新添加進去的頂點。對于已經選擇的頂點之間的邊存儲在最小生成樹的邊的集合中 E(MST)。 這里主要分為六個模塊，即 prime 算法模塊、 kruskal 算法模塊、用并查集實現 kruskal算法的模塊、 kruskal算法和深度優先搜索算法結合的模塊、 kruskal 算法和廣度優先搜索算法結合的模塊以及畫圖操作的相關模塊。對于不同的算法其求解最小生成樹時運算的效率是不同的，因此還需要對各種算法時間復雜度進行分析和比較， 從而更加深入的理解算法，從而方便我們在不同的場合采用不同的實現算法。這就需要找到帶權的最小生成樹。 基本的要求是實現兩種算 法：通過實現 Kruskal 算法和 Prim 算法來得到圖的最小生成樹。 方案選擇通過對題目的分析，對于如何將廣度優先搜索算法（ BreadthFirstSearch）、深度優先搜 1325465652447 3171 索算法 (DepthFirstSearch)和并查集（ UnionFindSet）這三種方法運用到對邊通分量進行查詢和合并中有不同的結合方法。設計與實現中由于所體現的重點不同，因此下面的說明主要圍繞著此題的重點，即最小生成樹的生成過程。 Prime算法的具體過程如下： 設最小生成樹中點的集合 V(MST)和邊的集合 E(MST)的初態均為空。 下面主要通過題目中給出的例子（如圖 1）對 prime 算法進行詳細的解析： （ 1）將 1 作為起始頂點添加到 V(MST)，找到與之相連的符合條件的邊 (v1,v2)，將權值為 5 的邊添加到 E(MST)中，并將頂點 2 添加到V(MST)中并畫出此邊。這里僅給出語言描述的實現過程，源代碼的實現在后面的附錄中將會給出。 Kruskal 算法通常是在已知 V(MST)=V(G)， E(MST)的初態為空時對圖 G 進行相關處理的到最小生成樹的。 （ 2）在圖 G的邊的集合 E中按存儲次序選擇權值最小的邊，即（ 6,7）由于邊（ 6,7）在（ 2,3）后面存儲，所以后選擇邊（ 6,7）并畫出此邊，其權重為 1。 kruskal 算法的設計與實現如下所述（具體的代碼實現見附錄）： （ 1）對所畫區域進行刷新。 在此處實現 Kruskal 算法時主 要使用并查集對相關頂點進行搜索和合并，從而實現了使用并查集實現 Kruskal 算法。此時集合變為 {1}、 { 3}、 {4}、 {5}、 { 7}。 （ 6）在圖 G 的邊的集合 E 中選擇權值最小的邊（ 4,6）并畫出此邊，其權重為 4。在 Kruskal 使用并查集時首先對其進行邊 集合的排序，接著利用并查集對圖 G 中的頂點進行初始化，每一個頂點當做一個集合，同時給其一個相關的變量標志其集合中頂點的數目；然后利用并查集判斷此時的頂點所在集合是不是相同，如果不相同則合并這兩個頂點所在的集合。 （ 4）合并：兩個集合合并時，任何一方均可作為另一方的子孫。對于深度優先搜索方法的實現這里使用的方法是通過利用棧這一數據結構來實現的。同時通過深度優先搜索對著兩個結點分別進行判斷是否需要標記，可知點 5 此時被標記訪問過了。 深度優先搜索的實現主要利用棧這一數據結構來實現。 （ 4）選擇下一條沒有被訪問過的邊重新進行（ 1）、（ 2）的判斷，直到所有的頂點均已被訪問過且在同一個集合中，即已經添加到了最小生成樹中則最小生成樹生成完畢。由于本題的重點是最小生成樹的生成，在這里不再給出廣度優先搜索具體的搜索過程。 （ 2）對已經排好序的邊進行選擇，對沒有訪問過的最小權值的邊的兩個結點進行判斷，檢查是否已經被訪問過了，如果有一個沒有被訪問過，則將和此邊相應的頂點進行廣度優先搜索的判斷之后進行標記，同時畫出所選擇的這個邊和相應的頂點。 三．系統測試 圖（ 2） 上圖是利用程序直接得到的原圖形，此測試數據中有七個頂點，有十條邊。通過對比前兩種 kruskal算法的實現過程可知其運行是一致的。 效率分析 Prime 算法實現的函數主要是一個兩重循環，其中每一重循環的次數均為頂點個數 n，所以該算法的時間復雜度為 O(n^2)。為了我的程序更加完美我會繼續努力，從而實現圖的動態擴充，同時讓程序更為簡練。 參考文獻： [1]朱戰立，數據結構 — 使用 c 語言（第四版），電子工業出版社2021年 11 月 [2]王桂平、王衍、任嘉辰，圖論算法理論、實現及應用，北京大學出版社， 2021 年 1月 [3]孫鑫、余安萍， VC++深入詳解，電子工業出版社 2021年 5月 第二篇：軟件綜合實習報告 軟件綜合實習報告 題目：最小生成樹算法 院（系）： 計算機學院 專 業： 計算機科學與技術 姓 名： 班級學號： 2021年 9月 12 日 目錄一．系統需求分析與總體設計 ............................................................................1 需 求 分析?????????????????????????????????????????? 1 問 題 描述???????????????????????????????????????? 1 問題 分析???????????????????????????????????????? 1 方 案 選擇???????????????????????????????????????? 1 開 發 平臺???????????????????????????????????????? 2 系 統 總 體 設計?????????????????????????????????????? .2 二．詳細設計與系統實現 .......................................................................................2 算 法 動 態 演 示模?? .?????? .????????