最小生成树问题 Prim算法和Kruskal算法

Question

问题描述：给定一个地区的n个城市间的距离网，用Prim算法和Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。
基本要求：
1、城市间的距离网采用邻接表存储结构。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。
2、表示城市间距离网的邻接表（要求至少10个城市，15条边）C语言 要求两种算法分为两个功能模块写在同一个代码中 即含有菜单进行操作

Answer 1

引自强大而免费的微信小程序：皆我百晓生。

以下是一个使用Prim算法和Kruskal算法建立最小生成树的C语言代码示例：

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

// 定义城市的结构体
typedef struct City {
    int index;  // 城市的索引
    struct City* next;  // 下一个城市指针
    int cost;  // 城市之间的道路代价
} City;

// 定义最小生成树的边的结构体
typedef struct MSTEdge {
    int u, v;  // 边的两个顶点
    int cost;  // 边的代价
} MSTEdge;

// 使用邻接表存储距离网
City* createGraph() {
    int n = 10;  // 城市数量
    int m = 15;  // 边数量
    City* graph = (City*)malloc(n * sizeof(City));

    // 初始化城市
    for (int i = 0; i < n; i++) {
        graph[i].index = i;
        graph[i].next = NULL;
    }

    // 构造城市之间的道路
    int edges[][3] = {{0, 1, 2}, {0, 2, 4}, {0, 3, 1}, {1, 2, 1}, {1, 4, 4},
                      {2, 3, 3}, {2, 5, 2}, {3, 6, 3}, {4, 5, 1}, {4, 7, 5},
                      {5, 6, 2}, {5, 8, 3}, {6, 9, 4}, {7, 8, 2}, {8, 9, 3}};

    // 添加道路到邻接表
    for (int i = 0; i < m; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        int cost = edges[i][2];

        City* newCity = (City*)malloc(sizeof(City));
        newCity->index = v;
        newCity->cost = cost;
        newCity->next = graph[u].next;
        graph[u].next = newCity;

        // 无向图需要添加反向边
        newCity = (City*)malloc(sizeof(City));
        newCity->index = u;
        newCity->cost = cost;
        newCity->next = graph[v].next;
        graph[v].next = newCity;
    }

    return graph;
}

// Prim算法生成最小生成树
int prim(City* graph, int n) {
    int mstCost = 0;  // 最小生成树的代价
    int* visited = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        visited[i] = 0;  // 初始化所有城市为未访问状态
    }

    visited[0] = 1;  // 从第一个城市开始
    int count = 1;
    while (count < n) {
        int minCost = __INT_MAX__;
        int u, v;

        // 遍历所有已访问的城市
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                // 遍历与当前城市相邻的城市
                City* p = graph[i].next;
                while (p != NULL) {
                    if (!visited[p->index] && p->cost < minCost) {
                        minCost = p->cost;
                        u = i;
                        v = p->index;
                    }
                    p = p->next;
                }
            }
        }

        visited[v] = 1;  // 将v标记为已访问
        mstCost += minCost;

        printf("Add road between city %d and %d, cost: %d\n", u, v, minCost);

        count++;
    }

    free(visited);

    return mstCost;
}

// Kruskal算法生成最小生成树
int kruskal(City* graph, int n) {
    int mstCost = 0;
    int count = 0;

    // 创建边的数组
    MSTEdge* edges = (MSTEdge*)malloc(n * sizeof(MSTEdge));
    int* parent = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        parent[i] = i;  // 初始化每个城市的父节点为自身
    }

    // 遍历邻接表，将所有边加入边的数组中
    for (int u = 0; u < n; u++) {
        City* p = graph[u].next;
        while (p != NULL) {
            int v = p->index;
            int cost = p->cost;

            if (u < v) {  // 避免重复添加边
                edges[count].u = u;
                edges[count].v = v;
                edges[count].cost = cost;
                count++;
            }

            p = p->next;
        }
    }

    // 对边按代价从小到大排序
    for (int i = 0; i < count - 1; i++) {
        for (int j = 0; j < count - i - 1; j++) {
            if (edges[j].cost > edges[j + 1].cost) {
                MSTEdge temp = edges[j];
                edges[j] = edges[j + 1];
                edges[j + 1] = temp;
            }
        }
    }

    // 遍历边的数组，依次加入最小生成树
    for (int i = 0; i < count; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int cost = edges[i].cost;

        while (parent[u] != u) {
            u = parent[u];
        }
        while (parent[v] != v) {
            v = parent[v];
        }

        if (u != v) {  // 判断是否构成环
            parent[v] = u;  // 将v的父节点设为u
            mstCost += cost;
            printf("Add road between city %d and %d, cost: %d\n", edges[i].u, edges[i].v, cost);
        }
    }

    free(parent);
    free(edges);

    return mstCost;
}

int main() {
    City* graph = createGraph();

    int choice;
    int mstCost;

    do {
        printf("Menu:\n");
        printf("1. Prim algorithm\n");
        printf("2. Kruskal algorithm\n");
        printf("3. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                mstCost = prim(graph, 10);
                printf("Minimum Spanning Tree cost: %d\n", mstCost);
                break;
            case 2:
                mstCost = kruskal(graph, 10);
                printf("Minimum Spanning Tree cost: %d\n", mstCost);
                break;
            case 3:
                printf("Exiting...\n");
                break;
            default:
                printf("Invalid choice\n");
                break;
        }

        printf("\n");
    } while (choice != 3);

    free(graph);

    return 0;
}

这段代码使用邻接表存储地区的距离网，包括了两种算法的实现：Prim算法和Kruskal算法。菜单提供了选择使用哪种算法进行计算，并显示得到的最小生成树的道路和代价。