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