m0_74003140 2023-12-08 09:44 采纳率: 0%
浏览 21
已结题

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

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

  • 写回答

20条回答 默认 最新

  • 专家-赤兔[在线] 2023-12-08 09:45
    关注
    获得0.60元问题酬金

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

    以下是一个使用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算法。菜单提供了选择使用哪种算法进行计算,并显示得到的最小生成树的道路和代价。

    评论 编辑记录

报告相同问题?

问题事件

  • 系统已结题 12月16日
  • 修改了问题 12月8日
  • 修改了问题 12月8日
  • 创建了问题 12月8日

悬赏问题

  • ¥55 AD844 howland电流源如何驱动大额负载
  • ¥15 C++ /QT 内存权限的判断函数列举
  • ¥15 深度学习GFnet理解问题
  • ¥15 单细胞小提琴堆叠图代码
  • ¥50 升级strust2版本到2.3.15.1后使用ognl3.0.6.jar windows环境中没有问题,但部署到linux环境报错
  • ¥15 vue页面,node封装接口
  • ¥15 求TMS320F280039C工程模板!
  • ¥15 delphi+fastreport实现分组补空打印问题
  • ¥15 使用python把两台mysql数据库服务器数据导出和导入
  • ¥15 NodeBB论坛配置Apache Solr中文搜索引擎的详细教程