【数据结构和算法】图的应用(最小生产树、最短路径、拓扑排序、关键路径)

简介: 【数据结构和算法】图的应用(最小生产树、最短路径、拓扑排序、关键路径)

最小生成树


用途:用最少的资源构建起支撑这n个节点的一张网或图

1、概念

  • 生成树(要求连通但是没有回路)

image.png

  • 一个图可以有许多颗不同的生成树
  • 所有生成树的共同特点:


  1. 生成树的顶点个数与图的顶点个数相同
  2. 生成树是图的极小连通子图,去掉一条边则非连通
  3. 一个有n个顶点的连通图的生成树有n-1条边
  4. 在生成树中再加一条边必然形成回路
  5. 生成树中任意两个顶点间的路径是唯一的


  • 含n个顶点n-1条边的图不一定是生成树
  • 构造生成树的思路(以无向图的生成树为例)


  1. 利用深度优先遍历搜索得到

image.png

  1. 利用广度优先遍历搜索得到

image.png

  1. 总结

image.png

  • 定义

image.png

  • 应用

(n个城市最少就是n-1条路,确保连通,最多有Cn2条路)

image.png


2、MST概念

MST性质:

image.png

MST性质例子:

image.png


 此时,u是顶点集v的非空子集,再V-U集合就是差集。其中,以v1为例,其和v2,v3,v4都有一条边,其中v1到v3边的权值最小,根据MST性质,就是说其一定会包含在某一颗最小生成树中。


MST性质解释

image.png

ps:如果加上了这条边会造成回路,再忽略再选取其他权值最小的边。


3、实现

  • 构造最小生成树方法一:普里姆算法(Prim算法)

image.png

  • 过程:
  1. 假设一开始v1在u集合中,而u集合此时与差集只有v1-v2/v3/v43条边,选出其中权值最短的边v1-v3,权值是1,再将v3加入u集合。
  2. 此时,u集合中有v1,v3两个顶点,这两个顶点与其他的顶点间权值最小的边是v3-v6,权值是4,然后将v6也加入u集合。
  3. 此时,u集合中有v1,v3,v6,此时与其他顶点最短的边是v6-v4,权值是2的边,所以将v4也加入u集合。
  4. 此时,u集合中有v1,v3,v4,v6,此时与其他顶点最短的边是v3-v2,权值是5,然后将v2也加入u集合。
  5. 此时,u集合中离v5最短的边是v2-v5,将最后的v5加入u集合,结束,此时所选的边加上顶点就是最小生成树。


  • 构造最小生成树方法二:克鲁斯卡尔(Kruskal算法)

(将权值最小的边由小到大排序,不断的选取权值最小的边,前提是不能形成环)

image.png

(最小生成树不唯一)

image.png

  • 两种算法的比较

image.png

(提示:由于Kruscal算法是按边来操作,而稀疏图的边比较少,所以适合稀疏图)


最短路径


  • 用途:求两点间最短路径或某源点到其他各点最短路径

1、概念

  • 问题:

image.png

  • 第一类问题:两点间最短路径

image.png

可见,第二条路径最短最优

  • 第二类问题:某源点到其他各点最短路径

image.png

  • 实现的算法:

image.png


2、实现

Dijkstra(迪杰斯特拉)算法

单源最短路径 — Dijkstra(迪杰斯特拉)算法

image.png


实现思路:按路径长度递增次序产生最短路径

image.png


例子

image.png


分析:

  1. 一开始的S集合中只有v0,此时v0里其他顶点的距离如图所示,其中到达不了的设为无穷大。其中v0到v2的距离最短,为8,所以选取v2加入S集合,此后就不需要再对比到v2的距离。
  2. 此时S的集合中有V0,v2,再次看看有了V2顶点的加入,能不能剪短到其他顶点的距离。可见,有了v2的加入,v0可以到达v3,距离为13,最短的距离,但是v0到v1也是最短的距离。所以这一次选取v1加入S集合,此后不需要再对比v1的距离。
  3. 此时S的集合中有v0,v1,v2,再次看看有了v1顶点的加入,能不能剪短到其他顶点的距离。可见,有了v1的加入,v0又可以到达v5,v6,但是这次的最短距离是上次的v2到v3,所以选取v3加入S集合,此后不再需要对比v3的距离
  4. 此时S的集合中有v0,v1,v2,v3,再次看看有了v3顶点的加入,能不能剪短到其他顶点的距离。可见,有了v3的加入,v0又可以到达v4,切这次到达v4的距离更短,为19,比此时其他的距离都短。所以选取v4加入S集合,此后不再需要对比v4的距离.
  5. 此时S的集合中有v0,v1,v2,v3,v4,再次看看有了v4顶点的加入,能不能剪短到其他顶点的距离。可见,有了v4的加入,v0又可以到达v5,且这次到达v5的距离更短,为21,但是v0到v6的距离更短。所以选取v6加入S集合,此后不再需要对比v6的距离.
  6. 最后一次,选取v5加入S集合,此时全部的顶点都加入了S集合,算法结束。


