實驗3 貪心算法

1、算法設計與分析實驗報告實驗3 貪心算法姓名 學號 班級 實驗日期 實驗地點 一、實驗目的1、掌握貪心算法的設計思想。2、理解最小生成樹的相關概念。二、實驗環(huán)境1、硬件環(huán)境CPU：酷睿i5內(nèi)存：4GB硬盤：1T2、軟件環(huán)境操作系統(tǒng)：Windows10編程環(huán)境：jdk編程語言：Java三、實驗內(nèi)容：在Prim算法與Kruskal算法中任選一種求解最小生成樹問題。1、你選擇的是：Prim算法2、數(shù)據(jù)結構（1）圖的數(shù)據(jù)結構圖結構是研究數(shù)據(jù)元素之間的多對多的關系。在這種結構中，任意兩個元素之間可能存在關系，即結點之間的關系可以是任意的，圖中任意元素之間都可能相關。圖形結構多個對多個，如（2）樹的數(shù)據(jù)結構

2、樹結構是研究數(shù)據(jù)元素之間的一對多的關系。在這種結構中，每個元素對下(層)可以有0個或多個元素相聯(lián)系，對上(層)只有唯一的一個元素相關，數(shù)據(jù)元素之間有明顯的層次關系。樹形結構一個對多個，如3、算法偽代碼Prim(G,E,W)輸入：連通圖G輸出：G的最小生成樹T1. S1;T=2. While V-S do3. 從V-S中選擇j使得j到S中頂點的邊e的權最??；TTe4. SSj3、算法分析時間復雜度：O(n)空間復雜度：O(n2)4、關鍵代碼（含注釋）package Prim;import java.util.*;public class Main static int MAXCOST=Integ

3、er.MAX_VALUE; static int Prim(int graph, int n) /* lowcosti記錄以i為終點的邊的最小權值，當lowcosti=0時表示終點i加入生成樹 */ int lowcost=new intn+1; /* msti記錄對應lowcosti的起點，當msti=0時表示起點i加入生成樹 */ int mst=new intn+1; int min, minid, sum = 0; /* 默認選擇1號節(jié)點加入生成樹，從2號節(jié)點開始初始化 */ for (int i = 2; i = n; i+)/* 最短距離初始化為其他節(jié)點到1號節(jié)點的距離 */low

4、costi = graph1i; /* 標記所有節(jié)點的起點皆為默認的1號節(jié)點 */msti = 1; /* 標記1號節(jié)點加入生成樹 */ mst1 = 0; /* n個節(jié)點至少需要n-1條邊構成最小生成樹 */ for (int i = 2; i = n; i+)min = MAXCOST;minid = 0; /* 找滿足條件的最小權值邊的節(jié)點minid */ for (int j = 2; j = n; j+) /* 邊權值較小且不在生成樹中 */ if (lowcostj min & lowcostj != 0) min = lowcostj; minid = j; /* 輸出生成樹邊的

5、信息:起點，終點，權值 */System.out.printf(%c - %c : %dn, mstminid + A - 1, minid + A - 1, min); /* 累加權值 */ sum += min; /* 標記節(jié)點minid加入生成樹 */ lowcostminid = 0; /* 更新當前節(jié)點minid到其他節(jié)點的權值 */ for (int j = 2; j = n; j+) /* 發(fā)現(xiàn)更小的權值 */ if (graphminidj lowcostj) /* 更新權值信息 */ lowcostj = graphminidj; /* 更新最小權值邊的起點 */ mstj

6、= minid; /* 返回最小權值和 */return sum; public static void main(String args) Scanner sc=new Scanner(System.in); int cost; char chx, chy; /* 讀取節(jié)點和邊的數(shù)目 */ int n=sc.nextInt();/節(jié)點 int m=sc.nextInt();/邊數(shù) int graph=new intn+1n+1; /* 初始化圖，所有節(jié)點間距離為無窮大 */ for (int i = 1; i = n; i+)for (int j = 1; j = n; j+)graphij

7、 = MAXCOST; /* 讀取邊信息 */ for (int k = 0; k m; k+) chx=sc.next().charAt(0); chy=sc.next().charAt(0); cost=sc.nextInt(); int i = chx - A + 1; int j = chy - A + 1; graphij = cost; graphji = cost; /* 求解最小生成樹 */ cost = Prim(graph, n); /* 輸出最小權值和 */ System.out.println(Total:+cost); 5、實驗結果（1）輸入（2）輸出最小生成樹的權值為：生成過程： (a) (b) (c) (d) (e) 四、實