最小生成树prim算法

Prim算法 最小生成树问题

算法同样是解决最小生成树的问题。

其算法为：在这n个点中的相通的边进行排序，然后不断地将边添加到集合中（体现了贪心的算法特点），在并入集合之前，必须检查一下这两点是不是在一个集合当中，这就用到了并查集的知识。直到边的集合达到了n-1个。

与prim算法的不同：prim算法为单源不断寻找连接的最短边，向外扩展，即单树形成森林。而Kruskal算法则是不断寻找最短边然后不断将集合合并，即多树形成森林。

复杂度的不同：prim算法的复杂度是O(n^2),其中n为点的个数。Kruskal算法的复杂度是O(e*loge)，其中e为边的个数。两者各有优劣，在不同的情况下选择不同的算法。

Prim算法用于求无向图的最小生成树。

设图G =（V，E），其生成树的顶点集合为U。

①、把v0放入U。

②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。

③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。

其算法的时间复杂度为O(n^2)。

Prim算法实现：

（1）集合：设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1）

（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。

{先选定一个点，然后从该点出发，与该点相连的点取权值最小者归入集合，然后再比较在集合中的两点与其它各点的边的权值最小者，再次进入集合，一直到将所有的点都归入集合为止。}。

用prim算法求最小生成树:c语言

你的图里有两条边权重一样，在实际计算前无法事先保证最小生成树的唯一性，即使是两个不同的Prim算法也可能产生不同的结果。

当然，计算完之后情况会略有不同，下面会解释。

Prim算法首先会依次选

E(1,2)=1

E(2,7)=2

E(2,3)=3

然后E(3,4)=E(7,6)=4，会面临两种选择。

如果优先选E(3,4)这条边，那么下一步仍然会选E(7,6)，反过来也一样，所以这个图恰好没影响。

继续下去最终得到

E(1,2)=1

E(2,7)=2

E(2,3)=3

E(3,4)=4

E(7,6)=4

E(4,5)=6

这样6条边构成唯一的最小生成树，总权重是20。

（唯一性是因为总权重不超过20的其它子图确实都不连通）

既然最小生成树唯一，Kruskal算法当然也会产生同一棵树。

c++求最小生成树prim算法,我捣鼓2天了,真心不会改了,求指导感激不尽啊

把main函数改成：

main(){

GraphMatrix graph = {。

"abcd",。

{{7,8,Max,15},{12,100,6,20},{Max,100,4,13},{Max,4,8,10}},。

};

Edge mst[Max];

int i,j;

prim(graph,mst);。

for(j=0;j<Max;j++)。

printf("%c\t",mst[j].stop_vex);。

printf("%c\t",mst[j].start_vex);。

printf("%d\n",mst[j].weight);。

还有GraphMatrix结构体里的vexs数组最好定义为vexs[VN+1]给字符串末尾的‘\0'留地方。

最小生成树

你的代码太乱，给你这个，添加了注释，容易看懂：

#include<stdio.h>。

#include<stdlib.h>。

#include<iostream>。

using namespace std;。

#define MAX_VERTEX_NUM 20。

#define OK 1

#define ERROR 0。

#define MAX 1000。

typedef struct Arcell。

double adj;

}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];。

typedef struct

char vexs[MAX_VERTEX_NUM]; //节点数组。

AdjMatrix arcs; //邻接矩阵。

int vexnum,arcnum; //图的当前节点数和弧数。

}MGraph;

typedef struct Pnode //用于普利姆算法。

char adjvex; //节点。

double lowcost; //权值。

}Pnode,Closedge[MAX_VERTEX_NUM]; //记录顶点集U到V-U的代价最小的边的辅助数组定义。

typedef struct Knode //用于克鲁斯卡尔算法中存储一条边及其对应的2个节点。

char ch1; //节点1。

char ch2; //节点2。

double value;//权值。

}Knode,Dgevalue[MAX_VERTEX_NUM];。

//-------------------------------------------------------------------------------。

int CreateUDG(MGraph & G,Dgevalue & dgevalue);。

int LocateVex(MGraph G,char ch);。

int Minimum(MGraph G,Closedge closedge);。

void MiniSpanTree_PRIM(MGraph G,char u);。

void Sortdge(Dgevalue & dgevalue,MGraph G);。

//-------------------------------------------------------------------------------。

int CreateUDG(MGraph & G,Dgevalue & dgevalue) //构造无向加权图的邻接矩阵。

int i,j,k;

cout<<"请输入图中节点个数和边/弧的条数：";。

cin>>G.vexnum>>G.arcnum;。

cout<<"请输入节点：";。

for(i=0;i<G.vexnum;++i)。

cin>>G.vexs[i];。

for(i=0;i<G.vexnum;++i)//初始化数组。

