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

文档介绍：该【Prim最小生成树算法实验报告 】是由【jiyudian11】上传分享，文档一共【8】页，该文档可以免费在线阅读，需要了解更多关于【Prim最小生成树算法实验报告 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。算法分析与设计之Prim
学院:软件学院学号:201421031059姓名:吕吕
一、问题描述

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

选择一门编程语言,根据Prim算法实现最小生成树,并打印最小生成树权值。
二、算法分析与设计

基本思想:假设G=(V,E)是连通的,TE是G上最小生成树中边的集合。算法从U={uO}(uOuV)、TE={}开始。重复执行下列操作:
在所有uuU,vuV—U的边(u,v)eE中找一条权值最小的边(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)跟边的数目有关,适合稀疏图。
三、数据结构的设计
图采用类存储,定义如下:
classGraph
{
private:
int*VerticesList;
int**Edge;
intnumVertices;
intnumEdges;
intmaxVertices;
public:
Graph();
〜Graph();
boolinsertVertex(constintvertex);
boolinsertEdge(intv1,intv2,intcost);
intgetVertexPos(intvertex);
intgetValue(inti);
intgetWeight(intv1,intv2);
intNumberOfVertices();
intNumberOfEdges();voidPrim();
}
其中,图中结点连接情况及权值使用二重指针表示,即二维数组实现邻接矩阵。
四、代码与运行结果
代码运行结果:
;边数知叹直格式扪下:
2
2
3
3

旦
•写薯匸捲7
PH结结结5
数<1
豁边点点占小
匡儿结结结
3
3
5
6
1
|图彳吕息如下;
<1,4r5>
<3,4f5>
<3,5,6>
帛:禄M电佰:10
源码:
//普雷姆算法
#include<iostream〉
usingnamespacestd;
constintmaxWeight=10000;
constintDefaultVertices=10000;
constintmaxEdges=10000;
constintMAXINT=10000000;
classGraph
{
private:
int*VerticesList;
int**Edge;
intnumVertices;
intnumEdges;
intmaxVertices;
public:
Graph();
〜Graph();
boolinsertVertex(constintvertex);
boolinsertEdge(intv1,intv2,intcost);intgetVertexPos(intvertex);
intgetValue(inti);
intgetWeight(intv1,intv2);
intNumberOfVertices();
intNumberOfEdges();
voidPrim();
voidlvlv(Graph&G);
};
istream&operator〉〉(istream&in,Graph&G);ostream&operator〈〈(ostream&out,Graph&G);
//默认构造函数
Graph::Graph()
{
maxVertices=DefaultVertices;
numVertices=0;
numEdges=0;
inti,j;
VerticesList=newint[maxVertices];Edge=(int**)newint*[maxVertices];
for(i=0;i〈maxVertices;i++)
Edge[i]=newint[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开始
intGraph::getVertexPos(intvertex)
{
for(inti=0;i〈numVertices;i++)
if(VerticesList[i]==vertex)
returni;
return-1;
};
//共有属性
intGraph::getValue(inti)
{
return(i〉=0&&i〈=numVertices)?VerticesList[i]:NULL;
};
intGraph::getWeight(intv1,intv2)
{
return(v1!=T&&v2!=-1)?Edge[v1][v2]:0;
};
intGraph::NumberOfVertices()
{
returnnumVertices;
};
intGraph::NumberOfEdges()
{
returnnumEdges;
};
//插入结点
boolGraph::insertVertex(constintvertex)
{
if(numVertices==maxVertices)
returnfalse;
VerticesList[numVertices++]=vertex;
returntrue;
};
//插入边,v1和v2为结点在数组的下标
boolGraph::insertEdge(intv1,intv2,intcost)
{
if(v1〉T&&v1〈numVertices&&v2〉T&&v2〈numVertices&&Edge[v1][v2]==maxWeight)
{
Edge[v1][v2]=Edge[v2][v1]=cost;
numEdges++;returntrue;
}
else
returnfalse;
};
//输入图信息
istream&operator〉〉(istream&in,Graph&G){
//边的范围是n-1至n(nT)/2,n为顶点数intedges,vertices,i,j,k;
intstart,end,weight;
//输入顶点
in〉〉vertices〉〉edges;
for(i=1;i<=vertices;i++)
{
(i);
}
i=0;
while(i<edges)
{
in>>start〉〉end〉〉weight;
j=(start);k=(end);
if(j==-l||k==-1)
cout〈〈"inputerror!"〈〈endl;else
{
(j,k,weight);i++;
}
}
returnin;
};
//输出图对象
ostream&operator〈〈(ostream&&G){
inti,j,vertices,edges;
intstart,end,weight;
vertices=();edges=();
out〈〈vertices〈〈","〈〈edges〈〈endl;
for(i=0;i〈vertices;i++)
{
for(j=i+1;j〈vertices;j++)
{
weight=(i,j);
if(weight〉0&&weight<maxWeight)
{
start=(i);
end=(j);
out<<"("<<start〈〈","〈〈end〈〈","〈〈weight<<")"<<endl;}
}
}
returnout;
};
//普雷姆算法
voidGraph::Prim()
{
int*lowcost,*nearvex;
intsum=0;
lowcost=newint[numVertices];
nearvex=newint[numVertices];
for(inti=1;i〈numVertices;i++)
{
lowcost[i]=Edge[0][i]; //顶点0到各顶点的代价
nearvex[i]=0; //及最短带权路径
}
nearvex[0]=-1; //顶点0到生成树顶点集合
intcount=0; //生成树边值数组存放指针
for(inti=1;i〈numVertices;i++)//循环n-1次,加入n-1条边
{
intmin=MAXINT;
intv=0;
for(intj=0;j〈numVertices;j++)
{
//顶点j不在最小生成树中且边〈0,j〉权值比min小if(nearvex[j]!=T&&lowcost[j]〈min)
{
v=j; //求生成树外顶点到生成树内顶点具有最小
min=lowcost[j]; //权值的边,v是当前具最小权值的边的位置
}
//找到了下一个结点
if(v!=0)
{ //v==0表示再也找不到要求的顶点了
count++; //向生成树边值数组内存放
sum+=lowcost[v];
nearvex[v]=T; //作该边已加入生成树标记
//更新权值
for(intj=1;j〈numVertices;j++)
{
if(nearvex[j]!=T&&Edge[v][j]〈lowcost[j])//j不在生成树中{
//需要修改
lowcost[j]=Edge[v][j];nearvex[j]=v;
}
}
}
}
intc=0;
//cout<〈sum〈〈endl;
for(intk=1;k〈numVertices;k++)c+=lowcost[k];
cout〈〈c〈〈endl;
}
intmain()
{
cout〈〈"请输入图结点数,边数和权值,格式如下:"〈〈endl;
cout〈〈"结点数边数"〈〈endl;
cout〈〈"结点结点权值"〈〈endl;
cout〈〈"结点结点权值"〈〈endl;
cout〈〈"结点结点权值"〈〈endl;
GraphG;
cin〉〉G;
cout〈〈endl〈〈"图信息如下:"〈〈endl〈〈G;
cout〈〈"最小生成树权值:";
();
_sleep(100000);
return0;
}
/*test
57
23
45
33
53
45
56
51
*/