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