栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > C/C++/C#

下列代码的功能是使用Prim算法求出无向图的最小生成树权值总和,请补全。

C/C++/C# 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

下列代码的功能是使用Prim算法求出无向图的最小生成树权值总和,请补全。

程序填空题

下列代码的功能是使用Prim算法求出无向图的最小生成树权值总和,请补全。

给出的图用邻接矩阵存储。若两顶点之间没有直接路径,则对应权值为 INF,且题目保证 INF 值足够大;若找不到距离最短的顶点或者无法求出权值总和,则返回 ERROR。

typedef int WeightType;
typedef int VertexType;
typedef struct {
    int Nv;
    WeightType G[MAX_GRAPH_SIZE][MAX_GRAPH_SIZE];
} GNode, * MGraph;

VertexType FindMinDist(MGraph Graph, WeightType dist[]) {
    VertexType MinV = -1, V;
    WeightType MinDist = INF;
    for (V = 0; V < Graph->Nv; V++) {
        if (dist[V] != 0 && dist[V] < MinDist) {
            MinDist = dist[V];
            MinV = V;
        }
    }
    if (MinDist < INF) {
        return MinV;
    }
    else {
        return ERROR;
    }
}

int Prim(MGraph Graph) {
    int dist[MAX_GRAPH_SIZE];
    int TotalWeight = 0, VCount = 0;
    VertexType  V, W;
    for (V = 0; V < Graph->Nv; V++) {
        dist[V] = Graph->G[0][V];
    }
    dist[0] = 0;
    VCount++;
    while (1) {
        VertexType MinV;
        if ((MinV = FindMinDist(Graph, dist)) == ERROR) {
            break;
        }
        TotalWeight += dist[MinV];
        dist[MinV] = INF;
        VCount++;
        for (W = 0; W < Graph->Nv; W++) {
            if (dist[W] != 0 && dist[W] > Graph->G[MinV][W])
            {
                dist[W] = Graph->G[MinV][W];
            }
        }
    }
    if(!TotalWeight)
    {
        return ERROR;
    }
    else {	
        return TotalWeight;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/589885.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号