最小生成樹c程式

在C語言中，最小生成樹（Minimum Spanning Tree, MST）的算法可以通過Prim算法或Kruskal算法來實現。這裡我將為你提供一個簡單的Prim算法的C程式範例。

Prim算法的基本思想是從圖中的一個特定的頂點開始，逐漸將整個圖包含進來，每次選擇連接已經包含頂點的邊中權值最小的邊。

以下是一個簡單的Prim算法的C程式範例：

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

#define MAX_VERTICES 100

// 頂點結構體
typedef struct Vertex {
    int key; // 頂點的關鍵值
    int parent; // 父頂點
} Vertex;

// 邊結構體
typedef struct Edge {
    int src; // 源頂點
    int dest; // 目標頂點
    int weight; // 邊的權重
} Edge;

// 圖結構體
typedef struct Graph {
    int V; // 頂點數量
    int E; // 邊數量
    Edge *edges; // 邊的陣列
} Graph;

// 初始化頂點陣列
Vertex *createVertexArray(int V) {
    Vertex *arr = malloc(V * sizeof(Vertex));
    for (int i = 0; i < V; i++) {
        arr[i].key = INT_MAX;
        arr[i].parent = -1;
    }
    return arr;
}

// 初始化邊陣列
Edge *createEdgeArray(int E) {
    Edge *arr = malloc(E * sizeof(Edge));
    for (int i = 0; i < E; i++) {
        arr[i].weight = 0;
    }
    return arr;
}

// 輸入圖的邊
void inputEdges(Graph *graph) {
    int src, dest, weight;
    printf("Enter the number of edges: ");
    scanf("%d", &graph->E);
    for (int i = 0; i < graph->E; i++) {
        printf("Enter the source, destination and weight of edge %d: ", i + 1);
        scanf("%d %d %d", &src, &dest, &weight);
        graph->edges[i].src = src - 1;
        graph->edges[i].dest = dest - 1;
        graph->edges[i].weight = weight;
    }
}

// Prim算法
void primMST(Graph *graph, int start) {
    int V = graph->V;
    Vertex *arr = createVertexArray(V);
    bool *visited = malloc(V * sizeof(bool));
    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }
    arr[start].key = 0;
    for (int count = 0; count < V - 1; count++) {
        int u = -1;
        for (int v = 0; v < V; v++) {
            if (!visited[v] && (u == -1 || arr[v].key < arr[u].key)) {
                u = v;
            }
        }
        visited[u] = true;
        for (int v = 0; v < V; v++) {
            if (!visited[v] && graph->edges[v * V + u].weight < INT_MAX && graph->edges[v * V + u].weight < arr[u].key) {
                arr[v].key = graph->edges[v * V + u].weight;
                arr[v].parent = u;
            }
        }
    }
    printf("The Minimum Spanning Tree is: \n");
    printMST(graph, arr, start);
    free(visited);
    free(arr);
}

// 列印最小生成樹
void printMST(Graph *graph, Vertex *arr, int start) {
    int V = graph->V;
    printf("%d ", start);
    for (int count = 0; count < V - 1; count++) {
        int u = start;
        int v = arr[u].parent;
        printf("->%d ", v + 1);
        start = v;
    }
    printf("\n");
}

int main() {
    int V, E;
    printf("Enter the number of vertices: ");
    scanf("%d", &V);
    printf("Enter the number of edges: ");
    scanf("%d", &E);

    // 創建圖
    Graph *graph = malloc(1 * sizeof(Graph));
    graph->V = V;
    graph->E = E;
    graph->edges = createEdgeArray(V * V);
    inputEdges(graph);

    // 最小生成樹
    primMST(graph, 0);

    return 0;
}

這個程式首先要求用戶輸入圖的頂點數量和邊數量，然後讓用戶輸入邊的資訊。接著，程式使用Prim算法來構建最小生成樹，並列印出結果。

請注意，這個程式假設邊的權重都是正整數，並且邊的數量不會超過頂點數量的平方。如果你需要處理更一般的圖，你可能需要對程式進行修改。