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

Prim算法是用来求解无向连通图的最小生成树的一种算法，其基本思想是从一个点开始，逐步将与该点相连的边加入最小生成树中，直到最终生成一棵最小生成树为止。下面是Prim算法用邻接矩阵存储图的实现：

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

#define MAX_VERTICES 100

int graph[MAX_VERTICES][MAX_VERTICES];
int visited[MAX_VERTICES];
int parent[MAX_VERTICES];
int key[MAX_VERTICES];

int get_min_key(int vertices)
{
    int min = INT_MAX, min_index, i;
    for (i = 0; i < vertices; i++) {
        if (!visited[i] && key[i] < min) {
            min = key[i];
            min_index = i;
        }
    }
    return min_index;
}

void prim(int vertices)
{
    int i, j, u;
    for (i = 0; i < vertices; i++) {
        visited[i] = 0;
        key[i] = INT_MAX;
    }
    key[0] = 0;
    parent[0] = -1;
    for (i = 0; i < vertices - 1; i++) {
        u = get_min_key(vertices);
        visited[u] = 1;
        for (j = 0; j < vertices; j++) {
            if (graph[u][j] && !visited[j] && graph[u][j] < key[j]) {
                parent[j] = u;
                key[j] = graph[u][j];
            }
        }
    }
}

void print_mst(int vertices)
{
    int i;
    printf("Edge  Weight\n");
    for (i = 1; i < vertices; i++) {
        printf("%d - %d    %d\n", parent[i], i, graph[i][parent[i]]);
    }
}

int main()
{
    int vertices, edges, i, j, v1, v2, weight;
    printf("Enter the number of vertices: ");
    scanf("%d", &vertices);
    printf("Enter the number of edges: ");
    scanf("%d", &edges);
    for (i = 0; i < vertices; i++) {
        for (j = 0; j < vertices; j++) {
            graph[i][j] = 0;
        }
    }
    printf("Enter the edges and their weights:\n");
    for (i = 0; i < edges; i++) {
        scanf("%d%d%d", &v1, &v2, &weight);
        graph[v1][v2] = weight;
        graph[v2][v1] = weight;
    }
    prim(vertices);
    print_mst(vertices);
    return 0;
}

在这个实现中，我们使用了邻接矩阵来存储图。首先，我们初始化了visited、key和parent数组，将visited数组设置为0，key数组设置为INT_MAX，parent数组设置为-1。然后，我们将key[0]设置为0，因为我们从第一个点开始构建最小生成树。接下来，我们使用get_min_key函数来获取key数组中的最小值（即未访问的最小的边权重），然后将其标记为visited。然后，我们遍历与该节点相连的所有节点，并更新key数组和parent数组。最后，我们使用print_mst函数来输出最小生成树。

这就是Prim算法用邻接矩阵存储图的实现。