克鲁斯卡尔算法

连通图中寻找最小生成树的常用算法有 2 种,分别是普里姆算法和克鲁斯卡尔算法。本节,我们将带您详细了解克鲁斯卡尔算法。

和普里姆算法类似,克鲁斯卡尔算法的实现过程也采用了贪心的策略:对于具有 n 个顶点的图,将图中的所有路径(边)按照权值大小进行升序排序,从权值最小的路径开始挑选,只要此路径不会和已选择的其它路径构成环路,就选定其作为最小生成树的一部分,直至选够 n-1 条路径。 

对于具有 n 个顶点的图,选择 n-1 条路径就可以将所有顶点连接起来。在此基础上,保证所选的每条路径的权值都最小,就可以找到一棵最小生成树。

 以图 1 所示的连通图为例,克鲁斯卡尔算法寻找最小生成树的过程为:
1) 将所有路径(边)按照权值大小进行升序排序:

2) 从最小的路径开始,只要该路径不会和其它已选路径产生环路,就选择它作为组成最小生成树的一部分。显然 (B,D) 符合要求,选择它组成最小生成树:

3) (D,T) 不会和已选路径 (B,D) 构成环路,可以组成最小生成树:

 4) (A,C) 不会和 (B,D)、(D,T) 构成环路,可以组成最小生成树:

5) (C,D) 不会和 (A,C)、(B,D)、(D,T) 构成环路,可以组成最小生成树:

 6) (C,B) 会和已选路径 (C,D)、(B,D) 构成环路(如图 6 所示),因此不会被选择:

7) (B,T) 会和已选路径 (B,D)、(D,T) 构成环路,也不被选择;

8) (A,B) 会和已选路径 (A,C)、(C,D)、(D,B) 构成环路,也不被选择;

9) (S,A) 不会和已选路径 (A,C)、(C,D)、(D,B)、(D,T) 构成环路,可以组成最小生成树:

 

克鲁斯卡尔算法的具体实现

克鲁斯卡尔算法的实现,难点在于如何判断所选路径是否会造成环路,这里给您介绍一种简单的解决方案:初始状态下,为图中的每个顶点配备一个互不相同的标记值,算法执行过程中,如果新路径两个顶点的标记值不同,则不会构成环路,该路径被选择的同时,要将两个顶点的标记改为和其它已选路径中的顶点标记相同;反之,如果该路径两个顶点的标记值相同,则会构成环路。

举个例子,图 5 中,已选路径为 (A,C)、(B,D)、(C,D)、(D,T),此时顶点 A、C、B、D、T 的标记值相同,顶点 S 的标记值和它们不同。图 6 中,判定 (B,C) 路径是否可以组成最小生成树时,由于顶点 B 和 C 的标记值相同,因此该路径会和其它已选路径构成环路(如图 6 所示),不能组成最小生成树。

如下为实现克鲁斯卡尔算法的 C 语言程序:

#include <stdio.h>
#include <stdlib.h>
#define N 9   // 图中边的数量
#define P 6   // 图中顶点的数量
//构建表示边的结构体
struct edge {
    //一条边有 2 个顶点
    int initial;
    int end;
    //边的权值
    int weight;
};
//qsort排序函数中使用,使edges结构体中的边按照权值大小升序排序
int cmp(const void *a, const void*b) {
    return  ((struct edge*)a)->weight - ((struct edge*)b)->weight;
}
//克鲁斯卡尔算法寻找最小生成树,edges 存储用户输入的图的各个边,minTree 用于记录组成最小生成树的各个边
void kruskal_MinTree(struct edge edges[], struct edge minTree[]) {
    int i,initial, end;
    //每个顶点配置一个标记值
    int assists[P];
    int num = 0;
    //初始状态下,每个顶点的标记都不相同
    for (i = 0; i < P; i++) {
        assists[i] = i;
    }
    //根据权值,对所有边进行升序排序
    qsort(edges, N, sizeof(edges[0]), cmp);
    //遍历所有的边
    for (int i = 0; i < N; i++) {
        //找到当前边的两个顶点在 assists 数组中的位置下标
        initial = edges[i].initial - 1;
        end = edges[i].end - 1;
        //如果顶点位置存在且顶点的标记不同,说明不在一个集合中,不会产生回路
        if (assists[initial] != assists[end]) {
            //记录该边,作为最小生成树的组成部分
            minTree[num] = edges[i];
            //计数+1
            num++;
            int elem = assists[end];
            //将新加入生成树的顶点标记全部改为一样的
            for (int k = 0; k < P; k++) {
                if (assists[k] == elem) {
                    assists[k] = assists[initial];
                }
            }
            //如果选择的边的数量和顶点数相差1,证明最小生成树已经形成,退出循环
            if (num == P - 1) {
                break;
            }
        }
    }
}
void display(struct edge minTree[]) {
    int cost = 0;
    printf("最小生成树为:\n");
    for (int i = 0; i < P - 1; i++) {
        printf("%d-%d  权值:%d\n", minTree[i].initial, minTree[i].end, minTree[i].weight);
        cost += minTree[i].weight;
    }
    printf("总权值为:%d", cost);
}
int main() {
    int i;
    struct edge edges[N], minTree[P - 1];
    for (i = 0; i < N; i++) {
        scanf("%d %d %d", &edges[i].initial, &edges[i].end, &edges[i].weight);
    }
    kruskal_MinTree(edges,minTree);
    display(minTree);
    return 0;
}

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

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

