第一篇：用貪心算法求解Prim算法上機實驗報告書
算法分析與設(shè)計
實驗報告
班級：學(xué)號：姓名：上機時間：
一、實驗?zāi)康呐c要求：
1、熟悉貪心算法的基本原理和適用范圍；
2、使用貪心算法編程，求解最小生成樹問題。
二、實驗題目：
用貪心算法求解Prim算法
三、實驗內(nèi)容：
任選一種貪心算法（prim或Kruskal），求解最小生成樹。對算法進行
描述和復(fù)雜性分析。編程實現(xiàn)。
四、問題描述：
設(shè)G=(V,E)是連通帶權(quán)圖，V={1,2,…,n}。構(gòu)造G的最小生成樹的Prim
算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如
下的貪心選擇：選取滿足條件i∈s，j∈V-S，且c[i][j]最小的邊，將頂
點j添加到S中。這個過程一直進行到S=V時為止。在這個過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。
五、問題分析與算法設(shè)計
六、實驗結(jié)果及分析
七、實驗總結(jié)
八、程序代碼
#include
#include
#include
#include
#include
#define maxint 20
#define inf 700
int AllSelected(int n,int s[])
{
int i;
for(i = 1;i <= n;i++)
{
if(s[i] == 0)
return 0;
}
return 1;
}
void Prim(int n,int **c)
{
int lowcost[maxint];
int closest[maxint];
bools[maxint];s[1]=true;
for(int i=2;i<=n;i++)
{
lowcost[i]=c[1][i];
closest[i]=1;
s[i]=false;
}
for(i=1;i<=n;i++)
{
int min=inf;
int j=1;
for(int k=2;k<=n;k++)
{
if((lowcost[k] { min=lowcost[k]; j=k; } s[j]=true; for(int k=2;k<=n;k++) if((c[j][k] { lowcost[k]=c[j][k];closest[k]=j; } } } } void main() { int n,i,j; int **k; printf(“請輸入頂點個數(shù):”); scanf(“%d”,&n); k=(int **)malloc(sizeof(int *)*(n + 1)); for(i = 1;i <= n;i++) k[i] =(int *)malloc(sizeof(int)*(n+1)); printf(“輸入頂點間的權(quán)值(自己到自己為0，沒有路的為大于其他任何值的數(shù)):n”);for(i=1;i<=n;i++) for(j=i;j<=n;j++) { printf(“k[%d][%d]=k[%d][%d]=”,i,j,j,i); scanf(“%d”,&k[i][j]); k[j][i]=k[i][j]; } printf(“n”); printf(“頂點t”); for(i=1;i<=n;i++) { printf(“%dt”,i); } printf(“n”); for(i=1;i<=n;i++) { printf(“%dt”,i); for(j=1;j<=n;j++) { printf(“%dt”,k[i][j]); } printf(“n”); } printf(“n”); Prim(n,k); } 《算法設(shè)計與分析》實驗報告 實驗3貪心算法 姓名 學(xué)號班級 實驗日期實驗地點 一、實驗?zāi)康?/p> 1、掌握貪心算法的設(shè)計思想。 2、理解最小生成樹的相關(guān)概念。 二、實驗環(huán)境 1、硬件環(huán)境 CPU：酷睿i5 內(nèi)存：4GB 硬盤：1T 2、軟件環(huán)境 操作系統(tǒng)：Windows10 編程環(huán)境：jdk 編程語言：Java 三、實驗內(nèi)容：在Prim算法與Kruskal算法中任選一種求解最小生成樹問題。 1、你選擇的是：Prim算法 2、數(shù)據(jù)結(jié)構(gòu) （1）圖的數(shù)據(jù)結(jié)構(gòu)——圖結(jié)構(gòu)是研究數(shù)據(jù)元素之間的多對多的關(guān)系。在這種結(jié)構(gòu)中，任意兩個元素之間可能存在關(guān)系，即結(jié)點之間的關(guān)系可以是任意的，圖中任意元素之間都可能相關(guān)。 圖形結(jié)構(gòu)——多個對多個，如 （2）樹的數(shù)據(jù)結(jié)構(gòu)——樹結(jié)構(gòu)是研究數(shù)據(jù)元素之間的一對多的關(guān)系。在這種結(jié)構(gòu)中，每個元素對下(層)可以有0個或多個元素相聯(lián)系，對上(層)只有唯一的一個元素相關(guān)，數(shù)據(jù)元素之間有明顯的層次關(guān)系。樹形結(jié)構(gòu)——一個對多個，如 3、算法偽代碼 Prim(G,E,W)輸入：連通圖G 輸出：G的最小生成樹T 1.S←{1};T=? 2.While V-S ≠? do 3.從V-S中選擇j使得j到S中頂點的邊e的權(quán)最??；T←T∪{e} 4.S←S∪{j} 3、算法分析 時間復(fù)雜度：O(n)空間復(fù)雜度：O(n^2) 4、關(guān)鍵代碼（含注釋） package Prim; import java.util.*;publicclass Main { staticintMAXCOST=Integer.MAX_VALUE; staticint Prim(intgraph[][], intn){ /* lowcost[i]記錄以i為終點的邊的最小權(quán)值，當(dāng)lowcost[i]=0時表示終點i加入生成樹 */ intlowcost[]=newint[n+1]; /* mst[i]記錄對應(yīng)lowcost[i]的起點，當(dāng)mst[i]=0時表示起點i加入生成樹 */ intmst[]=newint[n+1]; intmin, minid, sum = 0; /* 默認選擇1號節(jié)點加入生成樹，從2號節(jié)點開始初始化 */ for(inti = 2;i<= n;i++){ /* 標(biāo)記1號節(jié)點加入生成樹 */ mst[1] = 0; /* n個節(jié)點至少需要n-1條邊構(gòu)成最小生成樹 */ for(inti = 2;i<= n;i++){ /* 找滿足條件的最小權(quán)值邊的節(jié)點minid */ for(intj = 2;j<= n;j++){ /* 輸出生成樹邊的信息:起點，終點，權(quán)值 */ System.out.printf(“%c1, minid + 'A''A' + 1;intj = chy-'A' + 1;graph[i][j] = cost;graph[j][i] = cost;for(intj = 1;j<= n;j++){ } graph[i][j] = MAXCOST;} } System.out.println(”Total:"+cost);} } 5、實驗結(jié)果（1）輸入 （2）輸出 最小生成樹的權(quán)值為： 生成過程： (a) (b) (d) (e) (c) 四、實驗總結(jié)（心得體會、需要注意的問題等） 這次實驗，使我受益匪淺。這次實驗我選擇了Prim算法來求出樹的最小生成樹，在編寫代碼的過程中，我對Prim算法有了更深的了解，也使我對算法設(shè)計與分析更有興趣，今后一定要更努力的學(xué)習(xí)這門課。 篇一：prim算法實驗報告 算法實驗報告 學(xué)院：xxx 班級：xxx 學(xué)號：xxx 姓名：xxx prim 篇二：prim最小生成樹算法實驗報告 算法分析與設(shè)計之prim 學(xué)院：軟件學(xué)院 學(xué)號：201421031059 姓名：呂呂 一、問題描述 1.prim的定義 prim算法是貪心算法的一個實例，用于找出一個有權(quán)重連通圖中的最小生成樹，即：具有最小權(quán)重且連接到所有結(jié)點的樹。(強調(diào)的是樹，樹是沒有回路的)。2.實驗?zāi)康?/p> 選擇一門編程語言，根據(jù)prim算法實現(xiàn)最小生成樹，并打印最小生成樹權(quán)值。 二、算法分析與設(shè)計 1.prim算法的實現(xiàn)過程 基本思想：假設(shè)g＝(v，e)是連通的，te是g上最小生成樹中邊的集合。算法從u＝{u0}（u0∈v）、te＝{}開始。重復(fù)執(zhí)行下列操作： 在所有u∈u，v∈v－u的邊(u，v)∈e中找一條權(quán)值最小的邊(u0,v0)并入集合te中，同時v0并入u，直到v＝u為止。 此時，te中必有n-1條邊，t=(v，te)為g的最小生成樹。prim算法的核心:始終保持te中的邊集構(gòu)成一棵生成樹。2.時間復(fù)雜度 prim算法適合稠密圖，其時間復(fù)雜度為o(n^2)，其時間復(fù)雜度與邊得數(shù)目無關(guān)，n為頂點數(shù)，而看ruskal算法的時間復(fù)雜度為o(eloge)跟邊的數(shù)目有關(guān)，適合稀疏圖。 三、數(shù)據(jù)結(jié)構(gòu)的設(shè)計 圖采用類存儲，定義如下： class graph { private: int *verticeslist;int **edge;int numvertices;int numedges;int maxvertices;graph();~graph();bool insertvertex(const int vertex);bool insertedge(int v1,int v2,int cost);int getvertexpos(int vertex);int getvalue(int i);int getweight(int v1,int v2);int numberofvertices();1 public: } void prim();其中，圖中結(jié)點連接情況及權(quán)值使用二重指針表示，即二維數(shù)組實現(xiàn)鄰接矩陣。 四、代碼與運行結(jié)果 代碼運行結(jié)果： 源碼： //普雷姆算法 #include int graph::getvalue(int i){ };int graph::getweight(int v1,int v2){ };int graph::numberofvertices(){ };int graph::numberofedges(){ };//插入結(jié)點 bool graph::insertvertex(const int vertex){ };//插入邊，v1和v2為結(jié)點在數(shù)組的下標(biāo) bool graph::insertedge(int v1,int v2,int cost){ if(v1>-1&&v1 istream& operator>>(istream &in ,graph &g){ };//輸出圖對象 ostream& operator<<(ostream &out,graph &g){ int i,j,vertices,edges;int start,end,weight;vertices=g.numberofvertices();edges=g.numberofedges();out< in>>vertices>>edges;for(i=1;i<=vertices;i++){ } i=0;while(i 黃岡師范學(xué)院 提高型實驗報告 實驗課題 最小生成樹的prim算法 （實驗類型：□綜合性 ■設(shè)計性 □應(yīng)用性） 實驗課程 算法程序設(shè)計 實驗時間2010年12月24日 學(xué)生姓名 周 媛鑫 專業(yè)班級 計科 0801 學(xué) 號 200826140110 一．實驗?zāi)康暮鸵?/p> （1）根據(jù)算法設(shè)計需要, 掌握連通網(wǎng)的靈活表示方法;（2）掌握最小生成樹的prim算法;（3）熟練掌握貪心算法的設(shè)計方法;二．實驗條件 （1）硬件環(huán)境：實驗室電腦一臺（2）軟件環(huán)境：wintc 三．實驗原理分析 （1）最小生成樹的定義： 假設(shè)一個單位要在n個辦公地點之間建立通信網(wǎng)，則連通n個地點只需要n-1條線路。可以用連通的無向網(wǎng)來表示n個地點以及它們之間可能設(shè)置的通信線路，其中網(wǎng)的頂點表示城市，邊表示兩地間的線路，賦于邊的權(quán)值表示相應(yīng)的代價。對于n個頂點的連通網(wǎng)可以建立許多不同的生成樹，每一棵生成樹都可以表示一個通信網(wǎng)。其中一棵使總的耗費最少，即邊的權(quán)值之和最小的生成樹，稱為最小生成樹。 （2）構(gòu)造最小生成樹可以用多種算法。其中多數(shù)算法利用了最小生成樹的下面一種簡稱為mst的性質(zhì)：假設(shè)n=(v,{e})是一個連通網(wǎng)，u是頂點集v的一個非空子集。若(u,v)是一條具有最小權(quán)值（代價）的邊，其中u∈u，v∈v-u，則必存在一棵包含邊(u.v)的最小生成樹。（3）普里姆（prim）算法即是利用mst性質(zhì)構(gòu)造最小生成樹的算法。算法思想如下： 假設(shè)n=(v,{e})和是連通網(wǎng)，te是n上最小生成樹中邊的集合。算法從u={u0}(u0∈v)，te={}開始，重復(fù)執(zhí)行下述操作：在所有u∈u，v∈v-u的邊(u, v)∈e中找一條代價最小的邊(u0, v0)并入集合te，同時v0并入u，直到u=v為止。此時te中必有n-1條邊，則t=(v,{te})為n的最小生成樹。四．實驗步驟 （1）數(shù)據(jù)結(jié)構(gòu)的設(shè)計 ： 采用鄰接矩陣的存儲結(jié)構(gòu)來存儲無向帶權(quán)圖更利于實現(xiàn)及操作： 鄰接矩陣的抽象數(shù)據(jù)結(jié)構(gòu)定義： #defineinfinityint_max //最大值 #define max_ertex_num20 //最大頂點數(shù) typedef enum {dg,dn,udg,udn}graphkind;//{有向圖,有向網(wǎng)，無向網(wǎng)，無向圖} typedef struct arc cell{ vrtype adj;// vrtype 是頂點關(guān)系的類型。對無權(quán)圖用1和0表示相鄰否； infotype * info;//該弧相關(guān)信息的指針 }arccell，adjmatrix [ max_vertex_num][max_vertex_num]； typedef struct { vertextype vexs [ max_vertex_num];//頂點向量adjmatrixarcs;// 鄰接矩陣 intvexnum , arcnum;//圖的當(dāng)前頂點數(shù)和弧數(shù) graphkindkind;// 圖的種類標(biāo)志 }mgraph;（2）函數(shù)設(shè)計 函數(shù)名稱 函數(shù)原型 功能描述 main()int main(void)系統(tǒng)調(diào)用主函數(shù) huiru()void huitu()繪制無向圖 graphicver()void graphicver(graph *g)輸出鄰接矩陣 prim()void prim(graph *g)prim算法演示（3）實驗源代碼 #include第二篇：實驗3 貪心算法（定稿）
第三篇：PRIM算法實驗報告