首页 范文大全 古典文学 职场知识 中国文学 公文书信 外国名著 寓言童话 百家讲坛 散文/诗歌 美文欣赏 礼仪知识 民俗风情
  • 范文大全
  • 古典文学
  • 职场知识
  • 中国文学
  • 公文书信
  • 外国名著
  • 寓言童话
  • 百家讲坛
  • 散文/诗歌
  • 美文欣赏
  • 礼仪知识
  • 民俗风情
  • 谜语大全
  • 名言警句
    • 蒲公英阅读网 > 寓言童话 > 正文

    Prim最小生成树算法实验报告

    时间：2020-11-26 12:34:00 来源：蒲公英阅读网 本文已影响人 蒲公英阅读网手机站

    相关热词搜索：算法 最小 生成

    　算法分析与设计之 Prim 学院：软件学院 学号：201421031059 姓名：吕吕

    　一、 问题描述 1. m Prim 的定义

    　 Prim 算法是贪心算法的一个实例，用于找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。(强调的是树，树是没有回路的)。

    　2. 实验目的 选择一门编程语言，根据 Prim 算法实现最小生成树，并打印最小生成树权值。

    　二、

    　算法分析与设计 m 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; public:

    　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(); } 其中，图中结点连接情况及权值使用二重指针表示，即二维数组实现邻接矩阵。

    　四、

    　代码与运行结果 代码运行结果：

    　 源码：

    　//普雷姆算法

    　#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;

    　int **Edge;

    　int numVertices;

    　int numEdges;

    　int maxVertices; public:

    　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);

    　};

    　istream& operator>>(istream& in,Graph &G); ostream& operator<<(ostream& out,Graph &G);

    　//默认构造函数 Graph::Graph() {

    　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; };

    　Graph::~Graph() {

    　delete []VerticesList;

    　 delete []Edge; };

    　//获取结点在结点数组中的下标，从0开始 int Graph::getVertexPos(int vertex) {

    　for(int i=0;i<numVertices;i++)

    　 if(VerticesList[i]==vertex)

    　return i;

    　return -1; };

    　//共有属性 int Graph::getValue(int i) {

    　return (i>=0&&i<=numVertices)?VerticesList[i]:NULL; }; int Graph::getWeight(int v1,int v2) {

    　return (v1!=-1&&v2!=-1)?Edge[v1][v2]:0; }; int Graph::NumberOfVertices() {

    　return numVertices; }; int Graph::NumberOfEdges() {

    　return numEdges; };

    　//插入结点 bool Graph::insertVertex(const int vertex) {

    　if(numVertices==maxVertices)

    　 return false;

    　VerticesList[numVertices++]=vertex;

    　return true; };

    　//插入边，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;

    　 numEdges++;

    　 return true;

    　}

    　else

    　 return false; };

    　//输入图信息 istream& operator>>(istream &in ,Graph &G) {

    　//边的范围是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++)

    　{

    　 G.insertVertex(i);

    　}

    　i=0;

    　while(i<edges)

    　{

    　 in>>start>>end>>weight;

    　 j=G.getVertexPos(start);

    　 k=G.getVertexPos(end);

    　 if(j==-1||k==-1)

    　cout<<"input error!"<<endl;

    　 else

    　 {

    　G.insertEdge(j,k,weight);

    　i++;

    　 }

    　}

    　return in; };

    　//输出图对象 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;

    　for(i=0;i<vertices;i++)

    　{

    　 for(j=i+1;j<vertices;j++)

    　 {

    　weight=G.getWeight(i,j);

    　if(weight>0 && weight<maxWeight)

    　{

    　 start=G.getValue(i);

    　 end=G.getValue(j);

    　 out<<"("<<start<<","<<end<<","<<weight<<")"<<endl;

    　}

    　 }

    　}

    　return out; };

    　//普雷姆算法 void Graph::Prim ()

    　{

    　int *lowcost,*nearvex;

    　int sum=0;

    　 lowcost=new int[numVertices];

    　nearvex=new int[numVertices];

    　for (int i=1;i<numVertices;i++)

    　{

    　 lowcost[i]=Edge[0][i];

    　 //顶点0到各顶点的代价

    　 nearvex[i]=0;

    　 //及最短带权路径

    　 }

    　 nearvex[0]=-1;

    　 //顶点0到生成树顶点集合

    　int count = 0;

    　 //生成树边值数组存放指针

    　for(int i=1;i<numVertices;i++)

    　//循环n-1次,加入n-1条边

    　{

    　 int min=MAXINT;

    　 int v=0;

    　 for(int j=0;j<numVertices;j++)

    　{

    　//顶点j不在最小生成树中且边<0,j>权值比min小

    　if (nearvex[j]!=-1 && lowcost[j]<min )

    　{

    　 v=j;

    　//求生成树外顶点到生成树内顶点具有最小

    　 min=lowcost[j];

    　//权值的边, v是当前具最小权值的边的位置

    　}

    　}

    　 //找到了下一个结点

    　 if(v!=0)

    　 {

    　//v==0表示再也找不到要求的顶点了

    　count++;

    　 //向生成树边值数组内存放

    　 sum+=lowcost[v];

    　nearvex[v]=-1;

    　//作该边已加入生成树标记

    　 //更新权值

    　for (int j=1;j<numVertices;j++)

    　{

    　 if (nearvex[j]!=-1 && Edge[v][j]<lowcost[j] ) //j不在生成树中

    　 {

    　 //需要修改

    　lowcost[j] = Edge[v][j];

    　nearvex[j] = v;

    　}

    　}

    　 }

    　}

    　int c=0;

    　 //cout<<sum<<endl;

    　for(int k=1;k<numVertices;k++)

    　 c+=lowcost[k];

    　cout<<c<<endl; }

    　int main() {

    　cout<<"请输入图结点数，边数和权值，格式如下："<<endl;

    　cout<<"结点数 边数"<<endl;

    　cout<<"结点 结点 权值"<<endl;

    　cout<<"结点 结点 权值"<<endl;

    　cout<<"结点 结点 权值"<<endl;

    　Graph G;

    　cin>>G;

    　 cout<<endl<<"图信息如下："<<endl<<G;

    　cout<<"最小生成树权值：";

    　G.Prim();

    　_sleep(100000);

    　return 0; } /*test

    　5 7 1 2 3 1 4 5 2 3 3 2 5 3 3 4 5 3 5 6 4 5 1 */

    　 （注：文档可能无法思考全面，请浏览后下载，供参考。可复制、编制，期待你的好评与关注！）

  • 三反、三查活动个人自查材料:个人自查材料
  • 精准扶贫调研报告范文 [深入推进精准健康
  • 怎样修改文档颜色样式 [Word文档如何修改
  • 【关于秋天的朗诵稿】 关于端午节的朗诵稿
  • 【小米盒子用着很卡怎么解决】 小米盒子卡
  • cd锤石符文出装_LOLS7辅助锤石符文天赋出装
  • 【学唱歌作文200字】学唱歌作文
  • 儿童节手抄报内容资料_6.1儿童节手抄报资料
  • _市物业管理条例学习心得
    • 范文大全
    • 职场知识
    • 精美散文
    • 名著
    • 讲坛
    • 诗歌
    • 礼仪知识
    最新文章

    推荐访问

    大反思大讨论活动 保安全” 筑防线 “查思想 贡献伟大时代” “以青春之我 工作评议报告 创建活动综述 市社保局党支部 自述报告 “党员先锋示范岗” 党建德育工作 达标创星活动 “星级党支部”创建 评星定级管理 社会组织党支部 第四巡察组 新进年轻干部 委厅机关 党性教育培训班 履职能力建设专题培训班 新考录社区工作者 “头雁领航”重点培训班 党组织业务培训 能力提升培训会 赋能经济高质量发展 “五好”园区 三年攻坚行动 行政管理能力建设提升班 高质量发展能力提升培训班 市疾控系统 中基层管理人员 专业能力提升专题培训班 新发展预备党员 进驻工作 迎接审计组 讲评推进大会 “三抓三促”行动动员 “永不过时的红岩精神” 市委党史研究室 科学绿化现场会 深化以案促改 一体推进不敢腐不能腐不想腐 奋斗精神 专题辅导讲稿 坚守使命追求 涉密 《党史学习教育工作条例》 百年新征程 “百年定位” 党课教育

    本文Prim最小生成树算法实验报告由蒲公英阅读网整理提供，版权归原作者、原出处所有。

    Copyright © 蒲公英阅读网 All Rights Reserved.