本專欄持續輸出數據結構題目集，歡迎訂閱。

題目

請編寫程序，實現在帶權的無向圖中求最小生成樹的 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;
}