Resolve data structures - traversal and application of graphs

51CTO 2022-08-06 19:33:15 阅读数:1,008

resolvedatastructurestraversalapplication

化解数据结构----图的遍历和应用_生成树

图知识框架:化解数据结构----图的遍历和应用_插入图片_02

图的遍历和应用

一、图的遍历

定义:
从已给的连通图中某一顶点出发,沿着一些边访遍图中所有的顶点,且使每个顶点仅被访问一次,就叫做图的遍历,它是图的基本运算.
遍历实质: 找每个顶点的邻接点的过程.

图的特点:
图中可能存在回路,且图的任一顶点都可能与其它顶点相通,在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点.
怎样避免重复访问?
解决思路:设置辅助数组visited [n ],用来标记每个被访问过的顶点.
· 初始状态visited[i]为0
· 顶点i被访问,改visited [0]为1,防止被多次访问

1.深度优先遍历(DFS)

例如我们访问图的顶点的次数时,按照顺序如下:
化解数据结构----图的遍历和应用_生成树_03
同时,如果放到迷宫里,我们按照如下箭头顺序来进行访问:
化解数据结构----图的遍历和应用_插入图片_04
我们来详细的进行分析:
以这个图为例↓↓↓
化解数据结构----图的遍历和应用_生成树_05
顶点访问次序:
V1→V2→V4→V8→V5→V3→V6→V7
V1→V2→V5→V8→V4→V3→V6→V7
V1→V2→V4→V8→V5→V3→V7→V6
V1→V2→V5→V8→V4→V3→V7→V6
V1→V3→V6→V7→V2→V4→V8→V5
即:连通图的深度优先遍历类似于树的先根遍历

2.深度优先遍历算法的实现

邻接矩阵表示的无向图深度遍历实现:
化解数据结构----图的遍历和应用_插入图片_06
辅助数组在每次遍历之后,如果数的值为0则表示还未遍历,就会遍历这个数,并将其对应的数组中的值由0变为1.
化解数据结构----图的遍历和应用_最小生成树_07
算法代码:
化解数据结构----图的遍历和应用_插入图片_08

2.1 DFS算法效率分析

  1. 邻接矩阵来表示图,遍历图中的每一个顶点都要从头扫描到该顶点所在的行,时间复杂度为O(n^2)
  2. 邻接表表示图,虽然有2e个表结点,但只需要扫描e个结点即可完成遍历,加上访问n个头结点的时间,时间复杂度为O(n+e).

结论:
稠密图适于在邻接矩阵上进行深度遍历
稀疏图适于在邻接表上进行深度遍历

2.2 非连通图的遍历

先遍历完一个图之后再遍历另一个图.
化解数据结构----图的遍历和应用_最小生成树_09

3.广度优先遍历(BFS)

方法:从图的某一结点出发,首先依次访问该结点的所有邻接点Vi, Vi2....,Vi,再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点
重复此过程,直至所有顶点均被访问为止.
化解数据结构----图的遍历和应用_插入图片_10

4.广度优先遍历算法的实现

化解数据结构----图的遍历和应用_生成树_11

化解数据结构----图的遍历和应用_最小生成树_12

4.1BFS算法效率问题

1.如果使用邻接矩阵,则BFS对于每一个被访问到的顶点,都要循环检测矩阵中的整整一行(n个元素),总的时间代价为O(n^2).
2.用邻接表来表示图,虽然有2e个表结点,但只需扫描e个结点即可完成遍历,加上访问n个头结点的时间,时间复杂度为O(n+e).

5.DFS与BFS算法效率比较

·空间复杂度相同,都是O(n)(借用了堆栈或队列) ;
·时间复杂度只与存储结构(邻接矩阵或邻接表)有关,而与搜索路径无关.O(n^2)和O(n+e)

二、图的应用

1.最小生成树

1.1生成树概念

生成树: 所有顶点均由边连接在一起,但不存在回路的图.
—个图可以有许多棵不同的生成树
化解数据结构----图的遍历和应用_最小生成树_13
图 2、3、4都是图1的生成树

所有生成树具有以下共同特点
1.生成树的顶点个数与图的顶点个数相同;.
2.生成树是图的极小连通子图,去掉一条边则非连通
3.一个有n个顶点的连通图的生成树有n-1条边;
4.在生成树中再加一多边必然形成回路.

但是:含有n个顶点的n-1条边的图却不一定是生成树.

1.2最小生成树

化解数据结构----图的遍历和应用_最小生成树_14
最小生成树: 给定一个(无向网络)在该网的所有生成树中,使得各边权值之和最小的那棵生成树称为该网的最小生成树,也叫最小代价生成树.

1.3最小生成树的典型应用

化解数据结构----图的遍历和应用_生成树_15

1.4构造最小生成树

化解数据结构----图的遍历和应用_插入图片_16

1.5 MST性质解释

在生成树的构造过程中,图中n个顶点分属两个集合:

  • 已落在生成树上的顶点集:u
  • 尚未落在生成树上的顶点集: V-U

接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边.

化解数据结构----图的遍历和应用_生成树_17

