篇一：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)跟边的数目有关，适合稀疏图。
三、数据结构的设计 图采用类存储，定义如下： cla 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 using namespace std; const int maxweight=10000; const int defaultvertices=10000; const int maxedges=10000; const int maxint = 10000000; cla 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
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-1&&v2=0&&i
istream& operator>>(istream &in ,graph &g) { }; //输出图对象
ostream& operator
in>>vertices>>edges; for(i=1;i>start>>end>>weight; j=g.getvertexpos(start); k=g.getvertexpos(end); if(j==-1||k==-1) {} g.insertedge(j,k,weight); i++; cout
黄冈师范学院 提高型实验报告
实验课题 最小生成树的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 #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;iv;i++) for(j=1;jv;j++) if(i==j) g->edges[i][j]=0; else{ g->edges[i][j]=inf;} for(k=1;ke;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;iv;i++) {printf(\\n); for(j=1;jv;j++) printf((g->edges[i][j]==inf)?∞\\t:%d\\t,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;iv;i++) /*n个顶点，n-1条边 */ {lowcost[i]=g->edges[1][i];closest[i]=1; } lowcost[1]=0; /*标志顶点1加入u集合*/ for(i=2;iv;i++) /*形成n-1条边的生成树 */ {min=inf; k=0; for(j=2;jv;j++) if((lowcost[j]v;j++)/*修改由顶点k到其他顶点边的权值*/ 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;iv;i++) /*n个顶点，n-1条边 */ { lowcost[i]=g->edges[1][i]; /*初始化*/ closest[i]=1; } /*顶点未加入到最小生成树中 */ drawwapicture(lowcost,closest,g->v);lowcost[1]=0; drawwapicture(lowcost,closest,g->v); for(i=2;iv;i++) /*形成n-1条边的生成树 */ { min=inf; k=0; for(j=2;jv;j++) if((lowcost[j]v); cprintf((%d,%d)%2d\\t,closest[k],k,min); lowcost[k]=0;/*顶点k加入u*/ drawwapicture(lowcost,closest,g->v); for(j=2;jv;j++)/*修改由顶点k到其他顶点边的权值*/
