017-Prim算法-貪心-《算法設(shè)計(jì)技巧與分析》M.H.A學(xué)習(xí)筆記
來源：程序員人生 發(fā)布時(shí)間：2016-06-30 08:42:24 閱讀次數(shù)：2760次
基本思路：
定義結(jié)點(diǎn)集合U, V (U表示已選擇加入MST的結(jié)點(diǎn)集合,V表示未選)
1. 任選1個(gè)結(jié)點(diǎn)加入U(xiǎn)
2. 選擇1條邊權(quán)最小的邊，他的兩個(gè)結(jié)點(diǎn)分別屬于U, V，并把屬于V的那個(gè)結(jié)點(diǎn)加入U(xiǎn)
3. 重復(fù)履行2直到V空
偽代碼：
C++代碼：
int g[mnx][mnx];
int n, m;
int d[mnx];
// 樸素 prim, 復(fù)雜度O(|V|^2) |V|:點(diǎn)數(shù)， |E|:邊數(shù)
int prim() {
memset(d, 0x3f, sizeof d); //初始化
int ret = d[1] = 0; // 先把d[1]弄成0
for(int i = 1; i <= n; ++i) {
int u = ⑴;
for(int j = 1; j <= n; ++j) //找到d[u]最小的1個(gè)u
if((u == ⑴ || d[u] > d[j]) && d[j] != ⑴)
u = j;
ret += d[u];
d[u] = ⑴;
for(int j = 1; j <= n; ++j) // 更新和u鄰接的節(jié)點(diǎn)的d[j]值
d[j] = min(d[j], g[u][j]);
}
return ret;
}
算法分析：
主要耗費(fèi)在查找邊權(quán)最小的邊，這1步的2重循環(huán)耗費(fèi)Θ(n2)，所以算法的時(shí)間復(fù)雜度為Θ(n2)。
堆優(yōu)化改進(jìn)：
我們用小頂堆來完成查找最小邊，和Dijkstra算法1樣，算法共進(jìn)行了n⑴次插入、n⑴次刪除、m-n+1次Siftup運(yùn)算。總的時(shí)間復(fù)雜度為O（mlogn）。
偽代碼：
C++代碼：
int fst[mnx], nxt[mxe], cost[mxe], to[mxe], e;
void init() {
memset(fst, ⑴, sizeof fst);
e = 0;
}
void add(int u, int v, int c) {
to[e] = v, nxt[e] = fst[u], cost[e] = c, fst[u] = e++;
}
struct node {
int u, dis;
node(int u, int dis):u(u), dis(dis) {}
bool operator < (const node &b) const {
return dis > b.dis;
}
};
//堆優(yōu)化， 復(fù)雜度O(|E|log|V|), 稠密圖時(shí)比較慢
int primHeap() {
memset(d, 0x3f, sizeof d);
d[1] = 0;
priority_queue<node> q;
q.push(node(1,0)); // 先選定第1個(gè)節(jié)點(diǎn)
int ret = 0;
while(!q.empty()) {
int u = q.top().u;
int dd = q.top().dis;
q.pop();
if(d[u] != dd) continue; // 如果是被更新之前的值的話就不取， continue掉
ret += dd;
d[u] = ⑴;
for(int j = fst[u]; ~j; j = nxt[j]) {
int v = to[j], c = cost[j]; // 更新
if(d[v] > c && d[v] != ⑴) {
d[v] = c;
q.push(node(v, c));
}
}
}
return ret;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
