今天就跟大家聊聊有關(guān)Prim算法原理是什么以及完整C代碼的實現(xiàn)，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

創(chuàng)新互聯(lián)致力于互聯(lián)網(wǎng)網(wǎng)站建設(shè)與網(wǎng)站營銷，提供成都網(wǎng)站設(shè)計、做網(wǎng)站、網(wǎng)站開發(fā)、seo優(yōu)化、網(wǎng)站排名、互聯(lián)網(wǎng)營銷、成都小程序開發(fā)、公眾號商城、等建站開發(fā)，創(chuàng)新互聯(lián)網(wǎng)站建設(shè)策劃專家，為不同類型的客戶提供良好的互聯(lián)網(wǎng)應(yīng)用定制解決方案，幫助客戶在新的全球化互聯(lián)網(wǎng)環(huán)境中保持優(yōu)勢。

Prim算法

涉及到的幾個基礎(chǔ)知識

• 生成樹： 一個連通圖的生成樹是它的極小連通子圖，在n個頂點的情形下，有n-1條邊。生成樹是對連通圖而言的，是連通圖的極小連通子圖，包含途中所有頂點，有且僅有n-1條邊。非連通圖的生成樹則組成一個聲稱森林；若圖中有n個頂點，m個連通分量，則生成森林中有n-m條邊。

• 圖的遍歷： 和樹的遍歷相似，若從圖中某頂點出發(fā)，訪問遍途中每個頂點，且每個頂點僅訪問一次，此過程稱為圖的遍歷。圖的遍歷算法是求解圖的連通性問題、拓撲排序和求關(guān)鍵路徑等算法的基礎(chǔ)。圖的常用遍歷順序有兩種：深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS），對每種搜索順序，訪問各頂點的順序也不是唯一的。

• 在一個無向連通圖G中，其所有頂點和遍歷該圖經(jīng)過的所有邊所構(gòu)成的子圖G'，稱作圖G的生成樹。一個圖可以有多個生成樹，從不同的頂點除法，采用不同的遍歷順序，遍歷時所經(jīng)過的邊也就不同。

• 最小生成樹：在圖論中，常常將樹定義為一個無回路連通圖。對于一個帶權(quán)的無向連通圖，其每個生成樹所有邊上的權(quán)值之和可能不同，我們把所有邊上權(quán)值之和最小的生成樹成為圖的最小生成樹（MST）。

• MST性質(zhì)：MST性質(zhì)：假設(shè)G＝(V,E)是一個連通網(wǎng)，U是頂點V的一個非空子集。若(u,v)是一條具有最小權(quán)值的邊，其中u∈U，v∈V－U，則必存在一棵包含邊(u,v)的最小生成樹。

Prim算法

• 基本思想：假設(shè)G＝(V，E)是連通的，TE是G上最小生成樹中邊的集合。算法從U＝{u0}（u0∈V）、TE＝{}開始。重復(fù)執(zhí)行下列操作：

• 在所有u∈U，v∈V－U的邊(u，v)∈E中找一條權(quán)值最小的邊(u0,v0)并入集合TE中，同時v0并入U，直到V＝U為止。
  此時，TE中必有n-1條邊，T=(V，TE)為G的最小生成樹。

• Prim算法的核心:始終保持TE中的邊集構(gòu)成一棵生成樹。

• Prim算法舉例：

采用的是頂點數(shù)為6的無向連通圖：

設(shè)集合V={A,B,C,D,E,F}，即所有頂點的集合。

集合U為最小生成樹的結(jié)點。

按照Prim算法：

1. 將A加入U，此時，U={ A }，V-U={ B，C，D，E}；

2. 與A鄰接的頂點有B，C，D。（A，B）、（A，C）、（A，D），權(quán)值分別為6、1、5，因而選定（A，C）為最小生成樹的一條邊；

3. 將上一步選定的在V-U中的頂點C加入U，此時，U={A，C}， V-U={ B，D，E，F(xiàn)}；

4. V-U中與U中頂點組成的邊有（A，B）、（A，D）、（C，B）、（C，D）、（C，E）、（C，F(xiàn)），權(quán)值分別為6、5、5、5、6、4，因而選定（C，F(xiàn)）為最小生成樹的一條邊；

5. 將F加入U中，此時U={ A，C，F(xiàn)} ， V-U={ B， D，E}；

6. V-U中與U中頂點組成的邊有（A，B）、（A，D）、（C，B）、（C，D）、（C，E）、（F，D）、（F，E），權(quán)值分別為6、5、5、5、6、2、6，選定（F，D）為最小生成樹的一條邊；

7. 將D加入U中，此時，U={ A，C，F(xiàn)，D}， V-U={ B，E}；

8. V-U中與U中頂點組成的邊有（A，B）、（C，B）、（C，E）、（F，E），權(quán)值分別為6、5、6、6，選定（C，B）為最小生成樹的一條邊。

9. 將B加入U中，此時U= {A，C，F(xiàn) ，D，B }, V -U={E };

10. V-U中與U中頂點組成的邊有（B，E）、（C，E）、（F，E），權(quán)值分別為3、6、6，選定（B，E）為最小生成樹的一條邊。

11. 將E加入U中，此時U={A ，C，F(xiàn)，D，B，E}，完成MST的生成。

其生成過程圖示如下：

1.  

         

2. 
   

3. 
   

4. 
   

5. 
              

Prim算法C代碼

