Prim算法原理是什么以及完整C代碼的實現

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

Prim算法

涉及到的幾個基礎知識

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

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

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

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

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

Prim算法

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

  
  

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

  
  

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

  
  

• Prim算法舉例：

  
  

采用的是頂點數為6的無向連通圖：

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

集合U為最小生成樹的結點。

按照Prim算法：

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

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

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

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

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

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

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

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

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

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

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

其生成過程圖示如下：

Prim算法C代碼

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

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

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

#define MaxSize 20
#define MAX 10000

typedef char VertexType;

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

//鄰接矩陣法圖的生成函數
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("請輸入相應的的鄰接矩陣:\n");
	for( i=0; i<VertexNum; i++ )
		for( j=0; j<VertexNum; j++ )
			scanf("%d", &g->edg[i][j]);
}

//打印圖的結點標識符和鄰接矩陣
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");
	}
}

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

//將不鄰接的頂點之間的權值設置為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++ ) {			//對輔助數組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中頂點組成的最小權值的邊的頂點編號
			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數組中的元素，檢測V-U中的頂點到j頂點的權值是否比j加入U之前的lowcost數組的元素小
			if( (0==used[k]) && (g.edg[k][j]<lowcost[k]) ) {
				lowcost[k] = g.edg[k][j];
				closest[k] = j;			//closest數組保存的是U中到V-U中最小權值的頂點編號
			}
	}
}

//打印最小生成樹的邊和MST的權值
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的權值為:%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;
}

測試結果：數據即為前面所講的圖。

看完上述內容，你們對Prim算法原理是什么以及完整C代碼的實現有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注億速云行業(yè)資訊頻道，感謝大家的支持。