题解：关于使用Prim算法求解最小生成树问题

一、题目背景

给定一个具有 (n) 个节点的带权无向图，图中每两个节点之间都存在一条边，并且每条边都有一个权值。要求使用Prim算法找出该图的最小生成树（Minimum Spanning Tree, MST），即连接所有节点且边权总和最小的子图，并输出最小生成树的边权总和。

二、代码整体思路

代码主要通过Prim算法来解决最小生成树问题，其核心思路是从一个起始节点开始，逐步将与已选节点相连的边中权值最小的边所对应的节点加入到最小生成树中，直到所有节点都被包含在最小生成树中。具体步骤如下：
1. 读取图的节点数量 (n) 和每两个节点之间边的权值，存储在邻接矩阵 w 中。
2. 初始化距离数组 dist，将所有节点到起始节点（这里选择节点 (1)）的距离设为无穷大，起始节点到自身的距离设为 (0)。
3. 调用 prim 函数，通过循环不断选择距离已选节点集合最近的节点，将其加入到最小生成树中，并更新其他节点到已选节点集合的距离。
4. 最后返回最小生成树的边权总和，并输出结果。

三、代码逐段分析

（一）头文件和全局变量

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int w[N][N];
int dist[N];
bool st[N];

1. 头文件：
   • #include <cstring>：用于字符串操作和内存初始化函数，如 memset。
   • #include <iostream>：提供 C++ 风格的输入输出流，如 cin 和 cout。
   • #include <algorithm>：包含一些常用的算法函数，如 min、max 等。
   • using namespace std;：使用标准命名空间，以便直接使用标准库中的函数和类型。
2. 常量定义：
   • const int N = 110：定义图中节点的最大数量。
3. 变量定义：
   • int n;：表示图的节点数量。
   • int w[N][N];：二维数组 w 用于存储图的邻接矩阵，w[i][j] 表示节点 (i) 和节点 (j) 之间边的权值。
   • int dist[N];：数组 dist 用于存储每个节点到已选节点集合（最小生成树）的最短距离。
   • bool st[N];：数组 st 用于标记每个节点是否已经被加入到最小生成树中，st[i] 为 true 表示节点 (i) 已在最小生成树中，false 表示不在。

（二）prim 函数

int prim()
{
    int res = 0;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], w[t][j]);
    }

    return res;
}

1. 初始化：
   • int res = 0;：初始化最小生成树的边权总和为 (0)。
   • memset(dist, 0x3f, sizeof dist);：将距离数组 dist 初始化为一个较大的值（0x3f 表示十六进制的较大数，这里用于表示初始时的无穷距离）。
   • dist[1] = 0;：设置起始节点（节点 (1)）到自身的距离为 (0)。
2. Prim算法过程：
   • 外层循环 for (int i = 0; i < n; i ++ )：循环 (n) 次，每次选择一个节点加入到最小生成树中。
   • 内层循环 for (int j = 1; j <= n; j ++ )：在未被加入到最小生成树的节点中（!st[j]），找到距离已选节点集合最近的节点 t。if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; 表示如果节点 j 未被标记且（t 还未初始化或者节点 j 到已选节点集合的距离小于节点 t 到已选节点集合的距离），则更新 t 为节点 j。
   • res += dist[t];：将节点 t 到已选节点集合的距离加到最小生成树的边权总和 res 中。
   • st[t] = true;：标记节点 t 已被加入到最小生成树中。
   • 内层循环 for (int j = 1; j <= n; j ++ )：更新其他节点到已选节点集合的距离。dist[j] = min(dist[j], w[t][j]); 表示对于每个节点 j，取其原来到已选节点集合的距离 dist[j] 和节点 t 到节点 j 的边权 w[t][j] 中的较小值，更新 dist[j]。
3. 返回结果：
   • return res;：返回最小生成树的边权总和。

（三）main 函数

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> w[i][j];

    cout << prim() << endl;

    return 0;
}

1. 输入图的信息：
   • cin >> n;：读取图的节点数量 n。
   • 通过两层循环 for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) 读取每两个节点之间边的权值，存储在邻接矩阵 w 中（cin >> w[i][j];）。
2. 计算并输出结果：
   • cout << prim() << endl;：调用 prim 函数计算最小生成树的边权总和，并输出结果。
3. 结束程序：
   • return 0;：程序正常结束。

四、时间复杂度和空间复杂度分析

（一）时间复杂度

1. 输入图的信息：通过两层循环读取边权值，时间复杂度为 (O(n^2))，其中 (n) 是节点数量。
2. Prim算法部分：外层循环 (n) 次，每次内层循环寻找最近节点和更新距离数组的操作时间复杂度都为 (O(n))，所以Prim算法的时间复杂度为 (O(n^2))。
3. 总体时间复杂度为 (O(n^2 + n^2) = O(n^2))。

（二）空间复杂度

1. 存储邻接矩阵：邻接矩阵 w[N][N] 占用空间为 (O(n^2))。
2. 存储距离数组和标记数组：距离数组 dist[N] 和标记数组 st[N] 占用空间均为 (O(n))，所以这部分空间复杂度为 (O(n + n) = O(n))。
3. 总体空间复杂度为 (O(n^2 + n) = O(n^2))，主要由存储邻接矩阵的空间占用决定。

希望以上题解能帮助你理解这道题的代码逻辑和Prim算法的实现细节。如果还有疑问，请随时提问。