本专栏持续输出数据结构题目集，欢迎订阅。

题目

请编写程序，实现在带权的无向图中求最小生成树的 Prim 算法。
注意：当多个待收录顶点到当前点集的距离等长时，按编号升序进行收录。

输入格式：
输入首先在第一行给出两个正整数，依次为当前要创建的图的顶点数 n（≤100）和边数 m。
随后 m 行，每行给出一条无向边两端点的编号、权重。顶点编号从 0 开始，权重（≤100）为整数。同行数字均以一个空格分隔。

输出格式：
参考样例。
首先在一行中输出 total weight = x，其中 x 为最小生成树中所有边的总权重。如果最小生成树不存在，则 x 为 −1。
随后在一行中按顶点编号升序输出每个顶点在最小生成树中的父结点的编号。为输出简单起见，每个数字后有一个空格。
注意：此处默认顶点 0 为最小生成树的根结点，其父结点编号规定为 −1。算法初始化时，所有顶点（除了根结点）的父结点编号默认为 0。

输入样例 1：
6 9
0 1 1
0 2 3
1 2 6
1 3 2
2 3 7
2 4 5
2 5 4
3 5 8
4 5 1

输出样例 1：
total weight = 11
-1 0 0 1 5 2

输入样例 2：
7 9
0 1 1
0 2 3
1 2 6
1 3 2
2 3 7
2 4 5
2 5 4
3 5 8
4 5 1

输出样例 2：
total weight = -1
-1 0 0 1 5 2 0

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_VERTICES 100
#define INF 999999999int main() {int n, m;int graph[MAX_VERTICES][MAX_VERTICES];int dist[MAX_VERTICES];int parent[MAX_VERTICES];int visited[MAX_VERTICES];// 初始化图for (int i = 0; i < MAX_VERTICES; i++) {for (int j = 0; j < MAX_VERTICES; j++) {graph[i][j] = INF;}}// 读取顶点数和边数scanf("%d %d", &n, &m);// 读取每条边的信息for (int i = 0; i < m; i++) {int u, v, weight;scanf("%d %d %d", &u, &v, &weight);graph[u][v] = weight;graph[v][u] = weight;}// 初始化距离数组和父结点数组for (int i = 0; i < n; i++) {dist[i] = INF;parent[i] = 0;  // 默认父结点为0visited[i] = 0;}// 从顶点0开始dist[0] = 0;parent[0] = -1;  // 根结点的父结点为-1// Prim算法核心for (int i = 0; i < n; i++) {// 选择距离最小且未被访问的顶点int min_dist = INF;int u = -1;for (int j = 0; j < n; j++) {if (!visited[j] && dist[j] < min_dist) {min_dist = dist[j];u = j;} else if (!visited[j] && dist[j] == min_dist && j < u) {// 当距离相同时，选择编号较小的顶点u = j;}}// 如果找不到符合条件的顶点，说明图不连通if (u == -1) {break;}visited[u] = 1;// 更新与u相邻的顶点的距离for (int v = 0; v < n; v++) {if (!visited[v] && graph[u][v] != INF && graph[u][v] < dist[v]) {dist[v] = graph[u][v];parent[v] = u;}}}// 计算总权重并检查是否存在最小生成树int total_weight = 0;int all_visited = 1;for (int i = 0; i < n; i++) {if (!visited[i]) {all_visited = 0;break;}if (i != 0) {  // 根结点的边不计入总权重total_weight += dist[i];}}// 输出结果if (all_visited) {printf("total weight = %d\n", total_weight);} else {printf("total weight = -1\n");}// 输出每个顶点的父结点for (int i = 0; i < n; i++) {printf("%d ", parent[i]);}printf("\n");return 0;
}