第一篇：PRIM算法實(shí)驗(yàn)報(bào)告

篇一：prim算法實(shí)驗(yàn)報(bào)告

算法實(shí)驗(yàn)報(bào)告

學(xué)院：xxx 班級：xxx 學(xué)號：xxx 姓名：xxx prim 篇二：prim最小生成樹算法實(shí)驗(yàn)報(bào)告 算法分析與設(shè)計(jì)之prim 學(xué)院：軟件學(xué)院 學(xué)號：201421031059 姓名：呂呂

一、問題描述 1.prim的定義

prim算法是貪心算法的一個實(shí)例，用于找出一個有權(quán)重連通圖中的最小生成樹，即：具有最小權(quán)重且連接到所有結(jié)點(diǎn)的樹。(強(qiáng)調(diào)的是樹，樹是沒有回路的)。2.實(shí)驗(yàn)?zāi)康?/p>

選擇一門編程語言，根據(jù)prim算法實(shí)現(xiàn)最小生成樹，并打印最小生成樹權(quán)值。

二、算法分析與設(shè)計(jì)

1.prim算法的實(shí)現(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為頂點(diǎn)數(shù)，而看ruskal算法的時間復(fù)雜度為o(eloge)跟邊的數(shù)目有關(guān)，適合稀疏圖。

三、數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì) 圖采用類存儲，定義如下： 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é)點(diǎn)連接情況及權(quán)值使用二重指針表示，即二維數(shù)組實(shí)現(xiàn)鄰接矩陣。

四、代碼與運(yùn)行結(jié)果 代碼運(yùn)行結(jié)果：

源碼：

//普雷姆算法

#include using namespace std;const int maxweight=10000;const int defaultvertices=10000;const int maxedges=10000;const int maxint = 10000000;class graph{ private: int *verticeslist;2 };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();int numberofedges();void prim();void lvlv(graph &g);public: istream& operator>>(istream& in,graph &g);ostream& operator<<(ostream& out,graph &g);//默認(rèn)構(gòu)造函數(shù) graph::graph(){ };graph::~graph(){ delete []verticeslist;delete []edge;3 maxvertices=defaultvertices;numvertices=0;numedges=0;int i,j;verticeslist=new int [maxvertices];edge=(int **)new int *[maxvertices];for(i=0;i

int graph::getvalue(int i){ };int graph::getweight(int v1,int v2){ };int graph::numberofvertices(){ };int graph::numberofedges(){ };//插入結(jié)點(diǎn) bool graph::insertvertex(const int vertex){ };//插入邊，v1和v2為結(jié)點(diǎn)在數(shù)組的下標(biāo)

bool graph::insertedge(int v1,int v2,int cost){

if(v1>-1&&v1-1&&v2=0&&i<=numvertices)?verticeslist[i]:null;return(v1!=-1&&v2!=-1)?edge[v1][v2]:0;return numvertices;return numedges;if(numvertices==maxvertices)return false;verticeslist[numvertices++]=vertex;return true;};} return true;else return false;//輸入圖信息

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>start>>end>>weight;j=g.getvertexpos(start);k=g.getvertexpos(end);if(j==-1||k==-1){} g.insertedge(j,k,weight);i++;cout<

黃岡師范學(xué)院 提高型實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)課題 最小生成樹的prim算法

（實(shí)驗(yàn)類型：□綜合性 ■設(shè)計(jì)性 □應(yīng)用性）

實(shí)驗(yàn)課程 算法程序設(shè)計(jì) 實(shí)驗(yàn)時間2010年12月24日

學(xué)生姓名 周 媛鑫 專業(yè)班級 計(jì)科 0801 學(xué) 號 200826140110 一．實(shí)驗(yàn)?zāi)康暮鸵?/p>

（1）根據(jù)算法設(shè)計(jì)需要, 掌握連通網(wǎng)的靈活表示方法;（2）掌握最小生成樹的prim算法;（3）熟練掌握貪心算法的設(shè)計(jì)方法;二．實(shí)驗(yàn)條件

