c++实现用邻接矩阵存储的图的最小生成树Prim算法

Prim算法是求解最小生成树问题的一种贪心算法，可以使用邻接矩阵来存储图。具体实现步骤如下：

1. 初始化：选择一个起点，将其加入到最小生成树中，将其与其它节点的距离（边权）存入一个数组dist中，将其它节点的前驱节点存入一个数组pre中，将起点的前驱节点设为-1，表示当前点为起点。

2. 重复以下步骤，直到所有节点都被加入到最小生成树中：

a. 找到距离最小的未加入节点v，将其加入到最小生成树中。

b. 更新dist和pre数组，将v与其它未加入节点u之间的距离（边权）与dist[u]比较，若小于dist[u]，则更新dist[u]和pre[u]。

最终得到的pre数组就是最小生成树的构建过程，代码实现如下：

#include <stdio.h>
#include <limits.h>

#define MAX_VERTICES 100

int graph[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵表示的图
int dist[MAX_VERTICES]; // 存储节点到最小生成树的距离
int pre[MAX_VERTICES]; // 存储节点的前驱节点
int visited[MAX_VERTICES]; // 标记节点是否已加入到最小生成树中

int prim(int n) // n为节点数
{
    int i, j;
    int min_dist, u, v;
    int total_weight = 0;

    for (i = 0; i < n; i++) {
        dist[i] = INT_MAX;
        pre[i] = -1;
        visited[i] = 0;
    }

    dist[0] = 0;

    for (i = 0; i < n; i++) {
        min_dist = INT_MAX;
        for (j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                u = j;
            }
        }
        visited[u] = 1;
        total_weight += min_dist;
        for (v = 0; v < n; v++) {
            if (!visited[v] && graph[u][v] < dist[v]) {
                dist[v] = graph[u][v];
                pre[v] = u;
            }
        }
    }

    return total_weight;
}

int main()
{
    int n, m;
    int i, j, u, v, w;

    scanf("%d%d", &n, &m);

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            graph[i][j] = INT_MAX;
        }
    }

    for (i = 0; i < m; i++) {
        scanf("%d%d%d", &u, &v, &w); // 输入边的起点、终点、边权
        graph[u][v] = graph[v][u] = w; // 无向图，所以要将两个方向的边都存储
    }

    printf("Total weight of minimum spanning tree: %d\n", prim(n));

    return 0;
}