普里姆算法辅助数组中各分量的值

㈠ 普里姆算法的相关信息

1）算法的基本思想：
普里姆算法的基本思想：普里姆算法是另一种构造最小生成树的算法，它是按逐个将顶点连通的方式来构造最小生成树的。
从连通网络N = { V, E }中的某一顶点u0出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把该边加入到生成树的边集TE中，把它的顶点加入到集合U中。如此重复执行，直到网络中的所有顶点都加入到生成树顶点集合U中为止。
假设G=(V，E)是一个具有n个顶点的带权无向连通图，T(U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则构造G的最小生成树T的步骤如下：
（1）初始状态，TE为空，U={v0}，v0∈V；
（2）在所有u∈U，v∈V-U的边(u，v)∈E中找一条代价最小的边(u′，v′)并入TE，同时将v′并入U；
重复执行步骤（2）n-1次，直到U=V为止。
在普里姆算法中，为了便于在集合U和(V-U)之间选取权值最小的边，需要设置两个辅助数组closest和lowcost，分别用于存放顶点的序号和边的权值。对于每一个顶点v∈V-U，closest[v]为U中距离v最近的一个邻接点，即边(v，closest[v])是在所有与顶点v相邻、且其另一顶点j∈U的边中具有最小权值的边，其最小权值为lowcost[v]，即lowcost[v]=cost[v][closest[v]]，采用邻接表作为存储结构：
设置一个辅助数组closedge[]：
lowcost域存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值；
adjvex域记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)。
应用Prim算法构造最小生成树的过程:

㈡ 什么事普里姆算法

是图的最小生成树的一种构造算法。 假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，TV 是 WN 上最小生成树中顶点的集合，TE 是最小生成树中边的集合。显然，在算法执行结束时，TV=V，而 TE 是 E 的一个子集。在算法开始执行时，TE 为空集，TV 中只有一个顶点，因此，按普里姆算法构造最小生成树的过程为：在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有 n-1条边为止。 补充：closedge的类型： struct { VertexData Adjvex; int Lowcost; }closedge[MAX_VERTEX_NUM]; //求最小生成树的辅助数组 void MiniSpanTree_P( MGraph G, VertexType u ) { //用普里姆算法从顶点u出发构造网G的最小生成树 k = LocateVex ( G, u ); closedge[k].Lowcost = 0; // 初始，U＝{u} for ( j=0; j<G.vexnum; ++j ) // 辅助数组初始化 if (j!=k) closedge[j] = { u, G.arcs[k][j] }; 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] }; }

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

为了便于在两个顶点集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无关，所以普里姆算法特别适合于稠密图求最小生成树。

㈣ 4.用Prim算法求下图的最小生成树, 若从顶点0出发，请将算法中的两个辅助数组的变化过程填入下表。

不好意思吖按照图弄那两个中间数组太久了。。。实现方法也有不同。我跟您说说我学的通用实现方法吧！
点集合：A，代表已经扩展到的点。
边集合B：代表待考虑的边，一开始为空。
一开始从任意点出发，如0.此时集合A中只有点0。将和A相邻的所有边加入到B中。
从B中选最短的一条边e。e的一个端点必不在A中，则将它加入A中。将不在A中的那个点的所有边加入B中，在B中删除边e
这样B中减少了一条边（先前的边中最短的）。在A中增加了一个新点，并且这个点的相关边加入了B中。而B中减少的这条边就是最小生成树的一条边。
这样一来，调用以上两个步骤N-1次（有N个点），则可以得到n-1条线段，就是其最小生成树。
如果不是很懂可以Q我，我会用通俗的语言解释的^^
QQ:328880142

㈤ 最小生成树算法，急！