（1）硬件環(huán)境：實(shí)驗(yàn)室電腦一臺（2）軟件環(huán)境：wintc 三．實(shí)驗(yàn)原理分析

（1）最小生成樹的定義：

假設(shè)一個單位要在n個辦公地點(diǎn)之間建立通信網(wǎng)，則連通n個地點(diǎn)只需要n-1條線路?？梢杂眠B通的無向網(wǎng)來表示n個地點(diǎn)以及它們之間可能設(shè)置的通信線路，其中網(wǎng)的頂點(diǎn)表示城市，邊表示兩地間的線路，賦于邊的權(quán)值表示相應(yīng)的代價。對于n個頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹，每一棵生成樹都可以表示一個通信網(wǎng)。其中一棵使總的耗費(fèi)最少，即邊的權(quán)值之和最小的生成樹，稱為最小生成樹。

（2）構(gòu)造最小生成樹可以用多種算法。其中多數(shù)算法利用了最小生成樹的下面一種簡稱為mst的性質(zhì)：假設(shè)n=(v,{e})是一個連通網(wǎng)，u是頂點(diǎn)集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的最小生成樹。四．實(shí)驗(yàn)步驟

（1）數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì) ：

采用鄰接矩陣的存儲結(jié)構(gòu)來存儲無向帶權(quán)圖更利于實(shí)現(xiàn)及操作： 鄰接矩陣的抽象數(shù)據(jù)結(jié)構(gòu)定義： #defineinfinityint_max //最大值

#define max_ertex_num20 //最大頂點(diǎn)數(shù)

typedef enum {dg,dn,udg,udn}graphkind;//{有向圖,有向網(wǎng)，無向網(wǎng)，無向圖} typedef struct arc cell{ vrtype adj;// vrtype 是頂點(diǎn)關(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];//頂點(diǎn)向量adjmatrixarcs;// 鄰接矩陣 intvexnum , arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) graphkindkind;// 圖的種類標(biāo)志 }mgraph;（2）函數(shù)設(shè)計(jì)

函數(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）實(shí)驗(yàn)源代碼

#include #include #include #include #include #define maxvertexnum 50 #define inf 32767 typedef struct graphic {char vexs[maxvertexnum];int edges[maxvertexnum][maxvertexnum];int v,e;}graph;char tmp[10];void huitu()/*無向圖的圖形生成*/ {char buffer[100];int graphdriver = detect, graphmode;int i,xbefore,ybefore;int x1,y1;char c;/*registerbgidriver(egavga_driver);initgraph(&graphdriver, &graphmode,);cleardevice();printf(input pot(300v,&g->e);for(i=1;i<=g->v;i++)for(j=1;j<=g->v;j++)if(i==j)g->edges[i][j]=0;else{ g->edges[i][j]=inf;} for(k=1;k<=g->e;k++){printf(input %dth edge :,k);scanf(%d,%d,%d,&v1,&v2,&weight);g->edges[v1][v2]=g->edges[v2][v1]=weight;} for(i=1;i<=g->v;i++){printf(n);for(j=1;j<=g->v;j++)printf((g->edges[i][j]==inf)?∞t:%dt,g->edges[i][j]);} printf(n);system(pause);} /***************prim 算法生成最小生成樹***************/ void prim(graph *g){int lowcost[maxvertexnum],closest[maxvertexnum];int i,j,k,min;for(i=2;i<=g->v;i++)/*n個頂點(diǎn)，n-1條邊 */ {lowcost[i]=g->edges[1][i];closest[i]=1;} lowcost[1]=0;/*標(biāo)志頂點(diǎn)1加入u集合*/ for(i=2;i<=g->v;i++)/*形成n-1條邊的生成樹 */ {min=inf;k=0;for(j=2;j<=g->v;j++)if((lowcost[j]v;j++)/*修改由頂點(diǎn)k到其他頂點(diǎn)邊的權(quán)值*/ if(g->edges[k][j]edges[k][j];closest[j]=k;}printf(n);} } setviewport(150,140,630,310,1);cleardevice();setcolor(green);rectangle(10,10,470,160);line(10,60,470,60);line(10,110,470,110);for(i=0;i