普里姆演算法輔助數組中各分量的值

㈠ 普里姆演算法的相關信息

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演算法。這些演算法在一個可能的非連通圖中找到最小生成森林；相比之下，普里姆演算法最基本的形式只能在連通圖中找到最小生成樹。然而，為圖中的每個連通分量單獨運行普里姆演算法，也可以用於找到最小生成森林。

就漸近時間復雜度而言，這三種演算法對於稀疏圖來說速度相同，但比其他更復雜的演算法慢。然而，對於足夠密集的圖，普里姆演算法可以在線性時間內運行，滿足或改進其他演算法的時間限制。