国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

prim算法

2019-11-11 05:16:06
字體:
來源:轉載
供稿:網友
/*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;//返回最小生成樹的邊權之和}
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 武宁县| 龙门县| 灵武市| 德化县| 临高县| 理塘县| 韩城市| 赤壁市| 阿拉尔市| 南木林县| 萍乡市| 浪卡子县| 巨鹿县| 开鲁县| 克拉玛依市| 元朗区| 蒲江县| 垦利县| 商都县| 江油市| 泽州县| 龙陵县| 梨树县| 会理县| 宣汉县| 河东区| 明溪县| 子洲县| 大厂| 阜新| 琼结县| 清镇市| 巴青县| 潼关县| 佛冈县| 莲花县| 北流市| 嘉善县| 陕西省| 卓尼县| 巴林左旗|