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算法的原理，明白原理后看下面的程序要点：

1.程序实现的时候将点分成两部分，加入集合的和没有加入集合的；
2.每次从没有加入集合中找点；
3.对所有没有加入到集合中的点中，找一个边权最小的；
4.将边权最小的点加入集合中，并且修改和加入点相连的没有加入的点的权，重复第2步，知道所有的点都加入到集合中；

㈢ Python中prim算法或kruscal算法的实现

kruskal:
#include "stdio.h"
#include "stdlib.h"
#include "iostream"
using namespace std;
#define MAXE 100 //MAXE为最大的边数
struct edges
{
int bv,tv,w; //边集类型,存储一条边的起始顶点bv、终止顶点tv和权w
}edges;
typedef struct edges edgeset[MAXE];
//寻找v所在的连通集
int seeks(int set[],int v)
{
int i=v;
while (set[i]>0)

i=set[i];
return i;
}
void kruskal(edgeset ge,int n,int e)
{
int set[MAXE],v1,v2,i,j;
for(i=1;i<=n;i++)
set[i]=0;
i=1; //i表示待获取的生成树中的边数,初值为1
j=1; //j表示ge中的下标,初值为1
while(j<n&&i<=e)//按边权递增顺序,逐边检查该边是否应加入到生成树中
{
v1=seeks(set,ge[i].bv); //确定顶点v所在的连通集
v2=seeks(set,ge[i].tv);
cout<<ge[i].bv<<":"<<v1<<", "<<ge[i].tv<<":"<<v2<<endl;
if(v1!=v2) //当v1,v2不在同一顶点集合,确定该边应当选入生成树
{
cout<<"("<<ge[i].bv<<", "<<ge[i].tv<<") "<<ge[i].w<<endl;
set[v1]=v2;
j++;
}
i++;
}
}
int main()
{
edgeset ee;
int n,e; //n是图的结点数,e是图的边数
n=6;
e=3;
for(int i=1;i<=e;i++)
{
scanf_s("%d",&ee[i].bv);
scanf_s("%d",&ee[i].tv);
scanf_s("%d",&ee[i].w);
}
//ee表示的边集图是按权值从小到大排列的
printf("最小生成树边集及它的权值: \n");
kruskal(ee,n,e);
system("pause");
return 0;
}
prim:

#include "stdio.h"
#include "stdlib.h"
#include "iostream"
using namespace std;
#define N 3
void prim(int c[N][N])
{
//lowcost 为顶点间的最小距离，closest为最小距离上的邻接顶点
//lowcost[i]:与顶点i连通的最小边的权值
//closest[i]:与顶点i连通的邻接顶点
int lowcost[N],closest[N];
int i,j,k,min;

//lowcost,closest初始化
for(i=0;i<N;i++)
{
lowcost[i]=c[0][i];
closest[i]=0;
}
closest[0]=-1;

//寻找U 和 V 之间连接的最短距离的邻接点
for(i=0;i<N;i++)
{
min=32767;
k=0;
//寻找U 和 V 之间连接的最短距离的邻接点
for(j=0;j<N;j++)
{
if((lowcost[j]<min)&&(closest[j]!=-1))
{
min=lowcost[j];
k=j;
}
}
//输出新的邻接顶点，并修改lowcost值
if(k)
{
cout<<"("<<closest[k]<<", "<<k<<") "<<lowcost[k]<<endl;
closest[k]=-1;
for(j=1;j<N;j++)
{
if(closest[j]!=-1)// huo if(!(closest[j]==-1))
{
//修改lowcost值
lowcost[j]=c[k][j];
//修改邻接顶点
closest[j]=k;
}
}
}
}
}

int main()
{
int i,j,a[3][3];
cout<<"请输入二维数组："<<endl;
for(i=0;i<3;i++)

for(j=0;j<3;j++)

cin>>a[i][j];
cout<<"最小树的结构为："<<endl;
prim(a);
int q;
cin>>q;
return 0;
}

㈣ prim算法是什么

prim算法是：图论中的一种算法。

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。

该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

通过邻接矩阵图表示的简易实现中，找到所有最小权边共需O（V）的运行时间。使用简单的二叉堆与邻接表来表示的话，普里姆算法的运行时间则可缩减为O(ElogV)，其中E为连通图的边数，V为顶点数。如果使用较为复杂的斐波那契堆，则可将运行时间进一步缩短为O(E+VlogV)，这在连通图足够密集时（当E满足Ω（VlogV）条件时），可较显着地提高运行速度。

㈤ 对给定的网和起点，实现求解最小生成树的PRIM算法，并给出动态演示。万分火急

最近忙着考试，没时间做图形界面来动态演示部分啦，先给你一个基本的Prim程序吧，希望有所帮助。
/**
* PRIM(简单版) 最小生成树算法 (Minimum Spanning Tree)
* 输入：图g； // 有向图或者无向图
* 输出：(1)最小生成树长sum；
* (2)最小生成树prev。
* 结构: 图g用邻接矩阵表示，最短边长dist用数组表示。
* 算法：Prim算法
* 复杂度：O(|V|^2)
*/
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <functional>
#include <climits>
using namespace std;

int n; // n : 顶点个数
vector<vector<int> > g; // g : 图(graph)(用邻接矩阵(adjacent matrix)表示)
vector<bool> known; // known : 各点是否已经选取
vector<早扰int> dist; // dist : 已选取点集到凳枯未选取点的最小边长
vector<int> prev; // prev : 最小生成树中各点的前一顶点
int s; // s : 起点(start)
int sum; // sum : 最小生成树长

