Prim算法求解最小生成树的贪心算法c语言实现

Prim算法是一种求解最小生成树的贪心算法，它的C语言实现如下：

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

#define MAX_VERTICES 1000

typedef struct {
    int vertex;
    int weight;
} Edge;

typedef struct {
    int num_vertices;
    int num_edges;
    int adj_matrix[MAX_VERTICES][MAX_VERTICES];
} Graph;

void prim(Graph *g, int start_vertex) {
    int selected[MAX_VERTICES] = {0};
    Edge edges[MAX_VERTICES];
    int num_edges = 0;
    int total_weight = 0;
    int current_vertex, i, j, min_weight, next_vertex;

    for (i = 0; i < g->num_vertices; i++) {
        edges[i].vertex = start_vertex;
        edges[i].weight = g->adj_matrix[start_vertex][i];
    }

    selected[start_vertex] = 1;

    for (i = 0; i < g->num_vertices - 1; i++) {
        min_weight = INT_MAX;
        for (j = 0; j < g->num_vertices; j++) {
            if (selected[j]) {
                for (int k = 0; k < g->num_vertices; k++) {
                    if (!selected[k] && g->adj_matrix[j][k]) {
                        if (min_weight > g->adj_matrix[j][k]) {
                            min_weight = g->adj_matrix[j][k];
                            current_vertex = j;
                            next_vertex = k;
                        }
                    }
                }
            }
        }
        selected[next_vertex] = 1;
        edges[num_edges++] = (Edge){next_vertex, min_weight};
        total_weight += min_weight;
    }

    printf("Minimum Spanning Tree:\n");
    for (i = 0; i < num_edges; i++) {
        printf("(%d, %d) weight=%d\n", edges[i].vertex, edges[i].weight);
    }
    printf("Total weight: %d\n", total_weight);
}

int main() {
    Graph g = {
        .num_vertices = 5,
        .num_edges = 7,
        .adj_matrix = {
            {0, 1, 2, 0, 0},
            {1, 0, 3, 4, 0},
            {2, 3, 0, 5, 6},
            {0, 4, 5, 0, 7},
            {0, 0, 6, 7, 0}
        }
    };

    prim(&g, 0);

    return 0;
}

该实现使用了邻接矩阵来表示图，其中`num_vertices`表示顶点数，`num_edges`表示边数，`adj_matrix`表示邻接矩阵。`prim`函数接受一个图和一个起始顶点作为参数，它使用一个`selected`数组来记录哪些顶点已经被加入到最小生成树中，使用一个`edges`数组来记录已经加入到最小生成树中的边，使用`num_edges`来记录已经加入到最小生成树中的边数，使用`total_weight`来记录最小生成树的总权值。在算法的主循环中，每次找到一个权值最小的边，并将其加入到最小生成树中。最后，输出最小生成树的边和总权值。