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

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

最小生成树


用途:用最少的资源构建起支撑这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

目录
打赏
0
0
0
0
21
分享
相关文章
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
83 29
|
26天前
|
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
92 25
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
70 23
|
1月前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
65 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
53 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
51 10
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
54 2
|
3月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
364 9
|
3月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
58 1
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
157 77