当前位置: 首页 > news >正文

DSA之图(4):图的应用

文章目录

  • 0 图的应用
  • 1 生成树
    • 1.1 无向图的生成树
    • 1.2 最小生成树
      • 1.2.1 构造最小生成树
      • 1.2.2 Prim算法构造最小生成树
      • 1.2.3 Kruskal算法构造最小生成树
      • 1.2.4 两种算法的比较
    • 1.3 最短路径
      • 1.3.1 两点间最短路径
      • 1.3.2 某源点到其他各点最短路径
      • 1.3.3 Dijkstra
      • 1.3.4 Floyd
    • 1.4 拓扑排序
      • 1.4.1 有向无环图DAG
      • 1.4.2 AOV网
    • 1.5 关键路径
      • 1.5.1 求解关键路径

0 图的应用

在这里插入图片描述

1 生成树

生成树:所有顶点均由边连接在一起,但不存在回路的图。
也就是两个条件,顶点条件和边数条件,顶点都要保持连通,边数达到最少,没有回路。
在这里插入图片描述
如右边的图,随便再加一条边就有回路了。在这里插入图片描述
所有生成树都具有以下的共同特点:

  • 生成树的顶点个数与图的顶点个数相同;
  • 生成树是图的极小连通子图,去掉一条边则非连通;
  • 一个有 n n n个顶点的连通图的生成树有 n − 1 n-1 n1条边;
  • 生成树中任意两个顶点间的路径是唯一的;
  • 含有 n n n个顶点 n − 1 n-1 n1条边的图不一定是生成树,如下图所示
    在这里插入图片描述
    因为生成树是连通的,每个顶点都要用边相连,上图是不连通的,有两个连通分量。

1.1 无向图的生成树

生成树要包含所有顶点,那么对图进行遍历,把走过的边全部加入到图当中。
遍历则采用DFS与BFS都可以。在这里插入图片描述

用DFS生成的生成树就是DFS生成树。
在这里插入图片描述
用BFS生成的生成树就是BFS生成树。
在这里插入图片描述

综上
在这里插入图片描述

1.2 最小生成树

在这里插入图片描述
最小生成树:给定一无向网络在该网的所有生成树中,使得各边权值之和最小的那棵生成树称为该网的最小生成树,也叫最小代价生成树。
最小生成树可能是不唯一的。

在这里插入图片描述

1.2.1 构造最小生成树

构造最小生成树的算法很多,其中多数算法都利用了MST(Minimum Spanning Tree)的性质。

MST性质
其实就是贪心算法,不断去找权值最小的边。
N = ( V , E ) N=(V, E) N=(V,E)以目是一个连通网, U U U是顶点集 V V V的一个非空子集。若边 ( u , v ) (u, v) (u,v)是一条具有最小权值的边,其中 u ∈ U , v ∈ V − U u∈U,v∈V-U uU,vVU则必存在一棵包含边 ( u , v ) (u,v) (u,v)的最小生成树。

举例

在这里插入图片描述
现在 U = { v 1 } U=\{v_1\} U={v1},所以 V − U = { v 2 , v 3 , v 4 , v 5 , v 6 } V-U=\{v_2,v_3,v_4,v_5,v_6\} VU={v2,v3,v4,v5,v6},所以 u ∈ U , v ∈ V − U u∈U,v∈V-U uU,vVU当中,其中从 v 1 v_1 v1 v 3 v_3 v3是最小的,权值为1,存在这个权值最小的边,这条边一定会包含在某个最下生成树当中。
在这里插入图片描述

1.2.2 Prim算法构造最小生成树

算法思想:
在这里插入图片描述

1.2.3 Kruskal算法构造最小生成树

相比Prim算法更加贪心,直截了当贪心,前提不成环。这次开始就把所有顶点都加入到最小生成树上面去。不过并不包括边,这时边的集合都是空集,没包含边,彼此之间不连通。
在这里插入图片描述
然后直接在边集合当中选权值最小的边,直接加入。在这里插入图片描述
以此类推,选到所有顶点都连通为止(前提不能形成回路)(n个点,n-1条边)。在这里插入图片描述

