關於MST的prim演算法C++ |
尚未結案
|
supergba2002
一般會員 發表:2 回覆:2 積分:0 註冊:2008-09-26 發送簡訊給我 |
[code cpp] #include #include #include #include #include #include #include #include using namespace std; int n; // n : 頂點個數 vector vector vector vector 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 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檔,來計算最小生成樹,第一行是節點,第二行也是節點,第三行是成本 |
本站聲明 |
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。 2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。 3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇! |