本文出自：http://blog.csdn.net/svitter

题意：给出一个数字n代表邻接矩阵的大小，随后给出邻接矩阵的值。输出最小生成树的权值。

题解：

prime算法的基本解法；

1.选择一个点，然后不停的向当中增加权值最小的边，边的一端在已经生成的部分生成树中，还有一端在未生成的生成树中。

2.利用优先队列维护边，将增加的点所包括的边增加到队列中去，随后依照边的权值弹出。

简单理解方法：一个人能够拉非常多人，新被拉进来的人，把能拉的人（有边，且未被訪问）排队，找最好拉的人拉进来，循环。

注意：

1.假设使用priority_queue(二叉堆)+prime算法，时间复杂度为ElogV

2.直接使用邻接矩阵，复杂度为O(n^2)

3.使用STL 优先队列的时候记得定义排序方法；（见代码：14行）

4.记得清空vector数组

Kruskal算法的基本解法：

1.Kruskal算法存的是边。将全部边存起来，然后依照从小到大排序，依次增加两端不再同一集合的边。

2.复杂度为O(ElogE)

3.稀疏图

简单理解方法：几个人抱团，最后在全都拉在一起。

树的特点：边的个数是n-1，所以增加n-1条边就可以停止。

Prime+堆解法——代码：

#include <iostream>

#include <cstdio>

#include <vector>

#include <queue>

#define INF 0xffffff

using namespace std;

struct Edge

{

    int v;

    int w;

    Edge(int v_, int w_):v(v_), w(w_){}

    bool operator < (const Edge &e) const

    {

        return w > e.w;

    }

};

typedef vector <Edge> vedge;

vector <vedge> g(110);

int n;

int Prime(vector <vedge> & g)

{

    int i, j, k;

    vector <int> visit(n);

    vector <int> dist(n);

    priority_queue <Edge> pq;

    for(i = 0; i < n; i++)

    {

        visit[i] = 0;

        dist[i] = INF;

    }

    Edge temp(0, 0);

    int nOwn = 0;

    int nWeight = 0;

    pq.push(Edge(0, 0));

    while(nOwn < n && !pq.empty())

    {

        do

        {

            temp = pq.top();

            pq.pop();

        }

        while(visit[temp.v] == 1 && !pq.empty());

        if(visit[temp.v] == 0)

        {

            nOwn++;

            nWeight += temp.w;

            visit[temp.v] = 1;

        }

        for(i = 0 ; i < g[temp.v].size(); i++)

        {

            int v = g[temp.v][i].v;

            if(visit[v] == 0)

            {

                int w = g[temp.v][i].w;

                dist[v] = w;

                pq.push(Edge(v, w));

            }

        }

    }

    if(nOwn < n)

    {

        cout << nOwn << n << endl;

        return -1;

    }

    return nWeight;

}

int main()

{

    int i, j, k;

    int temp;

    while(~scanf("%d", &n))

    {

        for(i = 0; i < n; i++)

            g[i].clear();

        for(i = 0; i < n; i++)

            for(j = 0; j < n; j++)

            {

                scanf("%d", &temp);

                g[i].push_back(Edge(j, temp));

            }

        cout << Prime(g) << endl;

    }

    return 0;

}

Kruscal算法代码：

//author: svtter

//

#include <algorithm>

#include <vector>

#include <iostream>

#include <stdio.h>

#include <string.h>

const int MAXN = 100000;

using namespace std;

vector <int> root;

int n;

struct Edge

{

    int i, j, w;

    Edge(int i_, int j_, int w_):i(i_), j(j_), w(w_){}

    bool operator < (const Edge &e) const

    {

        return w < e.w;

    }

};

void init()

{

    for(int i = 0; i < n; i++)

        root.push_back(i);

}

int getRoot(int i)

{

    if(root[i] == i)

        return i;

    return root[i] = getRoot(root[i]);

}

void Merge(int i, int j)

{

    int a, b;

    a = getRoot(i);

    b = getRoot(j);

    if(a == b)

        return;

    //a's root is a;

    root[a] = b;

}

vector <Edge> g;

int Kruskal()

{

    //init the

    init();

    sort(g.begin(),g.end());

    //the num of tree's Edges is n-1;

    //

    int nEdge = 0;

    //the weight of whole gtree

    int nWeight = 0;

    int i, s, e, w;

    for(i = 0; i < g.size(); i++)

    {

        s = g[i].i;

        e = g[i].j;

        w = g[i].w;

        if(getRoot(s) != getRoot(e))

        {

            Merge(s,e);

            nWeight += w;

            nEdge++;

        }

        if(nEdge == n-1)

            break;

    }

    return nWeight;

}

int main()

{

    int i, j, k;

    while(~scanf("%d", &n))

    {

        g.clear();

        root.clear();

        for(i = 0; i < n ; i++)

            for(j = 0; j < n; j++)

            {

                scanf("%d", &k);

                g.push_back(Edge(i, j, k));

            }

        cout << Kruskal() << endl;

    }

    return 0;

}