【图的应用一：最小生成树】- 用 C 语言实现普里姆算法

目录

一、最小生成树 

二、普里姆算法的构造过程

三、普里姆算法的实现

 

一、最小生成树 

假设要在 n 个城市之间建立通信联络网，则连通 n 个城市只需要 n - 1 条线路。这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。

在每两个城市之间都可设置一条线路，相应地都要付出一定的经济代价。n 个城市之间，最多可能设置 ​ C_n^2 = \dfrac{n(n - 1)}{2} 条线路，那么如何在这些可能的线路中选择 n - 1 条，以使总的耗费最少呢？

可以用连通网来表示 n 个城市，以及 n 个城市间可能设置的通信路线，其中网的顶点表示城市，边表示两城市之间的线路，赋予边的权值表示相应的代价。对于 n 个顶点的连通网可以建立许多不同的生成树，每一颗生成树都可以是一个通信网，最合理的通信网应该是各边代价之和最小的那颗生成树，称为连通网的最小代价生成树（Minimum Cost Spanning Tree），简称最小生成树。

构造最小生成树有多种算法，其中多数算法利用了最小生成树的下列一种简称为 MST 的性质：

假设 N = (V, E) 是一个连通网，U 是顶点集 V 的一个非空真子集。若 (u, v) 是 N 中所有的一个顶点在 U（u \in U​）中，另一个顶点在 V - U（​v \in V - U）中的边里，具有最小权值的一条边，则必存在一棵包含边 (u, v) 的最小生成树。

可以用反证法来证明：

假设网 N 的任何一棵最小生成树都不包含边 (u, v)，T 是连通网上的一棵最小生成树，由生成树的定义可知，T 中必存在一条从 u 到 v 的路径 P，且在 P 上必存在一条边 (u', v')，其中 u' \in U, v' \in V - U​。

当将边 (u, v) 加入到 T 中时，(u, v) 和 P 构成了一条回路，删去 (u', v') 便可消除回路，同时得到另一颗生成树 T‘。因为 (u, v) 的权值不高于 (u', v')，所以 T' 的权值亦不高于 T，那么 T’ 是包含 (u, v) 的一棵最小生成树，和假设矛盾。

普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法是两个利用 MST 性质构造最小生成树的算法。

二、普里姆算法的构造过程

假设 N = (V, E) 是连通网，TE 是 N 上最小生成树中边的集合。

  1. U = \{u_0\}(u_0 \in V), TE = \{\}​。

  2. 在所有 ​u \in U, v \in V - U 的边 (u, v) \in E 中找一条权值最小的边 (u_0, v_0) 并入集合 TE，同时 ​v_0 并入 U。

  3. 重复 2，直至 U = V 为止。

此时 TE 中必有 n - 1 条边，则 T = (V, TE) 为 N 的最小生成树。

下图所示为一个连通网 G5 从 v1 开始构造最小生成树的例子。可以看出，普里姆算法逐步增加 U 中的顶点，可称为 "加点法"。

每次选择最小边时，可能存在多条同样权值的边可选，此时任选其一即可。

三、普里姆算法的实现

假设无向网 N 以邻接矩阵形式存储，从顶点 u 出发构造 N 的最小生成树 T，要求输出 T 的各条边。

为实现这个算法附设了两个辅助数组 lowcostArr 和 adjVexPosArr。对每个顶点 ，lowcostArr[i - 1] = Min{ cost​ }，即表示 N 中所有的一个顶点在 U 中，另一个顶点是 vi 的边里，最小边上的权值；adjVexPosArr[i - 1] 则表示那条最小边在 U 中的那个顶点在图中的位置。

AMGraph.h：

#pragma once
​
// 无向网
typedef char VertexType;
typedef int EdgeType;
​
#define DEFAULT_CAPACITY 2
​
typedef struct AMGraph
{
    VertexType* vertices;
    EdgeType** edges;
    int vSize;
    int eSize;
    int capacity;
}AMGraph;
​
// 基本操作
void AMGraphInit(AMGraph* pg);
​
void ShowAdjMatrix(AMGraph* pg);
​
int GetVertexPos(AMGraph* pg, VertexType v);
​
void InsertVertex(AMGraph* pg, VertexType v);
void InsertEdge(AMGraph* pg, VertexType v1, VertexType v2, EdgeType cost);
​
// 普里姆算法
void MiniSpanTree_Prim(AMGraph* pg, VertexType u);

