数据结构-最小生成树-题解（C++代码）

这题用prim算法解决最小生成树的思想与用dijkstra算法解决最段路径的思想几乎完全相同，可以看看我上一篇关于dijkstra算法的文章，谢谢。

好了，话不多说，代码搞起来。

#include<iostream>
using namespace std;
const int N = 50;
const int INF = 100000000;
int Graph[N][N];
int d[N];
bool visit[N];
int n;
//普利姆算法适合求解提供源点的算法
//将最小生成树的所有点看作一个集合，里面的每一个点都属于这个集合
//生成最小生成树的过程就是把点一个一个加入集合的过程。
int prim(int s)
{
    d[s] = 0;//更新源点的距离
    int ans = 0;//最小生成树的权值之和
    for (int i = 0; i < n; i++)
    {
        int min = INF;
        int index = -1;
        for (int j = 0; j < n; j++)
        {
            if (visit[j] == false && d[j] < min)
            {
                min = d[j];
                index = j;
            }
        }
        if (index == -1)
        {
            return INF;//此图不连通
        }
        visit[index] = true;
        ans += d[index];
        for (int k=0;k<n;k++)
        {
            if (visit[k] == false &&d[k]>Graph[index][k])
            {
                d[k] = Graph[index][k];//这就是不同点，更新点到集合的最小距离即可
            }
        }
    }
    return ans;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> Graph[i][j];
            if (Graph[i][j] == 0)
            {
                Graph[i][j] = INF;
            }
        }
    }
    //如果原来的图里面任何两条边长都不相同，那么最小生成树是唯一的，
    //此时不管用什么方法算出来的都是一样的。但是如果图里有相等的边，
    //那么最小生成树可能不唯一，这样就无法保证不同的方法得到同一棵树
    //（即使是同一个算法，只内要图的编号方式改变也容可能得到不同的最小生成树）
    //所以在这里，我们运用循环 把每一个点当成源点，计算最小生成树的权值之和
    int  ans;
    int min = INF;
    for (int i = 0; i < n; i++)
    {prim算法适合给你源点，这里没有需要我们自己来
    每一次都要把visit和d数组更新
        for (int i = 0; i < n; i++)
        {
            visit[i] = false;
            d[i] = INF;
        }
        ans = prim(i);
        取最小值输出
         if (ans < min)
        {
            min = ans;
        }
    }
    cout << min << endl;
    return 0;
}