前面在介绍并查集时顺便提了Kruskal算法，既然已经说到了最小生成树问题，就没有道理不把Prime算法说了。

这里面先补充下Kruskal算法的大概意思，Kruskal算法通过把所有的边从小到大排列后，不断取权值最小的边加入最小生成树（起初可能是离散的多个树，最终连成一个整体），并通过并查集来舍弃形成回路的边。

Prime算法有所不同，Prime算法先将一个起点加入最小生成树，之后不断寻找与最小生成树相连的边权最小的边能通向的点，并将其加入最小生成树，是一种更符合人的主观直觉的最小生成树算法。

需要注意的是，Kruskal和Prime都仅适用于无向图。

#include 
     
      const int MAX_V = 100;const int INF = 1000000;int cost[MAX_V][MAX_V];//图int V;bool path[MAX_V][MAX_V];//记录结果int res;bool used[MAX_V];//表示是否访问过int mincost[MAX_V];//表示到此点消耗值void Prime(){    res = 0;//统计最小消耗    for (int i = 0;i < V;++i)//初始化    {        used[i] = false;        mincost[i] = INF;        for (int j = 0;j < V;++j)        {            path[i][j] = false;        }    }    mincost[0] = 0;//从0点开始    int prev = 0;//记录路径    while (true)    {        int visited = -1;        for (int i = 0;i < V;++i)        {            if (!used[i] && (visited == -1 || mincost[i] < mincost[visited])) visited = i;//贪婪寻找最短边        }        if (visited == -1) break;        used[visited] = true;        if (visited)        {            path[prev][visited] = true;            prev = visited;        }        res += mincost[visited];        for (int i = 0;i < V;++i)        {            mincost[i] = std::min(mincost[i], cost[visited][i]);        }    }}
     

 

下面给出一组Kruskal和Prime的测试数据及结果：

测试代码：

void mstTest(){    cin >> V;    for (int i = 0;i < V;++i)        for (int j = 0;j < V;++j)        {            cin >> cost[i][j];        }                for (int i = 0;i < V;++i) d[i] = INF;    cout << "Kruskal:" << endl;    Kruskal();    for (int i = 0;i < V;++i)    {        for (int j = 0;j < V;++j)        {            if (path[i][j]) cout << i << " " << j << endl;        }    }    cout << res << endl;    cout << endl;    cout << "Prime" << endl;    Prime();    for (int i = 0;i < V;++i)    {        for (int j = 0;j < V;++j)        {            if (path[i][j]) cout << i << " " << j << endl;        }    }    cout << res << endl;}

 

测试结果：

9

1000000 1 5 7 4 1000000 1000000 1000000 1000000

1 1000000 1000000 1000000 1000000 3 10 1000000 1000000

5 1000000 1000000 1000000 1000000 2 1000000 2 1000000

7 1000000 1000000 1000000 1000000 1000000 1 1000000 1000000

4 1000000 1000000 1000000 1000000 1000000 1000000 3 1000000

1000000 3 2 1000000 1000000 1000000 1000000 1000000 2

1000000 10 1000000 1 1000000 1000000 1000000 1000000 9

1000000 1000000 2 1000000 3 1000000 1000000 1000000 5

1000000 1000000 1000000 1000000 1000000 2 9 5 1000000

Kruskal:

0 1

0 3

1 5

2 5

2 7

3 6

4 7

5 8

21

Prime

0 1

1 5

2 7

3 6

4 3

5 2

7 8

8 4

21

请按任意键继续. . .

可以看到，两种算法生成了拥有相同最小消耗的两颗完全不同的最小生成树。