AMGraph.c：

#include "AMGraph.h"
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
​
void AMGraphInit(AMGraph* pg)
{
    assert(pg);
    pg->vSize = pg->eSize = 0;
    pg->capacity = DEFAULT_CAPACITY;
    
    pg->vertices = (VertexType*)malloc(sizeof(VertexType) * pg->capacity);
    assert(pg->vertices);
​
    pg->edges = (EdgeType**)malloc(sizeof(EdgeType*) * pg->capacity);
    assert(pg->edges);
    for (int i = 0; i < pg->capacity; ++i)
    {
        pg->edges[i] = (EdgeType*)malloc(sizeof(EdgeType) * pg->capacity);
        assert(pg->edges[i]);
        for (int j = 0; j < pg->capacity; ++j)
        {
            if (i == j)
                  pg->edges[i][j] = 0;
            else
                  pg->edges[i][j] = INT_MAX;
        }
    }
}
​
void ShowAdjMatrix(AMGraph* pg)
{
    assert(pg);
    printf("  ");
    for (int i = 0; i < pg->vSize; ++i)
    {
        printf("%c ", pg->vertices[i]);
    }
    printf("\n");
​
    for (int i = 0; i < pg->vSize; ++i)
    {
        printf("%c ", pg->vertices[i]);
        for (int j = 0; j < pg->vSize; ++j)
        {
            if (pg->edges[i][j] == INT_MAX)
                printf("# ");  // 用 # 代替 ∞
            else
                printf("%d ", pg->edges[i][j]);
        }
        printf("\n");
    }
}
​
int GetVertexPos(AMGraph* pg, VertexType v)
{
    assert(pg);
    for (int i = 0; i < pg->vSize; ++i)
    {
        if (pg->vertices[i] == v)
            return i;
    }
    return -1;
}
​
void InsertVertex(AMGraph* pg, VertexType v)
{
    assert(pg);
    // 考虑是否需要扩容
    if (pg->vSize == pg->capacity)
    {
        VertexType* tmp1 = (VertexType*)realloc(pg->vertices, sizeof(VertexType) * 2 * pg->capacity);
        assert(tmp1);
        pg->vertices = tmp1;
​
        EdgeType** tmp2 = (EdgeType**)realloc(pg->edges, sizeof(EdgeType*) * 2 * pg->capacity);
        assert(tmp2);
        pg->edges = tmp2;
        for (int i = 0; i < pg->capacity; ++i)
        {
            EdgeType* tmp3 = (EdgeType*)realloc(pg->edges[i], sizeof(EdgeType) * 2 * pg->capacity);
            assert(tmp3);
            pg->edges[i] = tmp3;
            for (int j = pg->capacity; j < 2 * pg->capacity; ++j)
            {
                pg->edges[i][j] = INT_MAX;  
            }
        }
        for (int i = pg->capacity; i < 2 * pg->capacity; ++i)
        {
            pg->edges[i] = (EdgeType*)malloc(sizeof(EdgeType) * 2 * pg->capacity);
            assert(pg->edges[i]);
            for (int j = 0; j < 2 * pg->capacity; ++j)
            {
                if (i == j)
                    pg->edges[i][j] = 0;
                else
                    pg->edges[i][j] = INT_MAX;
            }
        }
​
        pg->capacity *= 2;
    }
    // 插入顶点
    pg->vertices[pg->vSize++] = v;
}
​
void InsertEdge(AMGraph* pg, VertexType v1, VertexType v2, EdgeType cost)
{
    assert(pg);
    int pos1 = GetVertexPos(pg, v1);
    int pos2 = GetVertexPos(pg, v2);
    if (pos1 == -1 || pos2 == -1)
        return;
​
    if (pg->edges[pos1][pos2] != INT_MAX)
        return;
​
    pg->edges[pos1][pos2] = pg->edges[pos2][pos1] = cost;
    ++pg->eSize;
}
​
// 普里姆算法的实现
void MiniSpanTree_Prim(AMGraph* pg, VertexType u)
{
    assert(pg);
    EdgeType* lowcostArr = (EdgeType*)malloc(sizeof(EdgeType) * pg->vSize);
    int* adjVexPosArr = (int*)malloc(sizeof(int) * pg->vSize);
    assert(lowcostArr && adjVexPosArr);
​
    int pos = GetVertexPos(pg, u);
    if (pos == -1)
        return;
    
    for (int i = 0; i < pg->vSize; ++i)
    {
        if (i != pos)
        {
            lowcostArr[i] = pg->edges[pos][i];
            adjVexPosArr[i] = pos;
        }
        else
        {
            lowcostArr[i] = 0;  // 初始，U = {u}
        }
    }
    
    // 选择其余 pg->vSize - 1 个顶点，生成 pg->vSize - 1 条边
    for (int i = 0; i < pg->vSize - 1; ++i)
    {
        EdgeType min = INT_MAX;
        int minIndex = -1;
        for (int j = 0; j < pg->vSize; ++j)
        {
            if (lowcostArr[j] != 0 && lowcostArr[j] < min)
            {
                min = lowcostArr[j];
                minIndex = j;
            }
        }
        printf("(%c, %c)\n", pg->vertices[adjVexPosArr[minIndex]], pg->vertices[minIndex]);
        lowcostArr[minIndex] = 0;  // 将顶点并入 U 
​
        for (int j = 0; j < pg->vSize; ++j)
        {
            if (pg->edges[minIndex][j] < lowcostArr[j])
            {
                lowcostArr[j] = pg->edges[minIndex][j];
                adjVexPosArr[j] = minIndex;
            }
        }
    }
    
    free(lowcostArr);
    free(adjVexPosArr);
}

