C語言貪心算法實現：Kruskal 算法求最小生成樹（MST）

編輯：關於C語言

算法核心思想

Kruskal 算法：將所有邊按權重升序排序，依序嘗試加入生成樹，若加入不形成環（即兩端點屬於不同連通分量），則保留該邊。使用並查集（或本例簡化的分量標記陣列）維護連通性。

資料結構

#define MAX 100
typedef struct {
    int u, v;      // 邊的兩端點
    int weight;    // 權重
} edge;

edge edges[MAX];   // 所有邊
int nodes[MAX];    // 節點所屬分量標記 (0=未分派)

快速排序實現

void interchange(edge *m, edge *n) { edge t=*m; *m=*n; *n=t; }

int partition(edge a[], int p, int q) {
    int i=p, j=q+1;
    while (1) {
        do i++; while (a[i].weight < a[p].weight && i<q);
        do j--; while (a[j].weight > a[p].weight);
        if (i<j) interchange(&a[i], &a[j]); else break;
    }
    interchange(&a[p], &a[j]);
    return j;
}

void quicksort(edge a[], int p, int q) {
    if (p<q) {
        int j = partition(a, p, q);
        quicksort(a, p, j-1);
        quicksort(a, j+1, q);
    }
}

主流程

int main() {
    int nodenum, edgenum;
    scanf("%d%d", &nodenum, &edgenum);
    for (int i=0; i<edgenum; i++)
        scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].weight);

    for (int i=1; i<=nodenum; i++) nodes[i]=0;
    quicksort(edges, 0, edgenum-1);

    int flag=1, presult=0, cost=0;
    for (int i=0; i<edgenum; i++) {
        int m=edges[i].u, n=edges[i].v, safe=0;

        if (nodes[m]==0 && nodes[n]==0) {           // 兩點皆新
            nodes[m]=nodes[n]=flag++; safe=1;
        } else if (nodes[m]==0 || nodes[n]==0) {    // 一點新
            if (nodes[m]==0) nodes[m]=nodes[n];
            else nodes[n]=nodes[m];
            safe=1;
        } else if (nodes[m] != nodes[n]) {          // 兩點屬不同分量，合併
            int old = nodes[m];
            for (int j=1; j<=nodenum; j++)
                if (nodes[j]==old || nodes[j]==nodes[n])
                    nodes[j]=flag;
            nodes[m]=nodes[n]=flag++;
            safe=1;
        }

        if (safe) {
            edges[presult++] = edges[i];
            if (presult == nodenum-1) break;        // MST 完成
        }
    }

    printf("MST 邊:\\n起點 終點 權重\\n");
    for (int i=0; i<presult; i++) {
        printf("%d %d %d\\n", edges[i].u, edges[i].v, edges[i].weight);
        cost += edges[i].weight;
    }
    printf("最小權重和: %d\\n", cost);
    return 0;
}