已编译确认，编译环境vs2005/dev-cpp
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<conio.h>
#include<math.h> /* floor(),ceil(),abs() */

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int VRType;
typedef char InfoType;
#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */
#define MAX_INFO 20 /* 相关信息字符串的最大长度+1 */
typedef char VertexType[MAX_NAME];
#define INFINITY INT_MAX /* 用整型最大值代替∞ */
#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct
{
VRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； */
/* 对带权图，c则为权值类型 */
InfoType *info; /* 该弧相关信息的指针(可无) */
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量 */
AdjMatrix arcs; /* 邻接矩阵 */
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
GraphKind kind; /* 图的种类标志 */
}MGraph;
/*图的数组(邻接矩阵)存储(存储结构由c7-1.h定义)的基本操作*/
int LocateVex(MGraph G,VertexType u)
{ /* 初始条件:图G存在,u和G中顶点有相同特征 */
/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vexs[i])==0)
return i;
return -1;
}
Status CreateAN(MGraph *G)
{ /* 采用数组(邻接矩阵)表示法,构造无向网G。*/
int i,j,k,w,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i) /* 初始化邻接矩阵 */
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=INFINITY; /* 网 */
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回车符 */
i=LocateVex(*G,va);
j=LocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w; /* 无向 */
if(IncInfo)
{
printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);
gets(s);
w=strlen(s);
if(w)
{
info=(char*)malloc((w+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=info; /* 无向 */
}
}
}
(*G).kind=AN;
return OK;
}
typedef struct
{ /* 记录从顶点集U到V-U的代价最小的边的辅助数组定义 */
VertexType adjvex;
VRType lowcost;
}minside[MAX_VERTEX_NUM];
int minimum(minside SZ,MGraph G)
{ /* 求closedge.lowcost的最小正值 */
int i=0,j,k,min;
while(!SZ[i].lowcost)
i++;
min=SZ[i].lowcost; /* 第一个不为0的值 */
k=i;
for(j=i+1;j<G.vexnum;j++)
if(SZ[j].lowcost>0)
if(min>SZ[j].lowcost)
{
min=SZ[j].lowcost;
k=j;
}
return k;
}
void MiniSpanTree_PRIM(MGraph G,VertexType u)
{ /* 用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边*/
int i,j,k;
minside closedge;
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j) /* 辅助数组初始化 */
{
if(j!=k)
{
strcpy(closedge[j].adjvex,u);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
closedge[k].lowcost=0; /* 初始,U={u} */
printf("最小代价生成树的各条边为:\n");
for(i=1;i<G.vexnum;++i)
{ /* 选择其余G.vexnum-1个顶点 */
k=minimum(closedge,G); /* 求出T的下一个结点：第K顶点 */
printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]); /* 输出生成树的边 */
closedge[k].lowcost=0; /* 第K顶点并入U集 */
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j].adj<closedge[j].lowcost)
{ /* 新顶点并入U集后重新选择最小边 */
strcpy(closedge[j].adjvex,G.vexs[k]);
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}

int main()
{
MGraph G;
CreateAN(&G);
MiniSpanTree_PRIM(G,G.vexs[0]);
getch();
return 0;
}

㈥ 求救~！C语言 最小生成树问题

普里姆算法描述：
假设 N＝(V，E)是一个带权图，TE是N上最小生成树中边的集合。算法从U＝{u0}(u0∈V)，TE＝{}开始，重复执行下述操作：在所有u∈U，v∈V-U的边(u，v) ∈E中找一条权值最小的边(u，v)并入集合TE，同时v并入U，直至U＝V为止。此时TE中必有n-1边，则T＝(V，{TE})为N的最小生成树。
为实现这个算法需附设一个辅助数组 closedge，以记录从U到V-U具有最小代价的边。对每个顶点vi∈V-U，在辅助数组中存在一个相应分量closedge[I-1]，它包括两个域，其中lowcost存储该边上的权：显然， closedge[I-1]．Lowcost＝Min{cost(u，vi)|uEU} vex域存储该边依附的在U中的顶点。

㈦ 普里姆算法

用于得到最小生成树

时间复杂度：o(n2)

概念梳理：

算法需要：
所有边的长度（邻接矩阵即可）
数组dist[]，用来存放当前最小生成树到其他没有被纳入最小生成树的点的最短距离
数组set[]，用来存放点是否被纳入最小生成树中

描述下步骤：
初始化：
我们以0点作为起点，最开始dist初始化为从0点到其他点的距离，譬如dist[1]就表示起点0到点1的距离。
set[i]置1表示i点被纳入最小生成树中了，所以初始化时，set[0]置1，其他位置0。
用sum来记录最小生成树的权值。
循环：
可以推知，在n个点的情况下，经过初始化以后，我们还需要执行n-1次才能完成将所有点都纳入最小生成树，所以总的循环为n-1次。
循环内做什么呢？

总结：算法实现很巧妙，理解了就很简单，个人觉得还是需要去用心理解。

㈧ 普里姆算法

可以这么理解：因为最小生成树是包含所有顶点的所以开始lowcost先储存到第一个点的所有值，然后执行下面算法，找到最小值并记录是第几个点，比如说这个点是3，这样有了一条1-3得道路已经确定，现在从3出发找从3出发到其他顶点的路径，如果这个从3出发到达的路径长度比从1出发的短，则更新lowcost，这样使得lowcost保存一直到达该顶点的最短路径。比如1-4是5，3-4是4，则lowcost从原来的5被改为4。

㈨ 普里姆算法

测试结果:

610
123456
016
021
035
125
143
235
246
254
352
456
1---31
3---64
6---42
3---25
2---53


//图最小生成树Prim算法

#include"stdio.h"
#include"stdlib.h"

#defineMAXVEX200
#defineINFINITY65535

