lzm

who dare win.

posts - 14, comments - 29, trackbacks - 0, articles - 0

Prim算法

Posted on 2009-04-10 19:11 lzmagic 閱讀(4375) 評論(1) 編輯收藏引用所屬分類: Algorithm

/**

* PRIM(簡單版) 最小生成樹算法 (Minimum Spanning Tree)

* 輸入：圖g； // 有向圖或者無向圖

* 輸出：(1)最小生成樹長sum；

* (2)最小生成樹prev。

* 結構: 圖g用鄰接矩陣表示，最短邊長dist用數組表示。

* 算法：Prim算法

* 復雜度：O(|V|^2)

#include <iostream>

#include <vector>

#include <list>

#include <iterator>

#include <algorithm>

#include <numeric>

#include <functional>

#include <climits>

using namespace std;

int n; // n : 頂點個數

vector<vector<int> > g; // g : 圖(graph)(用鄰接矩陣(adjacent matrix)表示)

vector<bool> known; // known : 各點是否已經選取

vector<int> dist; // dist : 已選取點集到未選取點的最小邊長

vector<int> prev; // prev : 最小生成樹中各點的前一頂點

int s; // s : 起點(start)

int sum; // sum : 最小生成樹長

bool Prim() // 貪心算法(Greedy Algorithm)

{

known.assign(n, false);

dist.assign(n, INT_MAX);

prev.resize(n); // 初始化known、dist、prev。

dist[s] = 0; // 初始化起點到自身的路徑長為0。

int i;

for (i = 0; i < n; ++i)

{

int min = INT_MAX, v;

for (int i = 0; i < n; ++i)

if (!known[i] && min > dist[i])

min = dist[i], v = i; // 尋找未知的最短路徑長的頂點v，

if (min == INT_MAX) break; // 如果找不到，退出；

known[v] = true; // 如果找到，將頂點v設為已知，

sum += dist[v]; // 調整最小生成樹長

for (int w = 0; w < n; ++w) // 遍歷所有v指向的頂點w，

if (!known[w] && g[v][w] < INT_MAX && dist[w] > g[v][w])

dist[w] = g[v][w], prev[w] = v; // 調整頂點w的最短路徑長dist和最短路徑的前一頂點 prev。

}

return i == n; // 如果選取頂點個數為n，成功。

}

int main()

{

n = 7;

g.assign(n, vector<int>(n, INT_MAX));

g[0][1] = g[1][0] = 2; g[0][2] = g[2][0] = 4; g[0][3] = g[3][0] = 1;

g[1][3] = g[3][1] = 3; g[1][4] = g[4][1] = 10;

g[2][3] = g[3][2] = 2; g[2][5] = g[5][2] = 5;

g[3][4] = g[4][3] = 7; g[3][5] = g[5][3] = 8; g[3][6] = g[6][3] = 4;

g[4][6] = g[6][4] = 6;

g[5][6] = g[6][5] = 1;

s = 0; // 起點任選

sum = 0;

if (Prim())

{

cout << sum << endl;

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

if(i != s) cout << prev[i] << "->" << i << endl;

}

else

{

cout << "Some vertex cann't be reached." << endl;

}

system("pause");

return 0;

}

Feedback

# re: Prim算法 回復 更多評論

2009-04-15 12:52 by brightcoder

good!~

刷新評論列表

只有注冊用戶登錄后才能發表評論。


相關文章: Floyd_Warshall算法 Kruskal算法 Prim算法 Critical Path 關鍵路徑 Bellman_Ford算法 SPFA算法 Dijkstra算法 USP 無權最短路徑算法 Topsort 拓撲排序 (正則表達式)是否匹配(字符串) Quicksort 快速排序

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

lzm

導航

常用鏈接

留言簿(2)

隨筆分類(13)

隨筆檔案(14)

收藏夾(4)

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

Prim算法

Feedback

# re: Prim算法 回復 更多評論

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

lzm

導航

常用鏈接

留言簿(2)

隨筆分類(13)

隨筆檔案(14)

收藏夾(4)

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

Prim算法

Feedback

# re: Prim算法 回復 更多評論

# re: Prim算法回復更多評論