1.2.4 两种算法的比较

在这里插入图片描述
Prim是选择点加入的,而Kruskal是选择边的。选择边的时候和顶点数是没关系的。

1.3 最短路径

1.3.1 两点间最短路径

从起点走向终点,并非要n个节点都包括,也并非要n-1条边。在这里插入图片描述
直到找到路径长度最短的一条路径。
这种最短路径也称为单源的最短路径,采用Dijkstra算法。

1.3.2 某源点到其他各点最短路径

在这里插入图片描述
所有顶点的最短路径,统一使用Floyd弗洛伊德算法。

1.3.3 Dijkstra

其时间复杂度为 O ( n 3 ) O(n^3) O(n3)
在这里插入图片描述
按照路径长度递增次序产生最短路径,启发式贪心算法。
在这里插入图片描述
在这里插入图片描述
启发式算法,先找最短的,后面再及时更新,具体过程可以看王老师的视频。

1.3.4 Floyd

其时间复杂度为 O ( n 3 ) O(n^3) O(n3)

算法思想:

  • 逐个顶点试探
  • 从少,到的所有可能存在的路径中
  • 选出一条长度最短的路径

在这里插入图片描述
求最短路径的步骤:
初始时设置一个 n n n阶方阵,令其对角线元素(到自身的路径)为0,若存在弧 < v i , v j > <v_i, v_j> <vi,vj>,则对应元素为权值;否则为 ∞ ∞
逐步试着在原直接路径中增加中间顶点,若加入中间顶点后路径变短,则修改之;否则,维持原值。所有顶点试探完毕,算法结束。

在这里插入图片描述

1.4 拓扑排序

1.4.1 有向无环图DAG

在这里插入图片描述
在这里插入图片描述
AOV网以顶点表示活动;AOE网用弧表示活动(子工程)。
AOV网用来解决拓扑排序,AOE网用来解决关键路径问题。

拓扑排序的一个小例子:
在这里插入图片描述

1.4.2 AOV网

在这里插入图片描述
问题:如何判断AOV网中是否存在回路?

在这里插入图片描述
所有顶点都能加入拓扑排序的话,就一定没有网。

拓扑排序。
将网变成一个线性序列的过程就是拓扑排序。
在这里插入图片描述
拓扑排序的步骤:

  1. 首先构建好AOV网

在这里插入图片描述

  1. 在有向图中选一个没有前驱的顶点且输出(例如C1和C9)
  2. 假设选了C1,在有向图当中删除该顶点和所有以它为尾的弧(C1发出的弧)(即C1与C2,C4,C12的弧)
  3. 重复上述两步,直至全部顶点均已输出;或者当图中不存在无前驱的顶点为止在这里插入图片描述

1.5 关键路径

制定计划,查找关键路径。
关键路径就是从源点到汇点路径长度(权值之和)最长(大)的路径。

在这里插入图片描述
按照任务需求,构建有权图。
在这里插入图片描述
举例:
在这里插入图片描述

对于上方AOE网,我们关心两个问题:

  1. 完成整项女程至少需要多少时间?
  2. 哪些活动是影响工程进度的关键?

以上答为关键路径与路径长度。

1.5.1 求解关键路径

四个有用的量:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
求关键路径的步骤:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

相关文章:

DSA之图(4):图的应用

文章目录 0 图的应用1 生成树1.1 无向图的生成树1.2 最小生成树1.2.1 构造最小生成树1.2.2 Prim算法构造最小生成树1.2.3 Kruskal算法构造最小生成树1.2.4 两种算法的比较 1.3 最短路径1.3.1 两点间最短路径1.3.2 某源点到其他各点最短路径1.3.3 Dijkstra1.3.4 Floyd 1.4 拓扑排…...

[SQL挖掘机] - 窗口函数 - row_number

介绍: row_number() 是一种常用的窗口函数&#xff0c;它为结果集中的每一行分配一个唯一的数字。这个数字的分配基于指定的排序顺序&#xff0c;并且不会跳过相同的排名。 用法: row_number() 函数的语法如下&#xff1a; row_number() over ([partition by 列名1, 列名2,…...