typedefstruct
{
charvexs[MAXVEX];//顶点
	intarc[MAXVEX][MAXVEX];//边的权值
	intnumVertexes;//顶点总数
	intnumEdges;//边的总数
}MGraph;

voidCreateMGraph(MGraph*G)/*构件图*/
{
charstr[200];
intbeginVert,endVert,weight;
	inti,j;

//输入顶点总数,边的总数
	scanf("%d%d",&i,&j);
	G->numVertexes=i;
	G->numEdges=j;

//输入顶点符号
	scanf("%s",str);

	for(i=0;i<G->numVertexes;i++)
{
G->vexs[i]=str[i];
}

	for(i=0;i<G->numVertexes;i++)/*初始化图*/
	{
		for(j=0;j<G->numVertexes;j++)
		{
			if(i==j)
{
G->arc[i][j]=0;
}
			else
{
G->arc[i][j]=G->arc[j][i]=INFINITY;
}
		}
	}
//输入所有边的权值
	for(i=0;i<G->numEdges;i++)
{
scanf("%d%d%d",&beginVert,&endVert,&weight);
G->arc[beginVert][endVert]=weight;
}

	for(i=0;i<G->numVertexes;i++)
	{
		for(j=i;j<G->numVertexes;j++)
		{
			G->arc[j][i]=G->arc[i][j];
		}
	}
}

/*Prim算法生成最小生成树*/
voidMiniSpanTree_Prim(MGraphG)
{
	intmin,i,j,k;
	intadjvex[MAXVEX];		/*保存相关顶点下标*/
	intlowcost[MAXVEX];	/*保存相关顶点间边的权值*/
	charbeginVert,endVert;

	lowcost[0]=0;/*初始化第一个权值为0，即v0加入生成树*/
/*lowcost的值为0，在这里就是此下标的顶点已经加入生成树*/
	adjvex[0]=0;			/*初始化第一个顶点下标为0*/
	for(i=1;i<G.numVertexes;i++)	/*循环除下标为0外的全部顶点*/
	{
		lowcost[i]=G.arc[0][i];	/*将v0顶点与之有边的权值存入数组*/
		adjvex[i]=0;					/*初始化都为v0的下标*/
	}
	for(i=1;i<G.numVertexes;i++)
	{
		min=INFINITY;	/*初始化最小权值为∞，*/
						/*通常设置为不可能的大数字如32767、65535等*/
		j=1;k=0;
		while(j<G.numVertexes)	/*循环全部顶点*/
		{
			if(lowcost[j]!=0&&lowcost[j]<min)/*如果权值不为0且权值小于min*/
			{
				min=lowcost[j];	/*则让当前权值成为最小值*/
				k=j;			/*将当前最小值的下标存入k*/
			}
			j++;
		}

		beginVert=G.vexs[adjvex[k]];
		endVert=G.vexs[k];
		//打印当前顶点边中权值最小的边
		printf("%c---%c%d
",beginVert,endVert,min);

		lowcost[k]=0;/*将当前顶点的权值设置为0,表示此顶点已经完成任务*/
		for(j=1;j<G.numVertexes;j++)	/*循环所有顶点*/
		{
			if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j])
			{//如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值
				lowcost[j]=G.arc[k][j];//将较小的权值存入lowcost相应位置
				adjvex[j]=k;			//将下标为k的顶点存入adjvex
			}
		}
	}
}

intmain(void)
{
	MGraphG;
	CreateMGraph(&G);
	MiniSpanTree_Prim(G);

	return0;

}

㈩ 普里姆算法是什么

在计算机科学中，普里姆(也称为Jarník's)算法是一种贪婪算法，它为加权的无向图找到一个最小生成树 。

相关简介：

这意味着它找到边的一个子集，能够形成了一个包括所有顶点的树，其中在树中所有边的权重总和最小。该算法通过从任意起始顶点开始一次给树增加一个顶点来操作，在每个步骤中添加从树到另一个顶点的花费最小的可能的连接。

该算法由捷克数学家沃伊茨奇·贾尼克于1930年开发后，后来在1957年被计算机科学家罗伯特·普里姆，以及在1959年被艾兹赫尔·戴克斯特拉重新发现和重新出版。因此，它有时也被称为Jarník算法,普里姆-jarník算法。普里姆-迪克斯特拉算法或者DJP算法。

这个问题的其他众所周知的算法包括克鲁斯卡尔算法和 Borvka's算法。这些算法在一个可能的非连通图中找到最小生成森林；相比之下，普里姆算法最基本的形式只能在连通图中找到最小生成树。然而，为图中的每个连通分量单独运行普里姆算法，也可以用于找到最小生成森林。

就渐近时间复杂度而言，这三种算法对于稀疏图来说速度相同，但比其他更复杂的算法慢。然而，对于足够密集的图，普里姆算法可以在线性时间内运行，满足或改进其他算法的时间限制。