当前位置:首页 > yabo168亚博娱乐 > 其他 > 正文

数据结构:最小生成树--Prim算法

最小生成树:Prim算法?最小生成树?????给定一无向带权图,顶点数是n,要使图连通只需n-1条边,若这n-1条边的权值和最小,则称有这n个顶点和n-1条边构最小生成树:Prim算法?最小生成树?????给定一无向带权图,顶点数是n,要使图连通只需n-1条边,若这n-1条边的权值和最小,则称有这n个顶点和n-1条边构成了图的最小生成树(minimum-cost?spanning?tree)。?Prim算法?????Prim算法是解决最小生成树的常用算法。它采取贪心策略,从指定的顶点开始寻找最小权值的邻接点。图G=,初始时S={V0},把与V0相邻接,且边的权值最小的顶点加入到S。不断地把S中的顶点与V-S中顶点的最小权值边加入,直到所有顶点都已加入到S中。?算法说明?为了方便寻找最小权值的边,构建一最近边结构体CloseEdge:?//最近边
typedef?struct?closeedge_tag
{
int?adjvex;?//邻接点
int?weight;?//权值
}CloseEdge;创建一数组CloseEdge?closeedge[n];顶点u属于S,顶点v属于V-S,则closeedge[v].weight=min{weight(u,v)};closeedge[v].adjvex=u;另外设置一bool型的数组add,标记顶点i是否已加入S。结合closeedge和add即可得到当前最小权值边。每当有新的节点加入S时,则需更新closeedge。具体细节看代码。?实例?从V0开始?代码?类定义?#include?
#include
#include
using?namespace?std;
#define?MAXWEIGHT?100
//边
typedef?struct?edge_tag
{
int?tail;
int?head;
}Edge;
//最近边
typedef?struct?closeedge_tag
{
int?adjvex;?//邻接点
int?weight;?//权值
}CloseEdge;
class?Graph
{
private:
//顶点数?
int?numV;
//边数?
int?numE;
//邻接矩阵?
int?**matrix;
public:
Graph(int?numV);
//建图?
void?createGraph(int?numE);
//析构方法?
~Graph();
//Prim算法
void?Prim(int);
int?minEdgeVex(CloseEdge*,?bool*);
void?updateCloseEdge(CloseEdge*,?bool*,?int);
//打印邻接矩阵?
void?printAdjacentMatrix();
//检查输入?
bool?check(int,?int,?int);
};?类实现?//构造函数,指定顶点数目
Graph::Graph(int?numV)
{
//对输入的顶点数进行检测
while?(numV?<=?0)
{
cout?< cin?>>?numV;
}
this->numV?=?numV;
//构建邻接矩阵,并初始化
matrix?=?new?int*[numV];
int?i,?j;
for?(i?=?0;?i? matrix[i]?=?new?int[numV];
for?(i?=?0;?i? for?(j?=?0;?j? {
if?(i?==?j)
matrix[i][i]?=?0;
else
matrix[i][j]?=?MAXWEIGHT;
}
}
void?Graph::createGraph(int?numE)
{
/*
对输入的边数做检测
一个numV个顶点的有向图,最多有numV*(numV?-?1)条边
*/
while?(numE??numV*(numV?-?1))
{
cout?< cin?>>?numE;
}
this->numE?=?numE;
int?tail,?head,?weight,?i;
i?=?0;
cout?< while?(i? {
cin?>>?tail?>>?head?>>?weight;
while?(!check(tail,?head,?weight))
{
cout?< cin?>>?tail?>>?head?>>?weight;
}
//Prim算法主要针对的是无向图
matrix[tail][head]?=?weight;
matrix[head][tail]?=?weight;
i++;
}
}
Graph::~Graph()
{
int?i;
for?(i?=?0;?i? delete[]?matrix[i];
delete[]matrix;
}
/*
Prim算法
求最小生成树
*/
void?Graph::Prim(int?vertex)
{
//有numV个顶点的图的最小生成树有numV-1条边
Edge?*edges?=?new?Edge[numV?-?1];
//标记顶点是否加入
bool?*add?=?new?bool[numV];
memset(add,?0,?numV);
//先把vertex加入
add[vertex]?=?true;
//最近边
CloseEdge?*closeedge?=?new?CloseEdge[numV];
int?i;
//初始化最近边
for?(i?=?0;?i? {
closeedge[i].weight?=?matrix[vertex][i];
if?(!add[i]?&&?matrix[vertex][i]?>?0?&&?matrix[vertex][i]? closeedge[i].adjvex?=?vertex;
}
int?v,?count?=?0;
while?(count? {
//获取最近边的邻接点
v?=?minEdgeVex(closeedge,?add);
add[v]?=?true;
//把最小权值边依次加入数组edges
edges[count].tail?=?closeedge[v].adjvex;
edges[count].head?=?v;
//更新最近边
updateCloseEdge(closeedge,?add,?v);
count++;
}
cout?< for?(i?=?0;?i? cout?< //释放空间
delete[]edges;
delete[]add;
delete[]closeedge;
}
//从closeedge中寻找最小边的邻接顶点
int?Graph::minEdgeVex(CloseEdge?*closeedge,?bool?*add)
{
int?i,?v,?w;?
v?=?0;
w?=?MAXWEIGHT;
for?(i?=?0;?i? if?(!add[i]?&&?closeedge[i].weight? {
w?=?closeedge[i].weight;
v?=?i;
}
return?v;
}
//顶点v的加入后,需要更新最近边
void?Graph::updateCloseEdge(CloseEdge*?closeedge,?bool?*add,?int?v)
{
int?i;
for?(i?=?0;?i? if?(!add[i]?&&?matrix[v][i]? {
closeedge[i].adjvex?=?v;
closeedge[i].weight?=?matrix[v][i];
}
}
//打印邻接矩阵?
void?Graph::printAdjacentMatrix()
{
int?i,?j;
cout.setf(ios::left);
cout?< for?(i?=?0;?i? cout?< cout?< for?(i?=?0;?i? {
cout?< for?(j?=?0;?j? cout?< cout?< }
}
bool?Graph::check(int?tail,?int?head,?int?weight)
{
if?((tail?==?head)?||?tail?=?numV?
||?head?=?numV
||?weight?<=?0?||?weight?>=?MAXWEIGHT)
return?false;
return?true;
}主函数?int?main()
{
cout?< int?numV,?numE;
cout?< cout?< cin?>>?numV;
Graph?graph(numV);
cout?< cin?>>?numE;
graph.createGraph(numE);
cout?< /*
由于输出结果太长,不利于截图,故只打印一半的节点
要想获得从所有节点开始的最小生成树,修改i的变化范围即可
*/
for?(int?i?=?0;?i? graph.Prim(i);
system("pause");
return?0;
}运行?完整代码下载:Prim算法?转载请注明出处,本文地址:http://blog.csdn.net/zhangxiangdavaid/article/details/38377091?若有所帮助,顶一个哦!?专栏目录:?数据结构与算法目录??c指针
友情链接
异常 - Exception - Copyright ? 2014 - 2014 - 亚搏体育app异常网 - 鄂ICP备14001750号 - 网站地图