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)跟边的数目有关，适合稀疏图。

三、数据结构的设计 图采用类存储，定义如下： 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:%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;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)%2dt,closest[k],k,min);lowcost[k]=0;/*顶点k加入u*/ drawwapicture(lowcost,closest,g->v);for(j=2;jv;j++)/*修改由顶点k到其他顶点边的权值*/