《資料結構》課程討論課報告 --最小生成樹的求解方法與分析
學院：資訊科學與工程學院
班級：電腦科學與技術一班
指導老師：
學生姓名：
起止時間：2023年秋季學期第17周-第18周
一、 小組成員
組長：ppt製作：
講解：提問：
報告撰寫：
二、 組內貢獻度
： 23%
： 26%
： 26%
： 25%
三、 實驗目的
1、以資料結構中圖理論的典型應用---最小生成樹為討論物件，系統認識和歸納總結各種求最小生成樹的方法、分析不同方法的演算法複雜性和與實際系統的求解效率的關係。
2、以講演和討論為主要形式，以理論講述、方法解析、演算法設計(如相關概念與知識、不同演算法的理解與分析)為主要討論內容，積極思考，主動學習，訓練分析問題、總結能力，提高運用專業知識解決實際問題的能力。並在溝通能力、團隊合作精神和能力等方面得到提高。
四、實驗內容
通過利用課外時間閱讀教材相關內容和查閱其它有關求最小生成樹的資料，進行分析、歸納、總結及提煉。深入研討最小生成樹系統所涉及的知識點及應用。
總結出一種或一種以上求最小生成樹的演算法，並通過製作、講解ppt，回答他組的提問、撰寫報告來展示小組討論成果。
五、實驗原理
邊賦以權值的圖稱為網或權圖，權圖的生成樹也是帶權的，生成樹t各邊的權值總和稱為該樹的權最小生成樹（mst）即權值最小的生成樹。
1. prim演算法
假設n=(v，e)是連通網，te是n上最小生成樹中邊集合。
演算法從u=(u0∈v)，te={}開始，重複執行下述操作：在所有u∈u，v∈v-u的邊(u，v)中找一條代價最小的邊(u0 ,v0),將其併入集合te，同時將v0併入u集合。
當u=v則結束，此時te中必有n-1條邊，則t=(v，)為n的最小生成樹。
普里姆演算法構造最小生成樹的過程是從乙個頂點u=作初態，不斷尋找與u中頂點相鄰且代價最小的邊的另乙個頂點，擴充到u集合直至u=v為止。、
假設連通網n=(v，e)，則令最小生成樹的初始狀態為只有n個頂點而無邊的非連通圖t=(v，{})，圖中每個頂點自成乙個連通分量。
在e中選擇代價最小的邊，若該邊依附的頂點落在t中不同的連通分量上，則將此邊加入到t中，否則捨去此邊而選擇下一條代價最小的邊。依次類推，直至t中所有頂點都在同一連通分量上為止。
2. kruscal演算法
假設連通網n=（v，），則令最小生成樹的初始狀態為只有n個頂點而無邊的非連通圖t=（v，{}），圖中每個頂點自成乙個連通分量。在e中選擇代價最小的邊，若該邊依附的頂點落在t中不同的連通分量上，則將此邊加入到t中，否則捨去此邊而選擇下一條代價最小的邊。依此類推，直至t中所有的頂點都在同一連通分量上為止。
六、案例分析
1、運用prim演算法，求最小生成樹的過程如下：
步驟序號uu-v
0v1v2，v3，v4，v5，v6}
1v1，v3v2，v4，v5，v6}
2v1，v3，v6v2，v4，v5，}
3v1，v3，v6 ,v4v2，v5
4v1，v3，v6 ,v4 ,v2v5
5v1，v3，v6 ,v4 ,v2, v5
得到最小生成樹如下
2、運用kruskal演算法求最小生成樹的過程如下：
1. 選擇其中權最小的邊，滿足條件
2. 選擇剩下的邊中權最小的邊 ，滿足條件
3. 選擇剩下的邊中權最小的邊 ，滿足條件
4. 選擇剩下的邊中權最小的邊 ，滿足條件
5. 選擇剩下的邊中權最小的邊 ，但是v1，v4 在同乙個連通分量上，捨去，選擇，滿足條件
6， 此時所有頂點都在同乙個連通分量上，演算法結束。
得到的最小生成樹如下：
七、總結
prim演算法構造最小生成樹的方法：最初生成樹為空，即沒有乙個結點和一條邊，首先選擇乙個頂點作為生成樹的根，然後每次從不在生成樹中的邊中選擇一條權值盡可能小的邊，為了保證加入到生成樹中的邊不會造成迴路，與該邊鄰接的兩個頂點必須乙個已經在生成樹中，乙個則不在生成樹中，若網中有n個頂點（這裡考慮的網是乙個連通無向圖），則按這種條件選擇n-1邊就可以得到這個網的最小生成樹了。
詳細的過程可以描述為：設定2個集合，u集合中的元素是在生成中的結點，v-u集合中的元素是不在生成樹中的頂點。首先選擇乙個作為生成樹根結點的頂點，並將它放入u集合，然後在那些一端頂點在u集合中，而另一端頂點在v-u集合中的邊中找一條權最小的邊，並把這條邊和那個不在u集合中的頂點加入到生成樹中，即輸出這條邊，然後將其頂點新增到u集合中，重複這個操作n-1次。
kruskal算克魯斯卡爾演算法的基本思想則是以邊為主導地位，始終都是選擇當前可用的最小權值的邊。具體為： 設乙個有n個頂點的聯通網路為g(v, e)，最初先構造乙個只有 n 個頂點，沒有邊的非連通圖t = ，圖中每個頂點自成乙個連同分量。
當在e中選擇一條具有最小權值的邊時，若該邊的兩個頂點落在不同的連同分量上，則將此邊加入到t中；否則，則這條邊的兩個頂點落在同乙個連通分量上，則將此邊捨去（此後永不選用這條邊），重新選擇一條權值最小的邊。如此重複下去，直到所有頂點在同乙個連通分量上為止。
通過此次討論課，小組各個成員的溝通能力、團隊合作精神和能力等方面均得到很大提高對於團隊協作的意義有了很深刻的認識。大家分析問題、總結能力，運用專業知識解決實際問題的能力也得到了很大提公升。
實習報告終結版
湖南x x x x學院 畢業實習總結 實習單位 開發 實習時間 2013年3月至2013年6月 分院 經濟管理與人文科學系 班級 x xx 姓名 x x 學號 201034101042 指導教師 x x 2013年 6月 5日 一 實習的主要情況介紹 一 實習公司的簡介 x x x x開發 成立於2...
調查報告終結版
大學生就業情況問卷調查 姓名性別年齡學歷畢業年數調查表序號 1 作為大學生請問您認為現在形勢如何？單選題 a.形勢嚴峻，就業難 b.形勢正常 c.形勢較好，就業容易 d.不了解 2 請問你學習的專業為 你認為所學專業前景如何？單選題 a 很有前途 b 較有前途 c 一般 d 較無前途 e 很無前途 ...
劉瓊霞 開題報告 終結版
本科畢業 開題報告 擬定 題目 環己醇催化氧化合成環己烯的研究學院 化學與材料工程學院 專業 化學 班級 環10化本1 學號 2010407052 學生姓名 劉瓊霞 指導教師 吳林冬 副教授 凱里學院教務處制 2013年 9月 25 日填寫 填表須知 一 本表從凱里學院教務處 專區 不得隨意改變 結...