相关文章

竞赛选题 深度学习手势识别 - yolo python opencv cnn 机器视觉

文章目录 0 前言1 课题背景2 卷积神经网络2.1卷积层2.2 池化层2.3 激活函数2.4 全连接层2.5 使用tensorflow中keras模块实现卷积神经网络 3 YOLOV53.1 网络架构图3.2 输入端3.3 基准网络3.4 Neck网络3.5 Head输出层 4 数据集准备4.1 数据标注简介4.2 数据保存 5 模型训练5.1 修…

【仙逆】尸阴宗秘密揭露,王林差点被夺舍,修仙恐怖消息曝光

Hello,小伙伴们&#xff0c;我是小郑继续为大家深度解析国漫资讯。 深度爆料&#xff0c;《仙逆》国漫第九话最新剧情&#xff0c;尸阴宗表面上令人敬畏&#xff0c;但背后却隐藏着不为人知的秘密。这个宗门暗地里为受伤或死亡的强大修真者提供夺舍容器&#xff0c;帮助他们获…

定时发圈怎么设置?

微信本身是不能定时发送朋友圈的。微信公众号可以定时发送&#xff0c;微博可以定时发送&#xff0c;那微信可不可以也定时发送呢&#xff1f;当然可以&#xff0c;只要用这个方法&#xff0c;微信也能实现定时发朋友圈&#xff0c;不用再守着时间发朋友圈了。

持续集成交付CICD:安装Jenkins Slave(从节点)

目录 一、实验 1.安装Jenkins Slave&#xff08;从节点&#xff09; 二、问题 1.salve节点启动jenkins报错 2.终止命令行后jenkins从节点状态不在线 一、实验 1.安装Jenkins Slave&#xff08;从节点&#xff09; &#xff08;1&#xff09;查看jenkins版本 Version 2.…

基于SSM的酒店客房管理系统设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用JSP技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…

Maven-构建工具

一、背景 开发者编写完成源码&#xff0c;还需要进行编译、测试、打包、部署等一系列操作。在一些小型项目中&#xff0c;还可能通过手动方式进行以上操作。但是在大型项目中&#xff0c;难以确定以上操作的顺序&#xff0c;而且会耗费更高的时间成本。 1.构建工具 构建工具…

必看!玩转Salesforce沙盒的5个实用技巧

定期刷新沙盒对于尝试最新版本的功能&#xff0c;以及防止在生产组织的环境中缺乏测试而导致开发工作回滚至关重要。 为了确保沙盒设置在刷新后顺利进行&#xff0c;需要考虑几个因素。首先&#xff0c;确保有完善的文档化流程。文档应分为Conga、DocuSign、数据&#xff08;C…

双通道 H 桥电机驱动芯片AT8833,软硬件兼容替代DRV8833,应用玩具、打印机等应用

上期小编给大家分享了单通道 H 桥电机驱动芯片&#xff0c;现在来讲一讲双通道的驱动芯片。 双通道 H 桥电机驱动芯片能通过控制电机的正反转、速度和停止等功能&#xff0c;实现对电机的精确控制。下面介绍双通道H桥电机驱动芯片的工作原理和特点。 一、工作原理 双通道 H 桥电…

【题解】2023 DTS算法竞赛集训 第1次

比赛地址&#xff1a;https://www.luogu.com.cn/contest/143650 P1319 压缩技术 https://www.luogu.com.cn/problem/P1319 简单的签到模拟题 #include <iostream>//c标准库 using namespace std; int main(){int a,n,t0,i0,b,s0;//t判断有没有回车&#xff0c;i判断输…