bool Prim() // 贪心算法(Greedy Algorithm)
{
known.assign(n, false);
dist.assign(n, INT_MAX);
prev.resize(n); // 初始化known、dist、prev。
dist[s] = 0; // 初始化起点到自身的路径长为0。
int i;
for (i = 0; i < n; ++i)
{
int min = INT_MAX, v;
for (int i = 0; i <陆粗旦 n; ++i)
if (!known[i] && min > dist[i])
min = dist[i], v = i; // 寻找未知的最短路径长的顶点v，
if (min == INT_MAX) break; // 如果找不到，退出；
known[v] = true; // 如果找到，将顶点v设为已知，
sum += dist[v]; // 调整最小生成树长
for (int w = 0; w < n; ++w) // 遍历所有v指向的顶点w，
if (!known[w] && g[v][w] < INT_MAX && dist[w] > g[v][w])
dist[w] = g[v][w], prev[w] = v; /* 调整顶点w的最短路径长dist和最短路径的前一顶点 prev。 */
}
return i == n; // 如果选取顶点个数为n，成功。
}

int main()
{
n = 7;
g.assign(n, vector<int>(n, INT_MAX));
g[0][1] = g[1][0] = 2; g[0][2] = g[2][0] = 4; g[0][3] = g[3][0] = 1;
g[1][3] = g[3][1] = 3; g[1][4] = g[4][1] = 10;
g[2][3] = g[3][2] = 2; g[2][5] = g[5][2] = 5;
g[3][4] = g[4][3] = 7; g[3][5] = g[5][3] = 8; g[3][6] = g[6][3] = 4;
g[4][6] = g[6][4] = 6;
g[5][6] = g[6][5] = 1;

s = 0; // 起点任选
sum = 0;
if (Prim())
{
cout << sum << endl;
for (int i = 1; i < n; ++i)
if(i != s) cout << prev[i] << "->" << i << endl;
}
else
{
cout << "Some vertex cann't be reached." << endl;
}

system("pause");
return 0;
}

㈥ 普里姆算法的普里姆算法的实现

为了便于在两个顶点集U和V-U之间选择权最小的边，建立了两个辅助数组closest和lowcost，它们记录从U到V-U具有最小权值的边，对于某个j∈V-U，closest[j]存储该边依附的在U中的顶点编号，lowcost[j]存储该边的权值。
为了方便，假设图G采用邻接矩阵g存储，对应的Prim(g,v)算法如下：
void Prim(MatGraph g,int v) //输出求得的最小生树的所有边
{ int lowcost[MAXVEX]; //建立数组lowcost
int closest[MAXVEX]; //建立数组closest
int min,i,j,k;
for (i=0;i<g.n;i++) //给lowcost[]和closest[]置初值
{ lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<g.n;i++) //构造n-1条边
{ min=INF; k=-1;
for (j=0;j<g.n;j++) //在(V-U)中找出离U最近的顶点k
if (lowcost[j]!=0 && lowcost[j]<min)
{ min=lowcost[j];
k=j; //k为最近顶点的编号
}
printf( 边(%d,%d),权值为%d ,closest[k],k,min);
lowcost[k]=0; //标记k已经加入U
for (j=0;j<g.n;j++) //修正数组lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{ lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
}
普里姆算法中有两重for循环，所以时间复杂度为O(n2)，其中n为图的顶点个数。由于与e无关，所以普里姆算法特别适合于稠密图求最小生成树。

㈦ 急！数据结构最小生成树prim算法C语言实现

Kruskal算法：
void
Kruskal(Edge
E[],int
n,int
e)
{
int
i,j,m1,m2,sn1,sn2,k;
int
vset[MAXE];
for
(i=0;i<n;i++)
vset[i]=i;
//初始化辅助数组
k=1;
//k表示当前构造最小生成树的第几条边,初值为1
j=0;
//E中边的下标,初值为0
while
(k<n)
//生成的边数小于n时循环
{
m1=E[j].u;m2=E[j].v;
//取一条边的头尾顶点
sn1=vset[m1];sn2=vset[m2];
//分别得到两个顶点所属的集合编号
if
(sn1!=sn2)
//两顶点属于不同的集合,该边是最小生成树的一条边
{
printf("
(%d,%d):%d/n",m1,m2,E[j].w);
k++;
//生成边数增1
for
(i=0;i<n;i++)
//两个集合统一编号
if
(vset[i]==sn2)
//集合编号为sn2的改为sn1
vset[i]=sn1;
}
j++;
//扫描下一条边
}
}
Prim算法：
void
prim(MGraph
g,int
v)
{
int
lowcost[MAXV],min,n=g.vexnum;
int
closest[MAXV],i,j,k;
for
(i=0;i<n;i++)
//给lowcost[]和closest[]置初值
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for
(i=1;i<n;i++)
//找出n-1个顶点
{
min=INF;
for
(j=0;j<n;j++)
//在(V-U)中找出离U最近的顶点k
if
(lowcost[j]!=0
&&
lowcost[j]<min)
{
min=lowcost[j];k=j;
}
printf("
边(%d,%d)权为:%d/n",closest[k],k,min);
lowcost[k]=0;
//标记k已经加入U
for
(j=0;j<n;j++)
//修改数组lowcost和closest
if
(g.edges[k][j]!=0
&&
g.edges[k][j]<lowcost[j])
{
lowcost[j]=g.edges[k][j];closest[j]=k;
}
}
}