實(shí)驗(yàn)3 貪心算法

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

2、樹結(jié)構(gòu)是研究數(shù)據(jù)元素之間的一對(duì)多的關(guān)系。在這種結(jié)構(gòu)中，每個(gè)元素對(duì)下(層)可以有0個(gè)或多個(gè)元素相聯(lián)系，對(duì)上(層)只有唯一的一個(gè)元素相關(guān)，數(shù)據(jù)元素之間有明顯的層次關(guān)系。樹形結(jié)構(gòu)一個(gè)對(duì)多個(gè)，如3、算法偽代碼Prim(G,E,W)輸入：連通圖G輸出：G的最小生成樹T1. S1;T=2. While V-S do3. 從V-S中選擇j使得j到S中頂點(diǎn)的邊e的權(quán)最??；TTe4. SSj3、算法分析時(shí)間復(fù)雜度：O(n)空間復(fù)雜度：O(n2)4、關(guān)鍵代碼（含注釋）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為終點(diǎn)的邊的最小權(quán)值，當(dāng)lowcosti=0時(shí)表示終點(diǎn)i加入生成樹 */ int lowcost=new intn+1; /* msti記錄對(duì)應(yīng)lowcosti的起點(diǎn)，當(dāng)msti=0時(shí)表示起點(diǎn)i加入生成樹 */ int mst=new intn+1; int min, minid, sum = 0; /* 默認(rèn)選擇1號(hào)節(jié)點(diǎn)加入生成樹，從2號(hào)節(jié)點(diǎn)開始初始化 */ for (int i = 2; i = n; i+)/* 最短距離初始化為其他節(jié)點(diǎn)到1號(hào)節(jié)點(diǎn)的距離 */low

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

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

6、= minid; /* 返回最小權(quán)值和 */return sum; public static void main(String args) Scanner sc=new Scanner(System.in); int cost; char chx, chy; /* 讀取節(jié)點(diǎn)和邊的數(shù)目 */ int n=sc.nextInt();/節(jié)點(diǎn) int m=sc.nextInt();/邊數(shù) int graph=new intn+1n+1; /* 初始化圖，所有節(jié)點(diǎn)間距離為無窮大 */ 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); /* 輸出最小權(quán)值和 */ System.out.println(Total:+cost); 5、實(shí)驗(yàn)結(jié)果（1）輸入（2）輸出最小生成樹的權(quán)值為：生成過程： (a) (b) (c) (d) (e) 四、實(shí)