|
|
Posted on 2009-08-28 09:12 reiks 閱讀(545) 評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi): 算法與數(shù)據(jù)結(jié)構(gòu)
 // PRIM(簡(jiǎn)單版) 最小生成樹(shù)算法 (Minimum Spanning Tree)
// 輸入：圖g； // 有向圖或者無(wú)向圖
// 輸出：(1)最小生成樹(shù)長(zhǎng)sum；
// (2)最小生成樹(shù)prev。
// 結(jié)構(gòu): 圖g用鄰接矩陣表示，最短邊長(zhǎng)dist用數(shù)組表示。
// 算法：Prim算法
//復(fù)雜度：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 : 頂點(diǎn)個(gè)數(shù)
vector<vector<int> > g; // g : 圖(graph)(用鄰接矩陣(adjacent matrix)表示)
vector<bool> known; // known : 各點(diǎn)是否已經(jīng)選取
vector<int> dist; // dist : 已選取點(diǎn)集到未選取點(diǎn)的最小邊長(zhǎng)
vector<int> prev; // prev : 最小生成樹(shù)中各點(diǎn)的前一頂點(diǎn)
int s; // s : 起點(diǎn)(start)
int sum; // sum : 最小生成樹(shù)長(zhǎng)
bool Prim() // 貪心算法(Greedy Algorithm)
   {
 known.assign(n, false);
dist.assign(n, INT_MAX);
prev.resize(n); // 初始化known、dist、prev。
dist[s] = 0; // 初始化起點(diǎn)到自身的路徑長(zhǎng)為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; // 尋找未知的最短路徑長(zhǎng)的頂點(diǎn)v，
if (min == INT_MAX) break; // 如果找不到，退出；
known[v] = true; // 如果找到，將頂點(diǎn)v設(shè)為已知，
sum += dist[v]; // 調(diào)整最小生成樹(shù)長(zhǎng)
for (int w = 0; w < n; ++w) // 遍歷所有v指向的頂點(diǎn)w，
if (!known[w] && g[v][w] < INT_MAX && dist[w] > g[v][w])
dist[w] = g[v][w], prev[w] = v; // 調(diào)整頂點(diǎn)w的最短路徑長(zhǎng)dist和最短路徑的前一頂點(diǎn) prev。
 }
return i == n; // 如果選取頂點(diǎn)個(gè)數(shù)為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; // 起點(diǎn)任選
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;
}
/**//*=============================*/
/**//*
Write By LiveStar (2008.07.23)
*/
#include <stdio.h>
//max表示點(diǎn),邊的最大個(gè)數(shù)
#define max 1000
//wq表示兩點(diǎn)的距離為無(wú)窮
#define wq 9999
//鄰接矩陣存儲(chǔ)相應(yīng)的邊的權(quán)重
int mix[max][max];
//輸入并構(gòu)造鄰接矩陣
void input(int n,int m)
{
int i,j,sp,ep,wg;
//初始化鄰接矩陣每個(gè)都是無(wú)窮大
for (i=0;i<n;i++)
for (j=0;j<n;j++)
mix[i][j]=wq;
printf("請(qǐng)輸入邊的起點(diǎn)、終點(diǎn)、權(quán)重(EX:1 2 3):\n");
for (i=0;i<m;i++)
{
scanf("%d %d %d",&sp,&ep,&wg);
//無(wú)向連通圖
mix[sp][ep]=wg;
mix[ep][sp]=wg;
}
}
//顯示鄰接矩陣
void output(int n,int m)
{
int i,j;
printf("\n鄰接矩陣如下：\n\n");
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
printf("%d\t",mix[i][j]);
printf("\n");
}
}
//prim算法實(shí)現(xiàn)
void prim(int n,int r)
{
//a[max]用來(lái)存放各個(gè)點(diǎn)到已經(jīng)標(biāo)記點(diǎn)的集合的最短距離
int a[max];
//b[max]用來(lái)記錄每個(gè)點(diǎn)的標(biāo)記狀態(tài)，false表示還沒(méi)標(biāo)記。
bool b[max];
int i,j,k,min;
//初始化從根節(jié)點(diǎn)開(kāi)始
for (i=0;i<n;i++)
{
a[i]=mix[r][i];
b[i]=false;
}
b[r]=true;
printf("\n依次被標(biāo)記的點(diǎn)及相應(yīng)邊的權(quán)重：\n");
printf("%d\t%d\n",r,0);
for (i=0;i<n-1;i++)//還剩n-1個(gè)點(diǎn)
{
k=0;
min=wq;
for (j=0;j<n;j++)
{
//第j個(gè)點(diǎn)到已經(jīng)標(biāo)記點(diǎn)的集合的距離最小且這個(gè)點(diǎn)還沒(méi)有被標(biāo)記
//k記錄下一個(gè)將被標(biāo)記的點(diǎn)
if (a[j]<min&&b[j]==false)
{
min=a[j];
k=j;
}
}
b[k]=true;//標(biāo)記節(jié)點(diǎn)k
printf("%d\t%d\n",k,min);
//更新a[]里的狀態(tài)，時(shí)刻保持最新的狀態(tài)
//存放各個(gè)點(diǎn)到已經(jīng)標(biāo)記點(diǎn)的集合的最短距離
for (j=0;j<n;j++)
{
if (mix[k][j]<a[j])
{
a[j]=mix[k][j];
}
}
}
}
int main()
{
//n是點(diǎn)的個(gè)數(shù) ，m是邊的個(gè)數(shù)
int n,m,r;
printf("請(qǐng)輸入點(diǎn)的個(gè)數(shù)和邊的個(gè)數(shù)(EX:1 3):\n");
scanf("%d %d",&n,&m);
//輸入并構(gòu)造鄰接矩陣
input(n,m);
//顯示鄰接矩陣
output(n,m);
while (1)
{
printf("\n請(qǐng)輸入根節(jié)點(diǎn)(-1跳出)：\n");
scanf("%d",&r);
if(r==-1)
break;
//prim算法實(shí)現(xiàn)
prim(n,r);
printf("\n\n");
}
return 0;
}
|