【论文阅读】通过解缠绕表示学习提升领域泛化能力用于主题感知的作文评分

摘要 本文工作聚焦于从领域泛化的视角提升AES模型的泛化能力&#xff0c;在该情况下&#xff0c;目标主题的数据在训练时不能被获得。本文提出了一个主题感知的神经AES模型&#xff08;PANN&#xff09;来抽取用于作文评分的综合的表示&#xff0c;包括主题无关&#xff08;pr…...

二分查找P1873 [COCI2011-2012#5] EKO / 砍树

P1873 [COCI2011-2012#5] EKO / 砍树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 这个题就是给新手练手的&#xff0c;在那个位置上在进行&#xff0c;寻找合适的砍树高度&#xff0c;下面在介绍一个二分查找的模板 int binarySearch(vector<int>& nums, int t…...

【BOOST程序库】正则表达式相关操作

基本概念这里不解释了&#xff0c;代码中详细解释了BOOST程序库中对于正则表达式常用方法的详细用法。 #include <iostream> #include <string>//正则表达式头文件 #include <boost/xpressive/xpressive.hpp>int main() {//声明正则&#xff1a;boost::pres…...

阿里云国际版在使用过程中应该注意什么呢?

为确保系统稳定性&#xff0c;用户不得进行以下操作。否则&#xff0c;阿里云可能无法解决由以下违规操作引起的问题&#xff1a; 1) Windows系统中的PV Drivers 程序不可删除 PV Drivers程序为服务器虚拟化驱动程序&#xff0c;请不要针对该程序进行任何操作&#xff0c;如果删…...

Flutter Provider 共享状态管理

在使用Provider的时候&#xff0c;我们主要关心三个概念&#xff1a; ChangeNotifier&#xff1a;真正数据&#xff08;状态&#xff09;存放的地方ChangeNotifierProvider&#xff1a;Widget树中提供数据&#xff08;状态&#xff09;的地方&#xff0c;会在其中创建对应的Ch…...

std vector 用法

使用vector&#xff0c;需添加头文件#include&#xff0c;要使用sort或find&#xff0c;则需要添加头文件#include。函数封装在命名空间std中&#xff0c;使用&#xff1a;using namespace std; 1、vector的初始化 std::vector<int> nVec;    // 空对象 std::vecto…...

vue vite ts electron ipc addon-napi c arm64

初始化 因网络问题建议使用 cnpm 代替 npm npm init vue # 全选 yes npm i # 进入项目目录后使用 npm i electron electron-builder -D npm i commander -D # 额外组件electron 新建 plugins、src/electron 文件夹 添加 src/electron/background.ts 属于主进程 ipcMain.o…...

机器人科普--AGILOX 叉车

机器人科普--AGILOX 叉车 1 概述2 导航3 驱动轮组4 叉举参考 1 概述 AGILOX 叉车&#xff0c;不需要画地图路径&#xff0c;很厉害。 2 导航 中间路径自由导航&#xff0c;末端规划出轨迹路线&#xff0c;并使用优良的控制器做轨迹追踪。 AGILOX &#xff5c; 10 Min setu…...

Django的生命周期流程图(补充)、路由层urls.py文件、无名分组和有名分组、反向解析(无名反向解析、有名反向解析)、路由分发、伪静态

一、orm的增删改查方法&#xff08;补充&#xff09; 1. 查询resmodels.表名(类名).objects.all()[0]resmodels.表名(类名).objects.filter(usernameusername, passwordpassword).all()res models.表名(类名).objects.first() # 判断&#xff0c;判断数据是否有# res如果查询…...

selenium交互代码

一&#xff1a;selenium交互 用selenium打开网页后&#xff0c;也可以做一系列真人的操作&#xff0c;也就是利用selenium和浏览器进行交互&#xff0c;可利用以下几个函数进行操作&#xff1a; input.send_keys() 传递输入内容给某输入框button.click() 点击某按钮browser.e…...

下载远程服务器文件

业务需求:下载某云盘的视频文件存储到本地 测试代码 RequestMapping("testVideo")public String test() {try {SimpleDateFormat DATE_FORMAT new SimpleDateFormat("yyyy/MM/dd/");//组装本地保存地址StringBuilder filePath new StringBuilder(StoreP…...

[SQL挖掘机] - 索引

介绍: 当你在数据库中进行查询时&#xff0c;索引是一种用于提高查询性能的重要工具。索引是对表中的一列或多列进行排序的数据结构&#xff0c;它可以快速定位到满足特定条件的记录&#xff0c;从而减少了查询所需的时间和资源。 在数据库中使用索引的主要好处包括&#xff…...

C++STL库中的list

文章目录 list的介绍及使用 list的常用接口 list的模拟实现 list与vector的对比 一、list的介绍及使用 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器&#xff0c;并且该容器可以前后双向迭代。 2. list的底层是双向带头循环链表结构&#xff0c;双向带头循…...

【LeetCode 75】第十七题(1493)删掉一个元素以后全为1的最长子数组

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码运行结果&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 给一个数组&#xff0c;求删除一个元素以后能得到的连续的最长的全是1的子数组。 我们可以先单独统计出连续为1的子数组分别长度…...

配置IPv6 over IPv4 GRE隧道示例

组网需求 如图1&#xff0c;两个IPv6网络分别通过SwitchA和SwitchC与IPv4公网中的SwitchB连接&#xff0c;客户希望两个IPv6网络中的PC1和PC2实现互通。 其中PC1和PC2上分别指定SwitchA和SwitchC为自己的缺省网关。 图1 配置IPv6 over IPv4 GRE隧道组网图 配置思路 要实现I…...

Google Earth Engine谷歌地球引擎提取多波段长期反射率数据后绘制折线图并导出为Excel

本文介绍在谷歌地球引擎GEE中&#xff0c;提取多年遥感影像多个不同波段的反射率数据&#xff0c;在GEE内绘制各波段的长时间序列走势曲线图&#xff0c;并将各波段的反射率数据与其对应的成像日期一起导出为.csv文件的方法。 本文是谷歌地球引擎&#xff08;Google Earth Engi…...

第三大的数

414、第三大的数 class Solution {public int thirdMax(int[] nums) {Arrays.sort(nums);int tempnums[0];int ansnums[0];int count 0;// if(nums.length<3){// return nums[nums.length-1];// }// else {for(int inums.length-1;i>0;i--){if (nums[i]>nums[i…...

正则表达式中的方括号[]有什么用?

在正则表达式中&#xff0c;方括号 [] 是用于定义字符集合的元字符。它在正则表达式中有以下作用&#xff1a; 匹配字符集合中的任意一个字符&#xff1a;方括号中列出的字符&#xff0c;表示在这个位置可以匹配这些字符中的任意一个。例如&#xff0c;[abc] 将匹配任意一个字符…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...

篇章二 论坛系统——系统设计

目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...

GraphRAG优化新思路-开源的ROGRAG框架

目前的如微软开源的GraphRAG的工作流程都较为复杂&#xff0c;难以孤立地评估各个组件的贡献&#xff0c;传统的检索方法在处理复杂推理任务时可能不够有效&#xff0c;特别是在需要理解实体间关系或多跳知识的情况下。先说结论&#xff0c;看完后感觉这个框架性能上不会比Grap…...

第14节 Node.js 全局对象

JavaScript 中有一个特殊的对象&#xff0c;称为全局对象&#xff08;Global Object&#xff09;&#xff0c;它及其所有属性都可以在程序的任何地方访问&#xff0c;即全局变量。 在浏览器 JavaScript 中&#xff0c;通常 window 是全局对象&#xff0c; 而 Node.js 中的全局…...

Spring是如何实现无代理对象的循环依赖

无代理对象的循环依赖 什么是循环依赖解决方案实现方式测试验证 引入代理对象的影响创建代理对象问题分析 源码见&#xff1a;mini-spring 什么是循环依赖 循环依赖是指在对象创建过程中&#xff0c;两个或多个对象相互依赖&#xff0c;导致创建过程陷入死循环。以下通过一个简…...