prim算法实验报告.doc
文本预览下载声明
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)，其时间复杂度与边得数目无关，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 lt;iostreamgt;
using namespace std;
const int maxWeight=10000;
const int DefaultVertices=10000;
const int maxEdges=10000;
const int MAXINT =
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 amp;G); public:
istreamamp; operatorgt;gt;(istreamamp; in,Graph amp;G); ostreamamp; operatorlt;lt;(ostreamamp; out,Graph amp;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;ilt;maxVertices;i++) Edge[i]=new int[maxVertices]; //邻接矩阵表示权值 for(
显示全部