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 <iostream> 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); //默认构造函数 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<maxvertices;i++) edge[i]=new int[maxvertices]; //邻接矩阵表示权值 for(i=0;i<maxvertices;i++)for(j=0;j<maxvertices;j++)

edge[i][j]=(i==j)?0:maxweight;//获取结点在结点数组中的下标，从0开始 int graph::getvertexpos(int vertex) { };

//共有属性

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<numvertices&&v2>-1&&v2<numvertices&&edge[v1][v2]==maxweight) { edge[v1][v2]=edge[v2][v1]=cost;

4 for(int i=0;i<numvertices;i++)if(verticeslist[i]==vertex) return i; return -1; return (i>=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<<vertices<<,<<edges<<endl; 5

//边的范围是n-1至n(n-1)/2,n为顶点数 int edges,vertices,i,j,k; int start,end,weight; //输入顶点 in>>vertices>>edges; for(i=1;i<=vertices;i++) { } i=0; while(i<edges) { } return in; in>>start>>end>>weight; j=g.getvertexpos(start); k=g.getvertexpos(end); if(j==-1||k==-1) {} g.insertedge(j,k,weight); i++; cout<<input error!<<endl; else g.insertvertex(i);篇三：最小生成树的prim算法提高型实验报告 黄冈师范学院 提高型实验报告

实验课题 最小生成树的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<graphics.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <conio.h>