Prim算法以及優(yōu)化實(shí)現(xiàn)

最小生成樹(shù)（Minimum Spanning Trees），簡(jiǎn)稱(chēng)MST。是圖論中一個(gè)非常重要的概念。解決這個(gè)問(wèn)題有兩種算法，今天暫且先來(lái)討論一下Prim Algorithm。不做特別說(shuō)明，討論的都是無(wú)向圖。

首先介紹一下最小生成樹(shù)的概念，我們知道，圖可以這樣定義 G=(V,E) ，其中 G 表示圖，V 表示頂點(diǎn)集合，E 表示邊集合。最小生成樹(shù)是這樣一棵樹(shù)，它滿(mǎn)足：

通俗地講，就是使得圖GG連通時(shí)，所選取的邊的長(zhǎng)度的和最小。

如上圖，加粗的路徑就是在最小生成樹(shù)上的路徑。

算法講解：

現(xiàn)在，我們開(kāi)始討論P(yáng)rim Algorithm。這個(gè)算法可以分為下面幾個(gè)步驟：

將頂點(diǎn)集 V 分成兩個(gè)集合 A 和 B，其中集合 A 表示目前已經(jīng)在MST中的頂點(diǎn)，而集合 B 則表示目前不在 MST 中的頂點(diǎn)。

尋找與集合 A 連通的最短的邊 (u,v)，將這條邊加入最小生成樹(shù)中。（此時(shí),與(u,v) 相連的頂點(diǎn)，不妨設(shè)為 Bi，也應(yīng)加入集合 A 中）重復(fù)第二步，直至集合 B 為空集。

算法的大體思想就是這樣了。為了方便理解，我們先來(lái)看一下下面一張圖片：

對(duì)照上面的圖片，想必對(duì)于Prim Algorithm也有了一定的理解。

下面我們來(lái)設(shè)計(jì)算法，顯然，我們需要遍歷集合 A 中所有頂點(diǎn)及與之相連的邊，取連接到集合B的權(quán)值最小的邊，加入最小生成樹(shù)。這樣一來(lái)，復(fù)雜度將達(dá)到 O(n3)。

我們可以對(duì)這個(gè)想法進(jìn)行優(yōu)化。我們維護(hù)一 pCost[i] 數(shù)組，用來(lái)表示從集合A到與之相鄰的節(jié)點(diǎn)的最小費(fèi)用。這樣，我們只要每次取這個(gè)數(shù)組中的最小值，把它在集合B中所對(duì)應(yīng)的結(jié)點(diǎn)Vi加入到集合A中。

每次加入結(jié)束以后，都要更新pCost[i]數(shù)組。即枚舉所有與結(jié)點(diǎn)Vi相連的邊，判斷是否比pCost[i]數(shù)組中的最小費(fèi)用小，如果比它小，則更新。這樣可以將算法優(yōu)化到O(n2)。

代碼如下：

#include

#include

#include

using namespace std;

const int MAX = 1024;

const int INF = 2147483647;// 設(shè)置最大權(quán)值

int N, M;

vector > pMap[MAX];// 鄰接表

void Prim();

int main()

{

cin >> N >> M;

for(int i = 1; i <= M; i++)

{

int u, v, w;

cin >> u >> v >> w;

pMap[u].push_back(make_pair(v, w));

pMap[v].push_back(make_pair(u, w));

}

Prim();

return 0;

}

void Prim()

{

int nCost = 0;

vector pMST;// 儲(chǔ)存MST的結(jié)點(diǎn)

int pCost[MAX];// 儲(chǔ)存與集合A相鄰的頂點(diǎn)的最小權(quán)值，0表示該結(jié)點(diǎn)已經(jīng)在MST中

pMST.push_back(1);// 將結(jié)點(diǎn)1加入MST

pCost[1] = 0;

for(int i = 2; i <= N; i++)// 初始化，切記要將除1以外的都置為INF

{ pCost[i] = INF; }

for(int i = 0; i < pMap[1].size(); i++)// 處理與結(jié)點(diǎn)1相連的頂點(diǎn)

{ pCost[pMap[1][i].first] = pMap[1][i].second; }

for(int i = 1; i <= N - 1; i++)// 剩余N-1個(gè)頂點(diǎn)，循環(huán)N-1次

{

int nVertex = 0, nWeight = INF;// 用于尋找最短的邊

for(int j = 1; j <= N; j++)

{

if(nWeight > pCost[j] && pCost[j] != 0)

{

nVertex = j;

nWeight = pCost[j];

}

}

pCost[nVertex] = 0;

pMST.push_back(nVertex);// 將節(jié)點(diǎn)nVertex加入MST

nCost += nWeight;// 計(jì)算MST的費(fèi)用

for(int j = 0; j < pMap[nVertex].size(); j++)// 更新pCost數(shù)組

{

if(pCost[pMap[nVertex][j].first] != 0 &&

pCost[pMap[nVertex][j].first] > pMap[nVertex][j].second)

{

pCost[pMap[nVertex][j].first] = pMap[nVertex][j].second;

}

}

}

cout << "MST Cost is " << nCost << endl;

cout << "The vertexs in MST are ";

for(int i = 0; i < pMST.size(); i++)

{ cout << pMST[i] << " "; }?

cout << endl;

}