{

for(j=0;j<G.vexnum;++j)。

{

G.arcs[i][j].adj=MAX;。

}

}

cout<<"请输入一条边依附的定点及边的权值："<<endl;。

for(k=0;k<G.arcnum;++k)。

{

cin >> dgevalue[k].ch1 >> dgevalue[k].ch2 >> dgevalue[k].value;。

i = LocateVex(G,dgevalue[k].ch1);。

j = LocateVex(G,dgevalue[k].ch2);。

G.arcs[i][j].adj = dgevalue[k].value;。

G.arcs[j][i].adj = G.arcs[i][j].adj;。

}

return OK;

int LocateVex(MGraph G,char ch) //确定节点ch在图G.vexs中的位置。

int a ;

for(int i=0; i<G.vexnum; i++)。

{

if(G.vexs[i] == ch)。

a=i;

}

return a;

void MiniSpanTree_PRIM(MGraph G,char u)//普利姆算法求最小生成树。

int i,j,k;

Closedge closedge;。

k = LocateVex(G,u);。

// 将该顶点到其他所有的顶点权值赋值给closedge。

for(j=0; j<G.vexnum; j++)。

{

if(j != k)

{

closedge[j].adjvex = u;。

closedge[j].lowcost = G.arcs[k][j].adj;。

}

}

closedge[k].lowcost = 0;。

for(i=1; i<G.vexnum; i++)。

{

//找到权值最小的顶点，记录到k。

k = Minimum(G,closedge);。

cout<<"("<<closedge[k].adjvex<<","<<G.vexs[k]<<","<<closedge[k].lowcost<<")"<<endl;。

//清零，方便寻找下一个顶点。

closedge[k].lowcost = 0;。

for(j=0; j<G.vexnum; ++j)。

{

//依次比较上个顶点和当前顶点与剩余顶点的权值，将小的赋值给closedge。

if(G.arcs[k][j].adj < closedge[j].lowcost)。

{

closedge[j].adjvex = G.vexs[k];。

closedge[j].lowcost= G.arcs[k][j].adj;。

}

}

}

int Minimum(MGraph G,Closedge closedge) //求closedge中权值最小的边，并返回其顶点在vexs中的位置。

int i,j;

double k = 1000;。

for(i=0; i<G.vexnum; i++)。

{

if(closedge[i].lowcost != 0 && closedge[i].lowcost < k)。

{

k = closedge[i].lowcost;。

j = i;

}

}

return j;

void main()

int i,j;

MGraph G;

char u;

Dgevalue dgevalue;。

CreateUDG(G,dgevalue);。

cout<<"图的邻接矩阵为："<<endl;。

for(i=0; i<G.vexnum; i++)。

{

for(j=0; j<G.vexnum; j++)。

cout << G.arcs[i][j].adj<<" ";。

cout<<endl;。

}

cout<<"=============普利姆算法===============\n";。

cout<<"请输入起始点：";。

cin>>u;

cout<<"构成最小代价生成树的边集为：\n";。

MiniSpanTree_PRIM(G,u);。

最小生成树的两种算法？

最小生成树算法.可以用PRIM算法....你简单看看。

普里姆(Prim)算法

（1）算法思想 通过每次添加一个新节点加入集合，直到所有点加入停止的最小生成树的算法 。

原理：每次连出该集合到其他所有点的最短边保证生成树的边权总和最小 。

1. 首先随便选一个点加入集合 。

2. 用该点的所有边去刷新到其他点的最短路 。

3. 找出最短路中最短的一条连接（且该点未被加入集合）

4. 用该点去刷新到其他点的最短路 。

5 重复以上操作n-1次 。

6 最小生成树的代价就是连接的所有边的权值之和。

void MiniSpanTree_P( MGraph G, VertexType u ) 。

{

//用普里姆算法从顶点u出发构造网G的最小生成树 。

k = LocateVex ( G, u ); 。

for ( j=0; j<G.vexnum; ++j ) // 辅助数组初始化 。

if (j!=k) 。

closedge[j] = { u, G.arcs[k][j] }; 。

closedge[k].Lowcost = 0; // 初始，U＝{u} 。

for ( i=0; i<G.vexnum; ++i ) 。

{

继续向生成树上添加顶点；

}

k = minimum(closedge); // 求出加入生成树的下一个顶点(k) 。

printf(closedge[k].Adjvex, G.vexs[k]); // 输出生成树上一条边 。

closedge[k].Lowcost = 0; // 第k顶点并入U集 。

for (j=0; j<G.vexnum; ++j) //修改其它顶点的最小边 。

if ( G.arcs[k][j] < closedge[j].Lowcost ) 。

closedge[j] = { G.vexs[k], G.arcs[k][j] }; 。

原文地址：http://www.qianchusai.com/%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91prim%E7%AE%97%E6%B3%95.html