图的最小生成树

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

// 图的最大顶点数量
#define MAXVER 100
// 定义无穷大，表示两个点之间没有边
#define INF INT_MAX

//weights：邻接矩阵，表示边权重
//n：顶点数量
//src：起始顶点
//edges：记录每个点连接到当前生成树的最小边的另一个端点（即前驱）

void Prim(int weights[][MAXVER], int n, int src, int edges[])
{
    int minweight[MAXVER], min;
    for (int i = 0; i < n; i++) {
        // 初始化每个点到源点的边权
        minweight[i] = weights[src][i];
        // 初始每个点的前驱设为源点
        edges[i] = src;
    }
    // 源点加入生成树，设为0表示已访问
    minweight[src] = 0;

    for (int i = 1; i < n; i++) {
        min = INF;
        int k = 0;
        // 找出权重最小的未加入树的顶点
        for (int j = 0; j < n; j++) {
            if (minweight[j] != 0 && minweight[j] < min) {
                min = minweight[j];
                k = j;
            }
        }

        minweight[k] = 0;

        // 用新加入的顶点 k 更新其他顶点的最小权重
        for (int j = 0; j < n; j++) {
            if (minweight[j] != 0 && weights[k][j] < minweight[j]) {
                minweight[j] = weights[k][j];
                edges[j] = k;
            }
        }
    }
}

int cmp(const void* a, const void* b)
{
    int al = *(const int*)a;
    int bl = *(const int*)b;
    return al - bl;
}

int main(void)
{
    int n, e;
    scanf("%d %d", &n, &e);
    //初始化邻接矩阵和边编号表
    int weight[MAXVER][MAXVER];
    int edge_id[MAXVER][MAXVER];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            weight[i][j] = INF;
            edge_id[i][j] = -1;
        }
    }

    for (int k = 0; k < e; k++) {
        int id, u, v, w;
        scanf("%d %d %d %d", &id, &u, &v, &w);
        if (w < weight[u][v]) {
            weight[u][v] = w;
            edge_id[u][v] = id;
            weight[v][u] = w;
            edge_id[v][u] = id;
        }
    }

    int src = 0;
    int edges[MAXVER];
    Prim(weight, n, src, edges);

    int selected_edges[MAXVER];
    int count = 0;
    int sum = 0;

    for (int j = 0; j < n; j++) {
        if (j == src)
            continue;
        int k = edges[j];
        sum += weight[k][j];
        selected_edges[count++] = edge_id[k][j];
    }

    qsort(selected_edges, count, sizeof(int), cmp);

    printf("%d\n", sum);
    for (int i = 0; i < count; i++) {
        printf("%d ", selected_edges[i]);
    }
    printf("\n");

    return 0;
}