首页 > 编程语言 >从零开始学数据结构系列之第四章《克鲁斯卡尔算法应用场景-公交站问题》

从零开始学数据结构系列之第四章《克鲁斯卡尔算法应用场景-公交站问题》

时间:2024-07-28 17:26:48浏览次数:20  
标签:第三章 将边 克鲁斯 最小 算法 从零开始 二叉树 公交站 第四章

文章目录


在这里插入图片描述

  1. 某城市新增 7 个站点(A, B, C, D, E, F, G) ,现在需要修路把 7 个站点连通
  2. 各个站点的距离用边线表示(权) ,比如 A – B 距离 12 公里
  3. 问:如何修路保证各个站点都能连通,并且总的修建公路总里程最短?

以上图为例,来对克鲁斯卡尔进行演示(假设用数组 R 保存最小生成树结果)。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
第1步:将边<E,F>加入 R 中。

​   边<E,F>的权值最小,因此将它加入到最小生成树结果 R 中。

第2步:将边<C,D>加入 R 中。

​   上一步操作之后,边<C,D>的权值最小,因此将它加入到最小生成树结果 R 中。

第3步:将边<D,E>加入 R 中。

​   上一步操作之后,边<D,E>的权值最小,因此将它加入到最小生成树结果 R 中。

第4步:将边<B,F>加入 R 中。

​   上一步操作之后,边<C,E>的权值最小,但<C,E>会和已有的边构成回路;因此,跳过边<C,E>。同理,跳过边<C,F>。将边<B,F>加入到最小生成树结果 R 中。

第5步:将边<E,G>加入 R 中。

​   上一步操作之后,边<E,G>的权值最小,因此将它加入到最小生成树结果 R 中。

第6步:将边<A,B>加入 R 中。
  上一步操作之后,边<F,G>的权值最小,但<F,G>会和已有的边构成回路;因此,跳过边<F,G>。同理,跳过边<B,C>。将边<A,B>加入到最小生成树结果 R 中。

​   此时,最小生成树构造完成!它包括的边依次是:<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>

往期回顾

1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》
10.【第二章】《字符串暴力匹配》
11.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》
13.【第三章】《二叉树的存储结构》
14.【第三章】《二叉树链式结构及实现1》
15.【第三章】《二叉树链式结构及实现2》
16.【第三章】《二叉树链式结构及实现3》
17.【第三章】《二叉树链式结构及实现4》
18.【第三章】《二叉树链式结构及实现5》
19.【第三章】《中序线索二叉树理论部分》
20.【第三章】《中序线索二叉树代码初始化及创树》
21.【第三章】《中序线索二叉树线索化及总代码》
22【第三章】《先序线索二叉树理论及线索化》
23【第三章】《先序线索二叉树查找及总代码》
24【第三章】《后续线索二叉树线索化理论》
25【第三章】《后续线索二叉树总代码部分》
26【第三章】《二叉排序树基础了解》
27【第三章】《二叉排序树代码部分》
28【第三章】《二叉排序树代码部分》
29【第三章】《平衡二叉树基础概念》
30【第三章】《平衡二叉树的平衡因子》
31【第三章】《平衡二叉树的旋转基础详解》
32【第三章】《平衡二叉树的旋转类型图文详解》
33【第三章】《平衡二叉树的旋转类型总结及总代码》
34【第三章】《哈夫曼树简单了解》
35【第三章】《哈夫曼树的构造方法》
36【第三章】《哈夫曼编码构造及代码》
37【第四章】《图的定义》
38【第四章】《图的基本概念和术语》
39【第四章】《图的存储结构》
40【第四章】《图的遍历之深度优先遍历》
41【第四章】《广度优先遍历BFS》
42【第四章】《图的遍历总代码》
43【第四章】《最小生成树概念》
44【第四章】《最小生成树的应用举例》
45【第四章】《prim算法(普里姆算法)详解》
46【第四章】《prim算法(普里姆算法)详解2》
47【第四章】《prim算法(普里姆算法)详解3》
48【第四章】《prim算法(普里姆算法)讲解汇总》
49【第四章】《prim算法(普里姆算法)代码讲解》
50【第四章】《prim算法(普里姆算法)总代码》
51【第四章】《克鲁斯卡尔算法思路介绍》
52【第四章】《克鲁斯卡尔算法步骤思路1》
53【第四章】《克鲁斯卡尔算法步骤思路2》

