C语言实用数据结构与算法

Question

实用数据结构与算法C语言版，‘’图‘’的内容，最优灌溉问题。要求如上图，请教一下

Answer 1

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

为了实现 Prim 和 Kruskal 算法，我们首先需要定义一个结构体来表示边（包括起始节点、结束节点和费用），以及一个数组来存储这些边。然后，我们将使用两个辅助函数，一个用于检查两个节点是否在一个集合中（对于 Prim 算法），另一个用于合并两个集合（对于 Kruskal 算法）。这里是一个详细的 C 语言实现：

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

// 定义边的数据结构
typedef struct Edge {
    int src, dest;
    int cost;
} Edge;

// 初始化并查找操作
int find(int parent[], int i) {
    if (parent[i] == i)
        return i;
    return find(parent, parent[i]);
}

// 合并操作
void union_op(int parent[], int rank[], int x, int y) {
    x = find(parent, x);
    y = find(parent, y);

    if (rank[x] > rank[y])
        parent[y] = x;
    else {
        parent[x] = y;
        if (rank[x] == rank[y])
            rank[y]++;
    }
}

// Prim 算法
int primMST(Edge* edges, int n, int m) {
    int minimum_cost = 0;
    int parent[n + 1];
    int visited[n + 1]; // 标记已访问的节点
    int min_edge_cost; // 当前找到的最小边的成本

    for (int i = 1; i <= n; i++) {
        parent[i] = -1;
        visited[i] = 0;
    }

    visited[1] = 1; // 假设第1个节点是根节点

    for (int count = 0; count < n - 1; count++) {
        min_edge_cost = INT_MAX;
        int u = -1;

        for (int i = 0; i < m; i++) {
            int v = edges[i].dest;
            if ((visited[v] == 0) && (edges[i].cost < min_edge_cost)) {
                min_edge_cost = edges[i].cost;
                u = edges[i].src;
            }
        }

        visited[u] = 1;
        minimum_cost += min_edge_cost;
        for (int j = 0; j < m; j++) {
            int v = edges[j].dest;
            if ((visited[v] == 0) && (edges[j].src == u))
                parent[v] = u;
        }
    }

    return minimum_cost;
}

// Kruskal 算法
int kruskalMST(Edge* edges, int n, int m) {
    int minimum_cost = 0;
    int parent[n + 1];
    int rank[n + 1];

    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

    Edge* sortedEdges = malloc(m * sizeof(Edge));
    memcpy(sortedEdges, edges, m * sizeof(Edge));

    // 对边按费用排序
    for (int i = 0; i < m; i++)
        for (int j = i + 1; j < m; j++)
            if (sortedEdges[i].cost > sortedEdges[j].cost) {
                Edge temp = sortedEdges[i];
                sortedEdges[i] = sortedEdges[j];
                sortedEdges[j] = temp;
            }

    for (int i = 0; i < m; i++) {
        int x = find(parent, sortedEdges[i].src);
        int y = find(parent, sortedEdges[i].dest);

        if (x != y) {
            minimum_cost += sortedEdges[i].cost;
            union_op(parent, rank, x, y);
        }
    }

    free(sortedEdges);

    return minimum_cost;
}

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

    Edge edges[m];
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &edges[i].src, &edges[i].dest, &edges[i].cost);
    }

    printf("Minimum cost using Prim's algorithm: %d\n", primMST(edges, n, m));
    printf("Minimum cost using Kruskal's algorithm: %d\n", kruskalMST(edges, n, m));

    return 0;
}

这段代码首先读取输入数据，然后调用 Prim 和 Kruskal 算法计算最小生成树的最小成本，并将结果打印到控制台上。

请注意，这个程序没有处理错误输入的情况，例如输入的边数量超过实际可能的最大值（n*(n-1)/2）。在实际应用中，你应该添加适当的错误检查和异常处理代码。