資料結構課程設計
設計說明書
數學與電腦科學學院
2023年3月15日
課程設計任務書
2012—2013學年第二學期
設計內容：
圖論中，對於個帶權的連通圖，其每個生成樹所有邊上的權值之和可能不同，把其所有邊上權值之和最小的生成樹稱為圖的最小生成樹。通訊線路鋪設造價最優問題就是最小生成樹的實際應用
普里姆演算法的的基本思想：從連通網n=中的某一頂點u0出發，選擇與它關聯的具有最小權值的邊(u0,v)，將其頂點加入到生成樹的頂點集合u中。以後每一步從乙個頂點在u中，而另乙個頂點不在u中的各條邊中選擇權值最小的邊(u,v),把它的頂點加入到集合u中。
如此繼續下去，直到網中的所有頂點都加入到生成樹頂點集合u中為止。
本課程設計中主要完成以下內容
1.任意給出乙個帶權值的連通網路圖，能夠遍歷圖中的所有節點
2. 根據普里姆演算法思想，程式設計實現此連通圖的最小生成樹的輸出
3.計算討論演算法的時間複雜度及空間複雜度
基本要求如下
1.程式設計介面友好；2.設計思想闡述清晰；3.演算法流程圖正確；4.軟體測試方案合理、有效
指導教師教研室負責人
課程設計評閱
摘要 最短路徑的問題在現實生活中應用非常廣泛，如郵遞員送信、公路造價等問題。本設計以vc++作為開發平台，c語言作為程式語言，以鄰接矩陣作為儲存結構，程式設計實現了最短路徑演算法。該程式操作簡單，具有一定的應用性。
關鍵詞：最短路徑；普里姆演算法；最小生成樹；vc++
目錄1 課題描述 1
2 演算法描述 2
2.1 演算法思想 2
2.2 普里姆演算法分析 4
3 流程圖 5
4 源** 1
5 程式測試 5
參考文獻 9
日常生活中，人們都希望花最少的時間或者最少的金錢將一件事情辦成，例如：乙個郵遞員想走最短的路把手中的物件送到收件人手中，通訊公司想花費最少的金錢把通訊網路覆蓋在n個城市之間，這些都可歸納為求最短路徑問題。
本課題利用普里姆演算法來實現譬如通訊網路中各種連線方式中的最短路徑問題，從而達到一條最優線路，以使金錢或時間的花費最小，達到解決成本的目的。
開發工具：visual c++ 6.0
本設計是基於最小生成樹普里姆演算法的思想上，以實現在網路中可以選擇出最**路，從而達到省時省力的效果。
普利姆演算法求最小生成樹的主要思想
此演算法是普利姆與2023年提出的一種構造最小生成樹的演算法，主要思想是：假設n=（v，）是連通網，te是n上最小生成樹中邊的集合。演算法從u=( u0∈v),te={}開始，重複執行下述操作：
在所有u∈u,v∈v-u的邊（u,v）∈e中找一條代價最小的邊（u0,v0）併入集合te，同時v0併入u，直至u=v為止。此時te中必有n-1條邊，則t=（v，）為n的最小生成樹。
最小生成樹是指在所有生成樹中，邊上權值之和最小的生成樹，另外最小生成樹也可能是多個，他們之間的權值之和相等。
6511 5
5 3246
6ab)11
1424cd
115 5
23244
ef)2.1普里姆演算法構造最小生成樹的過程
在其演算法中，首先，初始化乙個圖給引數g,然後定義closedge用於存放最小生成樹中的頂點，呼叫函式locate()求出起點u在頂點向量表中的位置，初始化u=，利用for迴圈對v-u中的頂點i,初始化，再利用for迴圈找n-1條邊，其中，呼叫函式minium()求出輔助陣列中權值最小的邊, 並將其在輔助陣列中的相應位置返回到主調函式中，最後，輸出起點、終點和權值。
void minispantree_prim(mgraph g,vertex u)
最小生成樹實驗報告
最小生成樹演算法的設計與實現 一 實驗目的 1 根據演算法設計需要,掌握連通網的靈活表示方法 2 掌握最小生成樹演算法，如prim kruskal演算法 3 基本掌握貪心演算法的一般設計方法 4 進一步掌握集合的表示與操作演算法的應用.二 預習與參考 1 認真閱讀演算法設計教材和資料結構教材內容,熟...
演算法設計與分析 貪心法求最小生成樹
一 問題描述 1.可以用連通網來表示n個城市間可能設定的通訊網路，其中網的頂點表示城市，邊表示兩城市之間的路線，邊的權值表示相應的費用。對於n個頂點的連通網可以建立許多不同的生成樹，每一棵生成樹都可以是乙個通訊網。現在，我們要選擇這樣一棵生成樹，它使總的費用最少，這棵樹就是最小生成樹。一棵生成樹的費...
資料結構課程設計報告 最小生成樹完整版
課程設計報告 課程名稱 設計題目 學生班級 學生姓名 指導教師 完成日期 資料結構最小生成樹的應用 09 計科 2 班蔣家權，陳相財，吳繼偉，梁麗春林麗惠 2011 1 19 計算機系課程設計報告 課程設計專案研究報告 目錄一 問題分析和任務定義1 二 實現本程式需要解決的問題如下1 三 測試資料2...