/*PRim算法與Dijkstra算法使用的思想幾乎完全相同，只有在數(shù)組d[]的含義上有所區(qū)別，其中Dijkstra算法的數(shù)組d[]含義為起點(diǎn)s到達(dá)頂點(diǎn)Vi的最短距離，而prim算法的數(shù)組d[]含義為頂點(diǎn)Vi與集合S(已經(jīng)處理過的點(diǎn)的集合)的最短距離,兩者的區(qū)別僅在于最短距離是頂點(diǎn)Vi針對(duì)"起點(diǎn)s"還是"集合S"。prim(保持樹形keep tree，其中有個(gè)p可以聯(lián)想記憶)算法偽代碼如下：//G為圖，一般設(shè)成全局變量；數(shù)組d為頂點(diǎn)與集合S的最短距離Prim(G,d[]){	初始化；	for(循環(huán)n次)	{		u = 使d[u]最小的還未被訪問的頂點(diǎn)標(biāo)號(hào)；		記u已被訪問；		for(從u出發(fā)能到達(dá)的所有頂點(diǎn)v)		{			if(v未被訪問&&以u(píng)為中介點(diǎn)使得v與集合S的最短距離d[v]更優(yōu))			{				將G[u][v]賦值給v與集合S的最短距離d[v]；			}		}	}}再次說明：Dijkstra算法和prim算法實(shí)際上是相同的思路，只不過是數(shù)組d[]的含義不同罷了*///prim算法實(shí)現(xiàn)代碼#include<vector>#include<algorithm>using namespace std;const int MAXV = 1000;//最大頂點(diǎn)數(shù)const int INF = 1000000000;//設(shè)INF為一個(gè)很大的數(shù)//鄰接矩陣版int n, G[MAXV][MAXV];//n為頂點(diǎn)數(shù)，MAXV為最大頂點(diǎn)數(shù)int d[MAXV];//頂點(diǎn)與集合S的最短距離bool vis[MAXV] = { false };//標(biāo)記數(shù)組，vis[i]==true表示已訪問。初值均為falseint prim()//默認(rèn)0號(hào)為初始點(diǎn)，函數(shù)返回最小生成樹的邊權(quán)之和{	fill(d, d + MAXV, INF);//fill函數(shù)將整個(gè)d數(shù)組賦為INF(慎用memset)	d[0] = 0;//只有0號(hào)頂點(diǎn)到集合S的距離為0，其余全為INF	int ans = 0;//存放最小生成樹的邊權(quán)之和	for (int i = 0; i < n; i++)//循環(huán)n次	{		int u = -1, MIN = INF;//u使d[u]最小，MIN存放該最小的d[u]		for (int j = 0; j < n; j++)		{			if (vis[j] == false && d[j] < MIN)			{				u = j;				MIN = d[j];			}		}		//找不到小于INF的d[u],則剩下的頂點(diǎn)和集合S不連通		if (u == -1)return -1;		vis[u] = true;//標(biāo)記u為已訪問		ans += d[u];//將與集合S距離最小的邊加入最小生成樹		for (int v = 0; v < n; v++)		{			//v未被訪問&&u能到達(dá)v&&以u(píng)為中介點(diǎn)可以使v離集合S更近			if (vis[v] == false && G[u][v] != INF&&G[u][v] < d[v])			{				d[v] = G[u][v];//將G[u][v]賦值給d[v]			}		}	}	return ans;//返回最小生成樹的邊權(quán)之和}//鄰接表版struct Node{	int v, dis;//v為邊的目標(biāo)頂點(diǎn)，dis為邊權(quán)};vector<Node> Adj[MAXV];//圖G，Adj[u]存放從頂點(diǎn)u出發(fā)可以到達(dá)的所有頂點(diǎn)int n;//n為頂點(diǎn)數(shù)，圖G使用鄰接表實(shí)現(xiàn)，MAXV為最大頂點(diǎn)數(shù)int d[MAXV];//頂點(diǎn)與集合S的最短距離bool vis[MAXV] = { false };//標(biāo)記數(shù)組,vis[i]==true表示已訪問。初值均為falseint prim()//默認(rèn)0號(hào)為初始點(diǎn)，函數(shù)返回最小生成樹的邊權(quán)之和{	fill(d, d + MAXV, INF);//fill函數(shù)將整個(gè)d數(shù)組賦為INF(慎用memset)	d[0] = 0;//只有0號(hào)頂點(diǎn)到集合S的距離為0，其余全為INF	int ans = 0;//存放最小生成樹的邊權(quán)之和	for (int i = 0; i < n; i++)//循環(huán)n次	{		int u = -1, MIN = INF;//u使d[u]最小，MIN存放該最小的d[u]		for (int j = 0; j < n; j++)//找到未訪問的頂點(diǎn)中d[]最小的		{			if (vis[j] == false && d[j] < MIN)			{				u = j;				MIN = d[j];			}		}		if (u == -1)return -1;		vis[u] - true;//標(biāo)記u為已訪問		ans += d[u];//將與集合S距離最小的邊加入最小生成樹		//只有下面這個(gè)for與鄰接矩陣的寫法不同		for (int j = 0; j < Adj[u].size(); j++)		{			int v = Adj[u][j].v;//通過鄰接表直接獲得u能到達(dá)的頂點(diǎn)v			if (vis[v] == false && Adj[u][j].dis < d[v])			{				//如果v未被訪問&&以u(píng)為中介點(diǎn)可以使v離集合S更近				d[v] = Adj[u][j].dis;//將Adj[u][j].dis賦值給d[v]			}		}	}	return ans;//返回最小生成樹的邊權(quán)之和}