弗洛伊德(Floyd)算法

  • 所有顶点间的最短路径

方法一:每次以一个顶点为源点,重复执行Dijkstra算法n次。

方法二:弗洛伊德(Floyd)算法


  • 算法思路

image.png

  • 例子:

image.png

  • 分析:
  1. 本来的路径长度如图所示。
  2. 加入了A顶点之后,本案例C是不能到达B的,所有距离是无穷大,但是增加了A顶点之后,C可以到达B,距离为3+4=7,所以表格的距离修改为7.
  3. 加入了B顶点之后,本来A去C只能是11,但是现在可以借住B来到达C,距离更短,为6.
  4. 加入了C顶点之后,本来B去A需要6个距离,现在借助C,2+3=5,距离更短。
  5. 算法结束,此时就得到了有向网中的所以顶点的最短路径。经过的顶点和路径权值如最后的表所示。


拓扑排序


用途判断AOE网中是否存在环。

1、概念

有向无环图:无环的有向图,简称DAG图

image.png


用途

image.png


AOV网与AOE网

image.png

ps:通常AOV网用来解决拓扑排序问题,而AOE网用来解决关键路径问题。


AOV网的特点

image.png

其中:

C1是C4的直接前驱,C4是C1的直接后继

C1是C5的前驱,C5是C1的后继


问题:如何判断AOV网中是否存在回路? ---- 拓扑排序

拓扑排序的定义

image.png


2、拓扑排序的方法

image.png

例子:过程如下所示(拓扑序列不唯一)

image.png

image.png

image.png

image.png

image.png

不唯一

image.png

检测AOV网中是否存在环的方法:

image.png

否则互相存在前驱必有环。


关键路径


引子

image.png


建模(AOE网的抽象)

image.png

解析:其中的v1->v2,表示菜单定制活动开始,到v2菜单定制活动结束,花费的时间A=20分钟。其他同理。


建模二

image.png

将问题转化为求解关键路径问题–根据AOE网求解关键路径


关键路径所需的一些描述量

image.png

描述量的求解方法

image.png


最早发生时间求解例子 – 正在算

image.png

解析:尽管v1只需2天的时间就到了Vu活到开始,再过1天时间就可以结束。但是v1到Vx要长达82天的时间,而之后还有进行6天才能结束,所以要提前82+6天才能确保活到完成,这个时间也就是最早发生时间。


最晚发生时间求解例子 – 逆着算

image.png

示例

image.png

如图所示:

时间余量为0的活动就是关键活动,由关键活动组成的路径就是关键路径。


总结

image.png

目录
相关文章
|
4月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
118 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
5天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》图、查找、排序专题考点(含解析)
408考研——《数据结构》图,查找和排序专题考点选择题汇总(含解析)。
56 29
|
29天前
|
存储 人工智能 算法
【C++数据结构——图】最短路径(头歌教学实验平台习题) 【合集】
任务描述 本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。 相关知识 为了完成本关任务,你需要掌握:Dijkst本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。为了完成本关任务,你需要掌握:Dijkstra算法。带权有向图:该图对应的二维数组如下所示:Dijkstra算法:Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。Dijkstra算法的具体步骤如下:(1)初始时,S只包含源点,即S={v},v的距离为0。
53 15
|
29天前
|
存储 人工智能 算法
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
34 10
|
29天前
|
搜索推荐 算法 数据处理
【C++数据结构——内排序】希尔排序(头歌实践教学平台习题)【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括: - **任务描述**:实现希尔排序算法。 - **相关知识**: - 排序算法基础概念,如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列(增量序列)的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧,如循环嵌套和索引计算。 - **测试说明**:提供了测试输入和输出示例,帮助验证代码正确性。 - **我的通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了代码运行的测试结果。 通过这些内容,读者可以全面了解希尔排序的原理和实现方法。
52 10
|
29天前
|
搜索推荐 C++
【C++数据结构——内排序】快速排序(头歌实践教学平台习题)【合集】
快速排序是一种高效的排序算法,基于分治策略。它的主要思想是通过选择一个基准元素(pivot),将数组划分成两部分。一部分的元素都小于等于基准元素,另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序,最终使整个数组有序。(第一行是元素个数,第二行是待排序的原始关键字数据。本关任务:实现快速排序算法。开始你的任务吧,祝你成功!
38 7
|
29天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
47 2
|
3月前
|
算法
树的遍历算法有哪些?
不同的遍历算法适用于不同的应用场景。深度优先搜索常用于搜索、路径查找等问题;广度优先搜索则在图的最短路径、层次相关的问题中较为常用;而二叉搜索树的遍历在数据排序、查找等方面有重要应用。
56 2
|
4月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
42 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)

热门文章

最新文章