今天开始学算法系列 -- prim

    最小生成树是对于有权连通图求权重合最小的联通子图问题的算法，注意连通图是不能带环的。像这类问题在算法题中很常见，像求几个城市间网路搭建成本消耗问题就可以运用prim最小生成树来解决。
   最小生成树和Dijkstra算法的思想比较类似， 只是Dijkstra主要关注每个节点的优先级， 而prim关注于相连的边的优先级。详细的还是从代码中看：
   伪代码：
   priority_queue que;
   que.push(startE);   //将源点的边长加入队列
   while que is not empty
        V a = que.top();
          vector T.pushback(a);  //每次取出的边都记录下来，最后这个vector就是最小生成树里所有的边
          que.pop();
        for all V connect with a:
            if d(v) > d(a) + length_a_to_v;
               d(v) = d(a) + length_a_to_v;
               que.push(length_a_to_v);

   直接上代码：
   

#include <functional>
#include <queue>
#include <vector>
using namespace std;
#define MAXV 4
#define INF 100000
int d[4] = { 0 };
int edge[4][4] = { 0 };
void init()
{
    for (int i = 0; i < MAXV; i++)
        for (int j = 0; j < MAXV; j++)
            edge[i][j] = INF;
    edge[0][0] = 0;
    edge[0][1] = 6;
    edge[1][0] = 6;
    edge[0][2] = 1;
    edge[2][0] = 1;
    edge[1][3] = 2;
    edge[3][1] = 2;
    edge[2][3] = 8;
    edge[3][2] = 8;
    edge[3][0] = 9;
    edge[0][3] = 9;
}

typedef pair<int, int> p;
vector<p> mst_vec;
void MST(p s)
{
    priority_queue<p, vector<p>, greater<p>> que;
    que.push(s);
    while (!que.empty())
    {
        p tmp = que.top();
        que.pop();
        if (mst_vec.size() != MAXV)
            mst_vec.push_back(tmp);
        else
            break;
        for (int i = 0; i < MAXV; i++)
        {
            if (tmp.second != i)
            {
                if (edge[tmp.second][i] != INF && d[i] > d[tmp.second] + edge[tmp.second][i])
                {
                    d[i] = d[tmp.second] + edge[tmp.second][i];
                    p newP;
                    newP.first = edge[tmp.second][i];
                    newP.second = i;
                    que.push(newP);
                }
            }
        }

    }
    for (int i = 0; i < MAXV; i++)
    {
        printf("%d", mst_vec[i].first);
    }

}

int _tmain(int argc, _TCHAR* argv[])
{
    fill(d, d + 4, INF);

    init();
    d[0] = 0;
    p s;
    s.first = 0;
    s.second = d[0];
    MST(s);

    return 0;
}