最小生成树Kruskal算法

Question

如图为一个城市连接图，现要设计一条高铁贯通所有城市（即从任一城市可以到达其它任何城市，用Kruskal算法设计一条代价最小的线路，写出完整的程序。图中权值表示两城市之间的里程（单位为100km，假设每公里的高铁造价为3000万元）。

Answer 1

引自免费微信小程序：皆我百晓生

为了实现Kruskal算法，我们首先需要定义一些数据结构：一个表示边的结构体、一个用于排序的优先队列以及一个表示集合的数据结构（这里我们可以选择并查集）。接下来，我们将编写实现这些功能的函数，并最终完成Kruskal算法的主要部分。

以下是C语言代码实现：

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

#define MAX_NODES 100
#define INF 99999

// 边的结构体
typedef struct Edge {
    int src, dest;
    int weight;
} Edge;

// 优先队列（使用最小堆）
typedef struct MinHeap {
    int capacity;
    int size;
    Edge* heap[MAX_NODES];
} MinHeap;

// 并查集
typedef struct UnionFind {
    int parent[MAX_NODES];
} UnionFind;

void init_uf(UnionFind* uf) {
    for (int i = 0; i < MAX_NODES; ++i) {
        uf->parent[i] = i;
    }
}

int find(UnionFind* uf, int node) {
    if (uf->parent[node] != node) {
        uf->parent[node] = find(uf, uf->parent[node]);
    }
    return uf->parent[node];
}

void union_set(UnionFind* uf, int x, int y) {
    int rootX = find(uf, x);
    int rootY = find(uf, y);

    if (rootX != rootY) {
        uf->parent[rootX] = rootY;
    }
}

void insert_heap(MinHeap* heap, Edge edge) {
    heap->heap[heap->size++] = edge;
    int curr = heap->size - 1;
    while (curr > 0 && heap->heap[curr].weight < heap->heap[(curr - 1) / 2].weight) {
        Edge temp = heap->heap[curr];
        heap->heap[curr] = heap->heap[(curr - 1) / 2];
        heap->heap[(curr - 1) / 2] = temp;
        curr = (curr - 1) / 2;
    }
}

Edge extract_min(MinHeap* heap) {
    Edge min_edge = heap->heap[0];
    heap->heap[0] = heap->heap[--heap->size];
    int curr = 0;
    while (curr * 2 + 1 < heap->size) {
        int child = curr * 2 + 1;
        if ((child + 1 < heap->size) && heap->heap[child + 1].weight < heap->heap[child].weight) {
            child++;
        }
        if (heap->heap[child].weight <= heap->heap[curr].weight) {
            break;
        } else {
            Edge temp = heap->heap[curr];
            heap->heap[curr] = heap->heap[child];
            heap->heap[child] = temp;
            curr = child;
        }
    }
    return min_edge;
}

void kruskal(int n, Edge edges[], int m) {
    int total_cost = 0;
    UnionFind uf;
    init_uf(&uf);

    MinHeap min_heap;
    min_heap.capacity = m;
    min_heap.size = 0;

    for (int i = 0; i < m; ++i) {
        insert_heap(&min_heap, edges[i]);
    }

    while (min_heap.size > 0 && uf.size < n - 1) {
        Edge edge = extract_min(&min_heap);
        int rootX = find(&uf, edge.src);
        int rootY = find(&uf, edge.dest);

        if (rootX != rootY) {
            total_cost += edge.weight;
            union_set(&uf, rootX, rootY);
        }
    }

    printf("Minimum cost to build the高铁 network: %d million yuan\n", total_cost * 3000);
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    Edge edges[m];

    // Read the edges and their weights from input
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &edges[i].src, &edges[i].dest);
        edges[i].weight = abs(edges[i].src - edges[i].dest); // Assuming weights are already given in km
    }

    kruskal(n, edges, m);

    return 0;
}

这段代码实现了Kruskal算法，你需要在main()函数中读取输入数据（城市数量n，边的数量m以及每条边的起始点和终点），然后调用kruskal()函数计算最小生成树的总成本。

注意：这个程序假设了输入已经按照边的权重进行排序。在实际应用中，可能需要先对输入的边进行排序，然后再执行Kruskal算法。在这个例子中，由于权重已经是两城市间的距离，因此不需要额外的排序步骤。

为了测试此代码，你需要提供一个包含城市数量、边的数量以及每条边的起点和终点的输入文件，例如：

4 6
0 1
1 2
2 3
0 2
1 3
3 2

这段输入表示有4个城市（编号为0到3），共6条边。运行程序后，它将输出最小生成树的总成本。