Test.c：

#include "AMGraph.h"
#include <stdio.h>
​
int main()
{
    AMGraph g;
    AMGraphInit(&g);
    InsertVertex(&g, 'A');
    InsertVertex(&g, 'B');
    InsertVertex(&g, 'C');
    InsertVertex(&g, 'D');
    InsertVertex(&g, 'E');
    InsertVertex(&g, 'F');
    InsertEdge(&g, 'A', 'B', 6);
    InsertEdge(&g, 'A', 'C', 1);
    InsertEdge(&g, 'A', 'D', 5);
    InsertEdge(&g, 'B', 'C', 5);
    InsertEdge(&g, 'B', 'E', 3);
    InsertEdge(&g, 'C', 'D', 5);
    InsertEdge(&g, 'C', 'E', 6);
    InsertEdge(&g, 'C', 'F', 4);
    InsertEdge(&g, 'D', 'F', 2);
    InsertEdge(&g, 'E', 'F', 6);
    ShowAdjMatrix(&g);
    printf("\n");
​
    MiniSpanTree_Prim(&g, 'A');
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/251407.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

针对网页html中插入动图gif不能循环播放只播放一次的解决方案

针对网页html中插入动图gif不能循环播放只播放一次的解决方案

针对网页html中插入动图gif不能循环播放只播放一次的解决方案 原因分析解决方案 原因分析 使用图片编辑软件制作的过程中未启用“循环播放”功能&#xff0c;这里以Photoshop为例&#xff0c;演示设置GIF图片循环播放的操作流程&#xff1a;所需材料&#xff1a;PS。第一步&am…
阅读更多...
使用Audition录制电脑内部声音

使用Audition录制电脑内部声音

在电脑上播放的媒体文件&#xff0c;包括视频和声音&#xff0c;很多是可以播放却无法保存的。例如一些网页播放的视频&#xff0c;或者在线播放的音乐。 视频的话&#xff0c;可以使用工具来截图&#xff0c;抓取GIF或录屏。 声音的话&#xff0c;也可以使用工具进行录制。这里…
阅读更多...
【算法刷题】Day17

【算法刷题】Day17

文章目录 1. 不同路径 II题干&#xff1a;算法原理&#xff1a;代码&#xff1a; 2. 在排序数组中查找元素的第一个和最后一个位置题干&#xff1a;算法原理&#xff1a;解法一&#xff1a;暴力解法 O(n)解法二&#xff1a;朴素二分解法三&#xff1a;查找区间左右端点 代码&am…
阅读更多...
redis未授权漏洞复现

redis未授权漏洞复现

什么是redis redis就是个数据库&#xff0c;跟mysql不同的地方在于redis主要将数据存在内存中&#xff0c;读写速度非常快 redis未授权 其原因很简单&#xff0c;就是redis服务器在默认安装好不配置的情况下可以直接免密码登录&#xff0c;登录后在web目录写入一句话木马&am…
阅读更多...
为什么选择国产WordPress：HelpLook的优势解析

为什么选择国产WordPress：HelpLook的优势解析

如今网站建设可以说已经是企业必备。而在众多的网站建设工具中&#xff0c;WordPress无疑是其中的佼佼者。作为一款开源的CMS&#xff08;内容管理系统&#xff09;&#xff0c;WordPress拥有丰富的插件和主题&#xff0c;以及强大的功能&#xff0c;使得用户可以轻松地构建出符…
阅读更多...
web前端之若依二次开发经验、使用IDEA启动若依项目、sysConfigController报错提示的解决办法、环境搭建

web前端之若依二次开发经验、使用IDEA启动若依项目、sysConfigController报错提示的解决办法、环境搭建

MENU 前言前端创建路由的细节 后端启动后端项目细节 前言 1、官网地址 2、在线文档 3、演示地址 4、代码下载 5、野生版的若依开发文档 此文章包括前端和后端&#xff0c;记录开发中遇到的一些问题。 前端 创建路由的细节 1、从系统管理进入菜单管理页面创建菜单&#xff0c;菜…
阅读更多...
最强Pose模型RTMO开源 | 基于YOLO架构再设计，9MB+9ms性能完爆YOLO-Pose

最强Pose模型RTMO开源 | 基于YOLO架构再设计，9MB+9ms性能完爆YOLO-Pose

实时多人在图像中的姿态估计面临着在速度和精度之间实现平衡的重大挑战。尽管两阶段的上下文方法在图像中人数增加时会减慢速度&#xff0c;但现有的单阶段方法往往无法同时实现高精度和实时性能。 本文介绍了RTMO&#xff0c;这是一个单阶段姿态估计框架&#xff0c;通过在YOL…
阅读更多...
03进程基础-学习笔记

03进程基础-学习笔记

Process 进程 进程为操作系统的基本调度单位&#xff0c;占用系统资源(cpu,内存)完成特定任务&#xff0c;所有说进程是操作系统的标准执行单元 进程与程序的差别 程序是静态资源&#xff0c;存储与电脑磁盘中(disk磁盘资源)程序执行后会创建进程&#xff0c;负责完成功能&a…
阅读更多...
第十五章总结

第十五章总结

一.输入/输出流 1.输入流 InputStrema类是字节输入流的抽象类&#xff0c;它是所有字节输入流的父类。 该类中所有方法遇到错误都会引发IOException异常。 read()方法&#xff1a;从输入流中读取数据的下一个字节。返回0~255的int字节值。如果因为已经到达流末尾而没有可用的…
阅读更多...
完美解决labelimg xml转可视化中文乱码问题，不用matplotlib

完美解决labelimg xml转可视化中文乱码问题，不用matplotlib

背景简述 我们有一批标注项目要转可视化&#xff0c;因为之前没有做过&#xff0c;然后网上随意找了一段代码测试完美&#xff08;并没有&#xff09;搞定&#xff0c;开始疯狂标注&#xff0c;当真正要转的时候傻眼了&#xff0c;因为测试的时候用的是英文标签&#xff0c;实…
阅读更多...
重生奇迹mu再生原石介绍

重生奇迹mu再生原石介绍

再生原石的作用&#xff1a; 可以通过坎特鲁提炼之塔的NPC艾尔菲丝提炼成功就可以可获得再生宝石。 再生原石的用法&#xff1a; 1、打怪获得再生原石去提炼之塔&#xff08;进入坎特鲁遗址的141188位置的传送台&#xff09;。 2、找到&#xff08;艾儿菲丝&#xff09;把原…
阅读更多...
【程序】STM32 读取光栅_编码器_光栅传感器_7针OLED

【程序】STM32 读取光栅_编码器_光栅传感器_7针OLED

文章目录 源代码工程编码器基础程序参考资料 源代码工程 源代码工程打开获取&#xff1a; http://dt2.8tupian.net/2/28880a55b6666.pg3这里做了四倍细分&#xff0c;在屏幕上显示 速度、路程、方向。 接线方法&#xff1a; 单片机--------------串口模块 单片机的5V-------…
阅读更多...
【JAVA基础(对象和封装以及构造方法)】----第四天

【JAVA基础(对象和封装以及构造方法)】----第四天

对象和封装以及构造方法 面向对象和面向过程面向过程面向对象 类与对象及其使用定义类创建一个对象&#xff0c;操作类补充&#xff08;成员变量和局部变量&#xff09; private 修饰类 封装练习编写类编写测试输出结果 面向对象和面向过程 面向过程 在了解面向对象之前先来了…
阅读更多...
C语言刷题每日一题——求1到100中包含数字9的整数的个数

C语言刷题每日一题——求1到100中包含数字9的整数的个数

思路分析 创建一个变量count记录个数使用一个for循环完成从1到100的循环每次循环判断该数字是否包含数字9——第一种情况 &#xff1a;个位包含9&#xff0c;即求模10的结果为9 &#xff1b;第二种情况&#xff1a;十位包含9&#xff0c;即除以10的结果为9&#xff08;两种情况…
阅读更多...
【Vulnhub 靶场】【VulnCMS: 1】【简单】【20210613】

【Vulnhub 靶场】【VulnCMS: 1】【简单】【20210613】

1、环境介绍 靶场介绍&#xff1a;https://www.vulnhub.com/entry/vulncms-1,710/ 靶场下载&#xff1a;https://download.vulnhub.com/vulncms/VulnCMS.ova 靶场难度&#xff1a;简单 发布日期&#xff1a;2021年06月13日 文件大小&#xff1a;1.4 GB 靶场作者&#xff1a;to…
阅读更多...
Stable Diffusion - High-Resolution Image Synthesis with Latent Diffusion Models

Stable Diffusion - High-Resolution Image Synthesis with Latent Diffusion Models

Paper name High-Resolution Image Synthesis with Latent Diffusion Models Paper Reading Note Paper URL: https://arxiv.org/abs/2112.10752 Code URL: https://github.com/CompVis/latent-diffusion TL;DR 2021 年 runway 和慕尼黑路德维希马克西米利安大学出品的文…
阅读更多...
服务器数据恢复—raid5热备盘未激活崩溃导致上层oracle数据丢失的数据恢复案例

服务器数据恢复—raid5热备盘未激活崩溃导致上层oracle数据丢失的数据恢复案例

服务器数据恢复环境&#xff1a; 某品牌X系列服务器&#xff0c;4块SAS硬盘组建了一组RAID5阵列&#xff0c;还有1块磁盘作为热备盘使用。服务器上层安装的linux操作系统&#xff0c;操作系统上部署了一个基于oracle数据库的OA&#xff08;oracle已经不再为该OA系统提供后续服务…
阅读更多...
vue3+echarts 立体柱状效果

vue3+echarts 立体柱状效果

vue3echarts 立体柱状效果 废话不多说&#xff0c;直接上代码 就两步&#xff0c;直接复制粘贴一手 <div id"main" class"chart" ref"chartDom"></div>import * as echarts from echarts; type EChartsOption echarts.EChartsOpti…
阅读更多...
前端实现一个时间区间内，再次单选功能，使用Antd组件库内日历组件Calendar

前端实现一个时间区间内，再次单选功能，使用Antd组件库内日历组件Calendar

需求&#xff1a;需要先让用户选择一个时间区间&#xff0c;然后再这个时间区间中&#xff0c;让用户再次去单选其种特殊日期。 思路&#xff1a; 1.先用Antd组件库中日期选择DatePicker.RangePicker实现让用户选择时间区间 2.在选择完时间区间后&#xff0c;用这个时间区间…
阅读更多...
蓝桥杯专题-真题版含答案-【扑克牌排列】【放麦子】【纵横放火柴游戏】【顺时针螺旋填入】

蓝桥杯专题-真题版含答案-【扑克牌排列】【放麦子】【纵横放火柴游戏】【顺时针螺旋填入】

Unity3D特效百例案例项目实战源码Android-Unity实战问题汇总游戏脚本-辅助自动化Android控件全解手册再战Android系列Scratch编程案例软考全系列Unity3D学习专栏蓝桥系列ChatGPT和AIGC &#x1f449;关于作者 专注于Android/Unity和各种游戏开发技巧&#xff0c;以及各种资源分…
阅读更多...
最新文章

Copyright @ 2022~2023