難點是prim函數(shù)中的兩個輔助數(shù)組的具體含義：lowcost數(shù)組，顧名思義，最小代價。也就是 lowcost[k] 保存著V-U中編號為k的頂點到U中所有頂點的最小權(quán)值。closest數(shù)組，顧名思義，距離最近。 也就是 closest[k] 保存著U中到V-U中編號為K的頂點權(quán)值最小的頂點的編號。這兩個數(shù)組的元素是隨著頂點不斷加入U集合而動態(tài)變化的。程序中采用鄰接矩陣法創(chuàng)建圖。

/* 求最小生成樹的prim算法 */

#include <stdio.h>
#include <string.h>

#define MaxSize 20
#define MAX 10000

typedef char VertexType;

//定義圖 的鄰接矩陣表示法結(jié)構(gòu)
typedef struct Graph {
	VertexType ver[MaxSize+1];
	int edg[MaxSize][MaxSize];
}Graph;

//鄰接矩陣法圖的生成函數(shù)
void CreateGraph( Graph *g )
{
	int i = 0;
	int j = 0;
	int VertexNum;
	VertexType Ver;

	printf("請輸入圖的頂點:\n");
	while( '\n' != (Ver=getchar()) )
		g->ver[i++] = Ver;
	g->ver[i] = '\0';

	VertexNum = strlen(g->ver);
	printf("請輸入相應(yīng)的的鄰接矩陣:\n");
	for( i=0; i<VertexNum; i++ )
		for( j=0; j<VertexNum; j++ )
			scanf("%d", &g->edg[i][j]);
}

//打印圖的結(jié)點標識符和鄰接矩陣
void PrintGraph( Graph g )
{
	int i, j;
	int VertexNum = strlen(g.ver);
	printf("圖的頂點為:\n");
	for( i=0; i<VertexNum; i++ )
		printf("%c ", g.ver[i]);
	printf("\n");

	printf("圖的鄰接矩陣為:\n");
	for( i=0; i<VertexNum; i++ ) {
		for( j=0; j<VertexNum; j++ )
			printf("%d ", g.edg[i][j]);
		printf("\n");
	}
}

//求圖的頂點數(shù)
int CalVerNum( Graph g )
{
	return strlen(g.ver);
}

//將不鄰接的頂點之間的權(quán)值設(shè)置為MAX
void SetWeight( Graph *g )
{
	for( int i=0; i<CalVerNum(*g); i++ )
		for( int j=0; j<CalVerNum(*g); j++ )
			if( 0 == g->edg[i][j] )
				g->edg[i][j] = MAX;
}

//運用prim算法求最小生成樹
void prim( Graph g, int VerNum, int *parent )
{
	int i, j, k;
	int lowcost[MaxSize];
	int closest[MaxSize], used[MaxSize];
	int min;

	for( i=0; i<VerNum; i++ ) {			//對輔助數(shù)組lowcost和closest進行初始化
		lowcost[i] = g.edg[0][i];
		closest[i] = 0;
		used[i] = 0;					//used[i] == 0 表示i頂點在U中，反之，在V-U中。
		parent[i] = -1;
	}

	used[0] = 1;						//第一步將編號為0的頂點放入U中，也可以是其他頂點

	for( i=0; i<VerNum-1; i++ ) {
		j = 0;
		min = MAX;

		for( k=1; k<VerNum; k++ )		//找到V-U中的與U中頂點組成的最小權(quán)值的邊的頂點編號
			if( (0==used[k]) && (lowcost[k]<min) ) {
				min = lowcost[k];
				j = k;
			}

		parent[j] = closest[j];

		used[j] = 1;					//將j頂點加入U中

		for( k=0; k<VerNum; k++ )		//由于j頂點加入U中，更新lowcost和closest數(shù)組中的元素，檢測V-U中的頂點到j(luò)頂點的權(quán)值是否比j加入U之前的lowcost數(shù)組的元素小
			if( (0==used[k]) && (g.edg[k][j]<lowcost[k]) ) {
				lowcost[k] = g.edg[k][j];
				closest[k] = j;			//closest數(shù)組保存的是U中到V-U中最小權(quán)值的頂點編號
			}
	}
}

//打印最小生成樹的邊和MST的權(quán)值
void PrintMST( Graph g, int *parent )
{
	int VerNum = CalVerNum( g );
	int weight = 0;
	printf("MST的邊為:\n");
	for( int i=1; i<VerNum; i++ ) {		 //VerNum-1條邊
		printf("%c--%c\n", g.ver[parent[i]], g.ver[i] );
		weight+=g.edg[parent[i]][i];
	}
	printf("MST的權(quán)值為:%d\n", weight);
}


int main()
{
	Graph g;
	int parent[20];

	CreateGraph ( &g );
	PrintGraph( g );
	
	SetWeight( &g );

	prim( g, CalVerNum(g), parent );
	PrintMST( g, parent );

	return 0;
}

測試結(jié)果：數(shù)據(jù)即為前面所講的圖。

看完上述內(nèi)容，你們對Prim算法原理是什么以及完整C代碼的實現(xiàn)有進一步的了解嗎？如果還想了解更多知識或者相關(guān)內(nèi)容，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝大家的支持。

網(wǎng)站標題：Prim算法原理是什么以及完整C代碼的實現(xiàn)
轉(zhuǎn)載源于：http://sd-ha.com/article0/jossio.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供云服務(wù)器、網(wǎng)站制作、App設(shè)計、企業(yè)網(wǎng)站制作、網(wǎng)站營銷、Google

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)