最小生成树-Prim算法

最小生成树-Prim算法,第1张

最小生成树-Prim算法
#include 
using namespace std;
const int MAX = 100, INF = (1 << 30);
struct Edge
{
    int p = -1, d = INF;
    bool used = false;
};
int n, M[MAX][MAX];
int Prim()
{
    int sum = 0;
    Edge E[n];
    E[0].d = 0;
    while (true)
    {
        int u = -1, minv = INF;
        //在V-MST各节点中寻找与MST距离最近的结点u
        for (int i = 0; i < n; i++)
            if (minv > E[i].d && !E[i].used)
                u = i, minv = E[i].d;
        //找不到,即说明MST已包含V的全部结点
        if (u == -1 || minv == INF)
            break;
        //MST加入结点u
        E[u].used = true;
        sum += E[u].d;
        //当MST加入结点u后,更新连接MST和V-MST各节点的最短距离
        for (int v = 0; v < n; v++)
            if (!E[v].used && M[u][v] != INF)
                if (M[u][v] < E[v].d)
                    E[v].d = M[u][v], E[v].p = u;
    }
    return sum;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0, e; j < n; j++)
            (cin >> e), M[i][j] = (e == -1) ? INF : e;
    cout << Prim();
    return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5692254.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存