轉(zhuǎn)自：ivy-end

http://www.ivy-end.com/archives/943

背景

最小生成樹（Minimum Spanning Trees），簡稱MST。是圖論中一個非常重要的概念。解決這個問題有兩種算法，今天暫且先來討論一下Prim Algorithm。不做特別說明，討論的都是無向圖。

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

通俗地講，就是使得圖GG連通時，所選取的邊的長度的和最小。

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

算法講解：

現(xiàn)在，我們開始討論Prim Algorithm。這個算法可以分為下面幾個步驟：

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

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

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

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

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

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

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

代碼如下：

#include <iostream>

#include <memory.h>?

#include <vector>

using namespace std;

const int MAX = 1024;

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

int N, M;

vector<pair<int, int> > 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<int> pMST; // 儲存MST的結(jié)點?

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

pMST.push_back(1); // 將結(jié)點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é)點1相連的頂點

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

for(int i = 1; i <= N - 1; i++) // 剩余N-1個頂點，循環(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é)點nVertex加入MST

nCost += nWeight; // 計算MST的費用

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;

}

總結(jié)

以上是生活随笔為你收集整理的Prim 算法及其高效实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。