Prim最小生成树算法

现在的位置: 首页 > 综合 > 正文

Prim最小生成树算法

2013年09月09日 ⁄ 综合 ⁄ 共 1555字 ⁄ 字号小中大 ⁄ 评论关闭


MST-PRIM(G, w, r)

// G: graph, w: weight,  r:root 
 1  for each u ∈ V [G]

 2       do key[u] ← ∞

 3          π[u] ← NIL

 4  key[r] ← 0

 5   Q ← V [G]

 6   while Q ≠ Ø

 7       do u ← EXTRACT-MIN(Q)

 8          for each v ∈ Adj[u]

 9              do if v ∈ Q and w(u, v) < key[v]

10                    then π[v] ← u

11                         key[v] ← w(u, v)

Prim's algorithm works as shown in the figure:

// MST set实现最小优先级队列

#include <vector>

#include <set>

int MST_PRIM(const vector<vector<pair<int, int> > > & G)
/*

index start from 1 to n and
G.size() -1 is the number of vertices in our graph
G[i].size() is the number of vertices directly reachable from vertex with index i
G[i][j].first is the index of j-th vertex reachable from vertex i
G[i][j].second is the length of the edge heading from vertex i to vertex G[i][j].first

       return the minimum cost of the spanning tree
*/
...{
    int n = G.size();
    vector<int> key (n, 987654321);
    vector<bool> belongQ(n, 1);
    key[1]=0;
    set<pair<int, int> > Q;
    for(int i=1; i<n; i++)
        Q.insert(make_pair(key[i], i));
    while (!Q.empty()) ...{
        int u=Q.begin()->second;
        Q.erase(Q.begin());
        belongQ[u]=false;
        for(int i=0; i< G[u].size(); i++) ...{
            int v = G[u][i].first;
            if(belongQ[v] && G[u][i].second < key[v]) ...{
                Q.erase(Q.find(make_pair(key[v], v)));
                key[v]=G[u][i].second;
                Q.insert(make_pair(key[v], v));
            }
        }
    }
    int res=0;
    for(int i=1; i < n; i++)
        res+=key[i];
    return res;
}