1.6普里姆Prim算法

化解数据结构----图的遍历和应用_生成树_18

1.7 克鲁斯卡尔Kruskal算法

化解数据结构----图的遍历和应用_生成树_19
化解数据结构----图的遍历和应用_最小生成树_20
最小生成树不唯一

1.8 两种算法比较

化解数据结构----图的遍历和应用_生成树_21

2.最短路径

2.1典型用途

典型用途:交通网络的问题——从甲地到乙地之间是否有公路连通?在有多条通路的情况下,哪一条路最短?
交通网络用有向网来表示:

  • 顶点——表示地点
  • 弧——表示两个地点有路连通
  • 弧上的权值——表示两地点之间的距离、交通费或途中所花费的时间等

如何能够使一个地点到另一个地点的运输时间最短或运费最省?这就是一个求两个地点间的最短路径问题.
化解数据结构----图的遍历和应用_生成树_22

2.1两点间的最短路径

化解数据结构----图的遍历和应用_插入图片_23

2.3某源点到其它各点的最短路径

化解数据结构----图的遍历和应用_生成树_24

2.4 Dijistra算法

初始化–选择–更新
化解数据结构----图的遍历和应用_插入图片_25
化解数据结构----图的遍历和应用_插入图片_26
每次以一个顶点为源点,重复执行Dijkstra算法n次.时间复杂度为O(n^3).

2.5弗洛伊德Floyd算法

算法思想:

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

化解数据结构----图的遍历和应用_生成树_27

3.拓扑排序

3.1有向无环图及其应用

化解数据结构----图的遍历和应用_最小生成树_28
AOV网:
用一个有向图表示一个工程的各子工程及其相互制约的关系,其中以顶点表示活动,弧表示活动之间的优先制约关系,称这种有向图为顶点表示活动的网,简称AOV网(Activity On Vertex network).

AOE网:
用一个有向图表示一个工程的各子工程及其相互制约的关系,以弧表示活动,以顶点表示活动的开始或结束事件,称这种有向图为边表示活动的网,简称为AOE网(Activity On Edge)
化解数据结构----图的遍历和应用_插入图片_29

3.2 拓扑排序定义

在AOV网没有回路的前提下,我们将全部活动排列成一个线性序列,使得若AOV 网中有弧<i,j>存在,则在这个序列中, i一定排在j的前面,具有这种性质的线性序列称为拓扑有序序列,相应的拓扑有序排序的算法称为拓扑排序.

3.3 拓扑排序的方法

  1. 在有向图中选一个没有前驱的顶点且输出之.
  2. 从图中删除该顶点和所有以它为尾的弧.
  3. 重复上述两步,直至全部顶点均已输出;
    或者当图中不存在无前驱的顶点为止
    化解数据结构----图的遍历和应用_生成树_30
    化解数据结构----图的遍历和应用_最小生成树_31
    化解数据结构----图的遍历和应用_生成树_32
    化解数据结构----图的遍历和应用_生成树_33
    化解数据结构----图的遍历和应用_生成树_34
    化解数据结构----图的遍历和应用_生成树_35
    化解数据结构----图的遍历和应用_插入图片_36
    化解数据结构----图的遍历和应用_最小生成树_37
    化解数据结构----图的遍历和应用_插入图片_38

………………………………………………………………………………………
化解数据结构----图的遍历和应用_插入图片_39

一个AOV网的拓扑序列是不唯一的!

3.4拓扑排序重要应用

检测AOV网中是否存在环方法
对有向图构造其顶点的拓扑有序序列,若网中所有顶点都在它的拓扑有序序列中,则该AOV 网必定不存在环.

4.关键路径

4.1定义

把工程计划表示为边表示活动的网络,即AOE网,用顶点表示事件,弧表示活动,弧的权表示活动持续时间.
**事件** 表示在它之前的活动已经完成,在它之后的活动可以开始.
化解数据结构----图的遍历和应用_插入图片_40

4.2举例

对于AOE网,我们关心两个问题:
(1)完成整项工程至少需要多少时闻?
(2)哪些活动是影响工程进度的关键?

化解数据结构----图的遍历和应用_生成树_41

关键路径——路径长度最长的路径.
路径长度——路径上各活动持续时间之和.

化解数据结构----图的遍历和应用_最小生成树_42

4.3关键时间

化解数据结构----图的遍历和应用_生成树_43

4.4举例说明

化解数据结构----图的遍历和应用_最小生成树_44
2.
化解数据结构----图的遍历和应用_生成树_45

4.5求解关键路径步骤

化解数据结构----图的遍历和应用_生成树_46

4.6关键路径中的讨论

化解数据结构----图的遍历和应用_生成树_47

好啦,这就是今天要分享给大家的全部内容了
️️️如果你喜欢的话,就不要吝惜你的一键三连了~

化解数据结构----图的遍历和应用_插入图片_48
化解数据结构----图的遍历和应用_插入图片_49

copyright:author[51CTO],Please bring the original link to reprint, thank you. https://en.javamana.com/2022/218/202208061926112785.html