普里姆算法c语言

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

为了便于在两个顶点集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)算法，和克鲁斯卡尔算法一样，是用来求加权连通图的最小生成树的算法。

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

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

基本思想：

对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。

从所有uЄU，vЄ(V-U) (V-U表示出去U的所有顶点)的边中选取权值最小的边(u, v)，将顶点v加入集合U中，将边(u, v)加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，这时集合T中包含了最小生成树中的所有边。

❸ 使用普里姆算法求最小生成树.

void minispantree_PRIM(int ad[][5],int n)
{ int i,j,k,p,q,wm;
q=p=n-1;
ad[q][q]=1;
for(k=0;k<(n-1);k++)
{ wm=MAX;
for(i=0;i<n;i++)
if(ad[i][i]==1)
for(j=0;j<岩竖纤n;j++)
if((ad[j][j]==0)&&(ad[i][j]<wm))
{ wm=ad[i][j];
p=i;
q=j;
}
ad[q][q]=1;
printf("%d %d %d\n"纤伍,p+1,q+1,ad[p][q]);
if(p>粗仿q) ad[p][q]=-ad[p][q];
else ad[q][p]=-ad[q][p];
}
}

main()
{
int m=6;
int ad[][5]={0,6,1,5,200,200,
6,0,5,200,3,200,
1,5,0,5,6,4,
5,200,5,0,200,2,
200,3,6,200,0,6,
200,200,4,2,6,0};
minispantree_PRIM(ad[5][5],m);

}

❹ 急！数据结构最小生成树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;
}
}
}

❺ 用普里姆算法求最小生成树（C++）

求最小生成树的谱里姆算法
#include <iostream>
using namespace std;

const int n=6;
const int e=10;
class edgeset
{public :
int front;
int end;
int weight;};

class tree
{public :
int s[n+1][n+1];
edgeset ct[n+1];

void prim(tree &t)
{
int i,j,k,min,t1,m,w;
for(i=1;i<n;i++)
{t.ct[i].front=1;
t.ct[i].end=i+1;
t.ct[i].weight=t.s[1][i+1];}

for(k=2;k<=n;k++)
{min=32767;
m=k-1;

for(j=k-1;j<n;j++)
if(t.ct[j].weight<min)
{min=t.ct[j].weight;
m=j;}
edgeset temp=t.ct[k-1];
t.ct[k-1]=t.ct[m];
t.ct[m]=temp;
j=t.ct[k-1].end;
for(i=k;i<n;i++)
{t1=t.ct[i].end;
w=t.s[j][t1];
if(w<t.ct[i].weight)
{t.ct[i].weight=w;
t.ct[i].front=j;}}}}
};

void main ()
{int j,w;tree t;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j)t.s[i][j]=0;
else t.s[i][j]=32767;

for(int k=1;k<=e;k++)
{cout<<"输入一条边及边上的权值 ";
cin>>i>>j>>w;
cout<<endl;
t.s[i][j]=w;
t.s[j][i]=w;}

t.prim(t);
for(i=1;i<n;i++)
{cout<<t.ct[i].front<<" "<<t.ct[i].end<<" "<<t.ct[i].weight<<endl;}
}
我们的实验上机做了的
运行结果
输入一条边及边上的权值 1 2 6

输入一条边及边上的权值 1 3 1

输入一条边及边上的权值 1 4 6

输入一条边及边上的权值 2 3 5

输入一条边及边上的权值 2 5 3

输入一条边及边上的权值 3 4 7

输入一条边及边上的权值 3 5 5

输入一条边及边上的权值 3 6 4

输入一条边及边上的权值 4 6 2

输入一条边及边上的权值 5 6 6

1 3 1
3 6 4
6 4 2
3 5 5
5 2 3
Press any key to continue
你有的图不一样就该顶点和边就是
const int n=6;
const int e=10;

❻ 普里姆算法(Prime)

普利姆(Prim)算法求最小生成树，也就是在包含 n 个顶点的连通图中，找出只有(n-1)条边包含所有 n 个顶点的连通子图，也就是所谓的极小连通子图

普利坦闹仔姆的算法如下:

1. 有七个站点 A,B,C,D,E,F,G，现在需要修线路把弯哗七个站点联通

2. 各个站点的距离用边线表示(权)，比如 A->C 为7公里

问： 如让汪何修线路使各个站点都能联通， 同时修的线路里程最短？

❼ 普里姆算法

你要先明白prim算法的原理，明白原理后看下面的程序要点：

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