标签:第三章,将边,克鲁斯,最小,算法,从零开始,二叉树,公交站,第四章
From: https://blog.csdn.net/qq_62548908/article/details/140743501

相关文章

  • 邦布带你从零开始实现图书管理系统(java版)
    今天我们来从零开始实现图书管理系统。图书管理系统来看我们的具体的实现,上述视频。我们首先来实现框架,我们要实现图书管理系统,首先要搭框架。我们首先定义一个书包,在书包中定义一个书类和一个书架类,再定义一个用户包,其中包含用户类,管理者类,普通用户类,在定义一个工具包......
  • 从零开始的JAVAday22~day28
    上周我们学习了如何定义变量,这周我们学习如何给变量起名。硬性要求:1.由数字、字母、下划线()和美元符($)组成2.不能以数字开头3.不能是关键字4.区分大小写软性要求:小驼峰命名法:存在一个单词时所有字母都小写,存在多个字母时第一个单词小写第二个单词首字母大写大驼峰命名法......
  • 《重生到现代之从零开始的C语言生活》—— 分支和循环
    前言:因为C语言是结构化的程序设计语言,这里面的结构指的是顺序结构,选择结构,循环结构,在日常生活中,所见的事都能拆分成这几个结构或者这三种结构的组合。if语句ifif在英文中有如果的意思,在C语言中意思相似if(表达式)要执行的语句如果表达式成立(为真),则执行语句,如果不......
  • 从零开始搭建博客系列-终
    结束,也是新的开始。‍不知不觉也写了接近30篇博客了,也帮助到了很多人,甚是欣慰。本文就做一个小结吧......
  • 从零开始搭建博客系列-终
    结束,也是新的开始。‍不知不觉也写了接近30篇博客了,也帮助到了很多人,甚是欣慰。本文就做一个小结吧......
  • 从零开始使用GPT-4o mini:配置、微调与优化
    引言随着人工智能技术的不断发展,OpenAI推出的GPT-4omini模型吸引了众多开发者的关注。作为一种更经济实惠且高效的语言模型,GPT-4omini在多模态推理和成本效益方面表现出色。本篇文章旨在分享使用GPT-4omini的经验,从初始设置到性能优化,涵盖各个应用场景,并提供实际的开发建议......
  • Python从零开始制做文字游戏(荒岛求生)
    文章目录前言开发游戏《荒岛求生》游戏大纲背景内容通关条件游戏过程探索荒岛购买物资休息总结代码开发定义变量当前代码引入背景故事当前代码循环问题解决:函数当前代码制作延时当前代码制作a函数(探索荒岛阶段)展示数......
  • 从零开始学习机器学习,掌握AI未来的关键!
    从零开始学习机器学习1.介绍1.1人工智能(AI)概述1.2机器学习在人工智能中的应用1.3机器学习基础概念2.监督学习2.1什么是监督学习2.2回归分析2.3分类问题2.4模型评估和选择3.无监督学习3.1什么是无监督学习3.2聚类算法3.3降维技术4.深度学习4.1神经网络......
  • 气压高度传感器 - 从零开始认识各种传感器【第十五期】
    气压高度传感器|从零开始认识各种传感器1、什么是气压高度传感器 气压高度传感器是通过气压的变化来测量所处高度的传感器,它在测量的过程中不易受到障碍物的影响,测量高度范围广,可进行绝对海拔高度测量和相对高度测量。目前智能手机及智能穿戴设备上也大多集成了气压传感......
  • 从零开始:神经网络(1)——什么是人工神经网络
      声明:本文章是根据网上资料,加上自己整理和理解而成,仅为记录自己学习的点点滴滴。可能有错误,欢迎大家指正。     人工神经网络(ArtificialNeuralNetwork,简称ANN)是一种模仿生物神经网络结构和功能的计算模型。它由大量的节点(或称神经元)相互连接而成,这些节点通常......