線上訂房服務-台灣趴趴狗聯合訂房中心
發文 回覆 瀏覽次數:3468
推到 Plurk!
推到 Facebook!

關於MST的prim演算法C++

尚未結案
supergba2002
一般會員


發表:2
回覆:2
積分:0
註冊:2008-09-26

發送簡訊給我
#1 引用回覆 回覆 發表時間:2009-04-14 23:14:55 IP:140.115.xxx.xxx 訂閱

[code cpp]
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

int n; // n : 頂點個數
vector > g; // g : 圖(graph)(用鄰接矩陣(adjacent matrix)表示)
vector known; // known : 各點是否已經選取
vector dist; // dist : 已選取點集到未選取點的最小邊長
vector 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(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;
}

[/code]

這是prim演算法的程式碼,但是我現在有個small.txt檔
有6個節點,10條邊界,我該怎麼修改呢?

要讀入small.txt檔,來計算最小生成樹,第一行是節點,第二行也是節點,第三行是成本
附加檔案:49e4a86fe8e7a_small.txt
系統時間:2024-03-29 12:51:45
聯絡我們 | Delphi K.Top討論版
本站聲明
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。
2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。
3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇!