题解 | #最小生成树#

/**

• 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
• 返回最小的花费代价使得这n户人家连接起来
• @param n int整型 n户人家的村庄
• @param m int整型 m条路
• @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
• @param costRowLen int cost数组行数
• @param costColLen int* cost数组列数
• @return int整型 */ //普里姆算法 #include <stdlib.h> #include <limits.h> // For INT_MAX

int miniSpanningTree(int n, int m, int** cost, int costRowLen, int* costColLen) { int* homevexcost = malloc(n * sizeof(int)); // 存储到最近村庄的距离 int** edgecost = malloc(n * sizeof(int*)); // 邻接矩阵 int sumcost = 0; // 最小生成树的总成本

// 初始化邻接矩阵
for (int i = 0; i < n; i++) {
    edgecost[i] = malloc(n * sizeof(int));
    for (int j = 0; j < n; j++) {
        edgecost[i][j] = (i == j) ? 0 :
                         INT_MAX; // 对角线设为0，其余设为无穷大
    }
}

// 填充邻接矩阵
for (int i = 0; i < costRowLen; i++) {
    int u = cost[i][0] - 1;
    int v = cost[i][1] - 1;
    int w = cost[i][2];
    if (w < edgecost[u][v]) {
        edgecost[u][v] = w;
        edgecost[v][u] = w;
    } // 因为图是无向的
}

// 初始化第一个村庄的成本为0
homevexcost[0] = 0;
// 计算从第一个村庄出发到其他村庄的最短距离
for (int i = 0; i < n; i++) {
    homevexcost[i] = edgecost[0][i];
}

// 构建最小生成树
for (int i = 1; i < n; i++) {
    int mincost = INT_MAX;
    int l = -1;
    for (int j = 0; j < n; j++) {
        if (homevexcost[j] != 0 && homevexcost[j] < mincost) {
            mincost = homevexcost[j];
            l = j;
        }
    }

    // 更新已加入生成树的村庄集合，并累加当前边的成本到总成本中
    sumcost += mincost;
    homevexcost[l] = 0;

    // 更新从新加入的村庄出发到其他村庄的距离
    for (int a = 0; a < n; a++) {
        if (edgecost[l][a] < homevexcost[a]) {
            homevexcost[a] = edgecost[l][a];
        }
    }
}

// 释放内存并返回最小生成树的总成本
for (int i = 0; i < n; i++) {
    free(edgecost[i]);
}
free(edgecost);
free(homevexcost);

return sumcost;

}