最小生成樹c語言

以下是用C語言實現最小生成樹的示例代碼，使用了Prim算法：

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

#define MAX_VEX 10 // 最大頂點數

// 鄰接矩陣表示圖
int graph[MAX_VEX][MAX_VEX];

// 存儲最小生成樹權重的數組
int min_weight[MAX_VEX];

// 記錄最小生成樹權重的最大值
int max_weight = 0;

// 存儲已訪問的頂點數組
int visited[MAX_VEX];

// Prim算法求解最小生成樹
void prim(int n) {
    // 初始化已訪問數組和最小生成樹權重數組
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
        min_weight[i] = INT_MAX;
    }
    min_weight[0] = 0; // 將第一個頂點加入最小生成樹中
    for (int i = 0; i < n; i++) {
        int min = INT_MAX, j; // 初始化最小權重頂點為未知
        for (int k = 0; k < n; k++) {
            if (!visited[k] && (min > graph[i][k])) { // 如果當前頂點和未訪問頂點之間存在邊且權重小於當前最小權重，更新最小權重頂點
                min = graph[i][k];
                j = k;
            }
        }
        visited[j] = 1; // 將找到的頂點加入已訪問數組中
        min_weight[j] = min_weight[i] + graph[i][j]; // 將找到的邊加入最小生成樹權重數組中
        max_weight = max(max_weight, min_weight[j]); // 更新最大權重
    }
}

int main() {
    int n, m; // n為頂點數，m為邊數
    scanf("%d %d", &n, &m); // 輸入頂點數和邊數
    // 根據鄰接矩陣表示圖輸入每條邊的權重，邊數可按相同格式輸出最小生成樹的權重數組
    printf("最小生成樹的權重數組為：");
    for (int i = 0; i < n; i++) {
        printf("%d ", min_weight[i]); // 輸出最小生成樹的權重數組，第一個頂點權值為0，因為它是最小的生成樹的一部分
    }
    printf("\n"); // 換行符結束輸出結果
    printf("最小生成樹權重的最大值為：%d\n", max_weight); // 輸出最小生成樹權重的最大值
    return 0;
}

這段代碼使用鄰接矩陣表示圖，使用Prim算法求解最小生成樹。它首先初始化已訪問數組和最小生成樹權重數組，並將第一個頂點加入最小生成樹中。然後，它遍歷所有邊，對於每條邊，它找到未訪問的頂點和當前頂點之間的最小權重邊，並將其加入最小生成樹中。最後，它輸出最小生成樹的權重數組和最小生成樹權重的最大值。