初识rust

调试下rust 的执行流程 参考&#xff1a; 认识 Cargo - Rust语言圣经(Rust Course) 新建一个hello world 程序&#xff1a; fn main() {println!("Hello, world!"); }用IDA 打开exe&#xff0c;并加载符号&#xff1a; 根据字符串找到主程序入口&#xff1a; 双击…

MySQL进阶之性能优化与调优技巧

数据库开发-MySQL 1. 多表查询1.1 概述1.1.2 介绍1.1.3 分类 1.2 内连接1.3 外连接1.4 子查询1.4.1 介绍1.4.2 标量子查询1.4.3 列子查询1.4.4 行子查询1.4.5 表子查询 2. 事务2.1 介绍2.2 操作2.3 四大特性 3. 索引3.1 介绍3.2 结构3.3 语法 1. 多表查询 1.1 概述 1.1.2 介绍…

云计算的大模型之争,亚马逊云科技落后了?

文丨智能相对论 作者丨沈浪 “OpenAI使用了Azure的智能云服务”——在过去的半年&#xff0c;这几乎成为了微软智能云最好的广告词。 正所谓“水涨船高”&#xff0c;凭借OpenAI旗下的ChatGPT在全球范围内爆发&#xff0c;微软趁势拉了一波自家的云计算业务。2023年二季度&a…

个人和企业如何做跨境电商?用API电商接口教你选平台选品决胜跨境电商

当下是跨境电商快速发展的阶段&#xff0c;在未来将会朝向成熟系统化的方向发展&#xff0c;对于跨境电商从业者来说既是机遇&#xff0c;也是挑战。那么&#xff0c;个人做跨境电商的核心要素是什么&#xff1f;又该如何去做&#xff1f;对此&#xff0c;小编总结以下四大核心…

【C/C++】什么是POD(Plain Old Data)类型

2023年11月6日&#xff0c;周一下午 目录 POD类型的定义标量类型POD类型的特点POD类型的例子整数类型&#xff1a;C 风格的结构体&#xff1a;数组&#xff1a;C 风格的字符串&#xff1a;std::array:使用 memcpy 对 POD 类型进行复制把POD类型存储到文件中&#xff0c;并从文…

3.Netty中Channel通道概述

Selector 模型 Java NIO 是基于 Selector 模型来实现非阻塞的 I/O。Netty 底层是基于 Java NIO 实现的&#xff0c;因此也使用了 Selector 模型。 Selector 模型解决了传统的阻塞 I/O 编程一个客户端一个线程的问题。Selector 提供了一种机制&#xff0c;用于监视一个或多个 …

Java2 - 数据结构

5 数据类型 5.1 整数类型 在Java中&#xff0c;数据类型用于定义变量或表达式可以存储的数据的类型。Java的数据类型可分为两大类&#xff1a;基本数据类型和引用数据类型。 byte&#xff0c;字节 【1字节】表示范围&#xff1a;-128 ~ 127 即&#xff1a;-2^7 ~ 2^7 -1 sho…

第二章:人工智能深度学习教程-深度学习简介

深度学习是基于人工神经网络的机器学习的一个分支。它能够学习数据中的复杂模式和关系。在深度学习中&#xff0c;我们不需要显式地对所有内容进行编程。近年来&#xff0c;由于处理能力的进步和大型数据集的可用性&#xff0c;它变得越来越流行。因为它基于人工神经网络&#…

mac装不了python3.7.6

今天发现一个很奇怪的问题 但是我一换成 conda create -n DCA python3.8.12就是成功的 这个就很奇怪

【ElasticSearch系列-04】ElasticSearch的聚合查询操作

ElasticSearch系列整体栏目 内容链接地址【一】ElasticSearch下载和安装https://zhenghuisheng.blog.csdn.net/article/details/129260827【二】ElasticSearch概念和基本操作https://blog.csdn.net/zhenghuishengq/article/details/134121631【三】ElasticSearch的高级查询Quer…

【机器学习3】有监督学习经典分类算法

1 支持向量机 在现实世界的机器学习领域&#xff0c; SVM涵盖了各个方面的知识&#xff0c; 也是面试题目中常见的基础模型。 SVM的分类结果仅依赖于支持向量&#xff0c;对于任意线性可分的两组点&#xff0c;它 们在SVM分类的超平面上的投影都是线性不可分的。 2逻辑回归 …