首页 > 其他分享 >数据结构——非线性结构(图)

数据结构——非线性结构(图)

时间:2022-12-26 21:33:05浏览次数:53  
标签:连通 遍历 复杂度 非线性 路径 算法 顶点 数据结构 结构


文章目录

  • ​​一. 非线性结构的概述​​
  • ​​二. 图的基本概念​​
  • ​​1. 定义​​
  • ​​2. 无向图、有向图​​
  • ​​2.1 无向图​​
  • ​​2.2 有向图​​
  • ​​2.3 简单图​​
  • ​​2.4 多重图​​
  • ​​3. 顶点的度、出度、入度​​
  • ​​3.1 对于无向图​​
  • ​​3.2 对于有向图​​
  • ​​4. 边的权、带权图 (网)​​
  • ​​5. 点到点的关系​​
  • ​​5.1 顶点与顶点之间的关系描述​​
  • ​​5.2 连通的、强连通的、连通图、强连通图​​
  • ​​6. 图的局部​​
  • ​​6.1 无向图子图、生成子图​​
  • ​​6.2 有向图子图、生成子图​​
  • ​​6.3 连通分量​​
  • ​​6.4 强连通分量​​
  • ​​7. 几种特殊形态的图​​
  • ​​7.1 生成树​​
  • ​​7.2 生成森林​​
  • ​​7.3 无向完全图和有向完全图​​
  • ​​7.4 稀疏图和稠密图​​
  • ​​7.5 生成树和有向树​​
  • ​​三. 图的存储​​
  • ​​1. 邻接矩阵法​​
  • ​​1.1 定义​​
  • ​​1.2 邻接矩阵存储有向图和无向图​​
  • ​​1.3 邻接矩阵存储带权图(网)​​
  • ​​1.4 邻接矩阵法的性能分析​​
  • ​​1.5 邻接矩阵法的性质​​
  • ​​2. 邻接表法​​
  • ​​2.1 来源​​
  • ​​2.2 定义(采用顺序存储和链式存储结合)​​
  • ​​2.3 邻接表法的性质​​
  • ​​2.4 邻接表和邻接矩阵的比较​​
  • ​​3. 十字链表(只能存储有向图)​​
  • ​​3.1 来源​​
  • ​​3.2 定义​​
  • ​​3.3 十字链表法性能分析​​
  • ​​4. 邻接多重表(只能存储无向图)​​
  • ​​4.1 来源​​
  • ​​4.2 定义​​
  • ​​4.3 邻接多重表性能分析​​
  • ​​5. 四种存储结构的比较​​
  • ​​四. 图的基本操作​​
  • ​​五. 图的遍历​​
  • ​​1. 广度优先搜索(BFS遍历)​​
  • ​​1.1 概述​​
  • ​​1.2 复杂度分析​​
  • ​​1.3 广度优先生成树​​
  • ​​2. 深度优先搜索(DFS遍历)​​
  • ​​2.1 概述​​
  • ​​2.2 复杂度分析​​
  • ​​2.3 深度优先生成树​​
  • ​​3. 图的遍历和图的连通性​​
  • ​​3.1 对于无向图​​
  • ​​3.2 对于有向图​​
  • ​​六. 图的应用​​
  • ​​1. 最小生成(代价)树​​
  • ​​1.1 概述​​
  • ​​1) 来源​​
  • ​​2) 定义​​
  • ​​3) 性质​​
  • ​​1.2 求最小生成树的两种算法​​
  • ​​1) Prim算法​​
  • ​​2) Kruskal算法​​
  • ​​3) 两个算法的比较​​
  • ​​2. 最短路径​​
  • ​​2.1 定义​​
  • ​​2.2 分类​​
  • ​​1)BFS求无权图的单源最短路径​​
  • ​​2)Dijkstra算法求单源最短路径​​
  • ​​3)Floyd算法求各顶点之间最短路径​​
  • ​​2.3 三种算法的比较​​
  • ​​3. 有向无环图描述表达式​​
  • ​​3.1 概述​​
  • ​​3.2 DAG描述表达式​​
  • ​​3.3 解题方法​​
  • ​​4. 拓扑排序​​
  • ​​4.1 AOV网​​
  • ​​4.2 拓扑排序概述​​
  • ​​4.3 拓扑排序常用方法​​
  • ​​4.4 拓扑排序复杂度​​
  • ​​4.5 逆拓扑排序​​
  • ​​5. 关键路径​​
  • ​​5.1 AOE网​​
  • ​​5.2 关键路径概述​​
  • ​​5.3 求关键路径的步骤​​
  • ​​5.4 关键路径的特性​​

一. 非线性结构的概述

数据结构——非线性结构(图)_图论

二. 图的基本概念

1. 定义

数据结构——非线性结构(图)_算法_02

2. 无向图、有向图

2.1 无向图

数据结构——非线性结构(图)_图论_03

2.2 有向图

数据结构——非线性结构(图)_图论_04

2.3 简单图

数据结构——非线性结构(图)_有向图_05

2.4 多重图

数据结构——非线性结构(图)_图论_06

3. 顶点的度、出度、入度

3.1 对于无向图

数据结构——非线性结构(图)_图论_07

3.2 对于有向图

数据结构——非线性结构(图)_图论_08

4. 边的权、带权图 (网)

数据结构——非线性结构(图)_有向图_09

5. 点到点的关系

5.1 顶点与顶点之间的关系描述

数据结构——非线性结构(图)_图论_10

5.2 连通的、强连通的、连通图、强连通图

数据结构——非线性结构(图)_图论_11


如果本身就是连通图,则本身就是其连通分量,而非连通图的各个连通图作为其组成部分均为其连通分量


强连通图:任意顶点出发可以到达其余任意节点

  • 假设一个图有n个节点,如果边数小于n-1,那么此图必是非连通图
  • 一个图有n个顶点,并且有大于n-1条边,则此图一定有环

6. 图的局部

6.1 无向图子图、生成子图

数据结构——非线性结构(图)_有向图_12

6.2 有向图子图、生成子图

数据结构——非线性结构(图)_有向图_13

6.3 连通分量

数据结构——非线性结构(图)_有向图_14


极小连通子图:保证了连通,且有着最少的边数

6.4 强连通分量

数据结构——非线性结构(图)_算法_15

7. 几种特殊形态的图

7.1 生成树

数据结构——非线性结构(图)_有向图_16

7.2 生成森林

数据结构——非线性结构(图)_算法_17

7.3 无向完全图和有向完全图

数据结构——非线性结构(图)_图论_18

7.4 稀疏图和稠密图

数据结构——非线性结构(图)_有向图_19

7.5 生成树和有向树

数据结构——非线性结构(图)_图论_20

三. 图的存储

  • 要根据不同图的结构和算法,采用不同存储结构,以使的程序的效率最大化
  • 由于图的结构比较复杂,任意两个顶点之间都有可能存在联系,因此无法以数据元素在内存中的物理位置来表示元素之间的关系

1. 邻接矩阵法

1.1 定义

  • 顶点不分大小、主次,所以用一个一维数组存储图中顶点的信息
  • 边或弧由于是顶点之间的关系,用一个二维数组存储图中边的信息(这个二维数组称为邻接矩阵)

1.2 邻接矩阵存储有向图和无向图

数据结构——非线性结构(图)_图论_21


数据结构——非线性结构(图)_算法_22

1.3 邻接矩阵存储带权图(网)

数据结构——非线性结构(图)_图论_23


数据结构——非线性结构(图)_图论_24


数据结构——非线性结构(图)_数据结构_25

1.4 邻接矩阵法的性能分析

数据结构——非线性结构(图)_有向图_26

1.5 邻接矩阵法的性质

性质1:

数据结构——非线性结构(图)_算法_27

性质2:

数据结构——非线性结构(图)_图论_28

2. 邻接表法

2.1 来源

由于邻接矩阵是使用数组实现的顺序存储,空间复杂度高,不适合存储稀疏图。

数据结构——非线性结构(图)_图论_29

2.2 定义(采用顺序存储和链式存储结合)

数据结构——非线性结构(图)_图论_30


数据结构——非线性结构(图)_数据结构_31


数据结构——非线性结构(图)_邻接矩阵_32

2.3 邻接表法的性质

性质1:

数据结构——非线性结构(图)_有向图_33


性质2:

数据结构——非线性结构(图)_有向图_34

2.4 邻接表和邻接矩阵的比较

数据结构——非线性结构(图)_算法_35


tip

  • 空间复杂度只与存储的节点数有关,与边数无关

3. 十字链表(只能存储有向图)

3.1 来源

数据结构——非线性结构(图)_图论_36

3.2 定义

是有向图的一种链式存储结构:将邻接表和逆邻接表整合在一起

数据结构——非线性结构(图)_数据结构_37


数据结构——非线性结构(图)_有向图_38


数据结构——非线性结构(图)_邻接矩阵_39

3.3 十字链表法性能分析

数据结构——非线性结构(图)_邻接矩阵_40

  • 十字链表中容易求得顶点的出度和入度
  • 图的十字链表表示是不唯一的,但一个十字链表表示确定一个图

4. 邻接多重表(只能存储无向图)

4.1 来源

在邻接表中,容易求得顶点和边的各种信息,但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时,需要分别在两个顶点的边表中遍历,效率较低

数据结构——非线性结构(图)_算法_41

4.2 定义

邻接多重表是无向图的另一种链式存储结构

数据结构——非线性结构(图)_有向图_42


数据结构——非线性结构(图)_有向图_43

4.3 邻接多重表性能分析

数据结构——非线性结构(图)_有向图_44

5. 四种存储结构的比较

数据结构——非线性结构(图)_算法_45

四. 图的基本操作

图的基本操作是独立于图的存储结构的。不同的存储结构,操作算法有着不同的的性能。

数据结构——非线性结构(图)_邻接矩阵_46

五. 图的遍历

1)什么是图的遍历?

  • 指从图中某一顶点出发,按照某种搜索方法沿着图中的边对图中的所有节点访问一次且仅访问一次

2) 图遍历与树遍历的关系

  • 树遍历本质上也视为一种特殊的图遍历

3)为什么需要图的遍历

  • 为了求解图的连通性
  • 为了进行拓扑排序
  • 为了求关键路径

4)图遍历的关键是什么?

  • 为了避免同一顶点被访问多次,在遍历图的过程中必须记下已访问过的顶点(可设一个辅助数组visited[ ]标记顶点)

1. 广度优先搜索(BFS遍历)

1.1 概述

1)树的广度优先搜索

  • 也就是二叉树的层序遍历
  • 访问完第一层节点之后再访问第二层节点

2)图的广度优先搜索(Breadth-First-Search)

  • 是二叉树层次遍历算法的扩展
  • 从某个节点开始访问,访问完该节点后,访问与该节点相邻的且未被访问过的节点,再从这些访问过的节点出发,访问他们所有未被访问的相邻节点,直至所有节点被访问完为止。此时若图中还有节点未被访问,则另外选一个未被访问的节点作为起始节点,重复上面过程。

3)树和图的广度优先遍历的比较

数据结构——非线性结构(图)_图论_47

广度优先遍历是一种分层查找过程,为了实现逐层的访问,算法必须借助一个辅助队列,以记忆正在访问的顶点的下一层顶点。

4)广度优先遍历序列

数据结构——非线性结构(图)_数据结构_48

tip

  • 广度优先搜索以起始结点为中心,一层一层地向外层扩展遍历图的顶点,因此无法考虑到边权值,只适合求边权值相等的图的单源最短路径

1.2 复杂度分析

1)空间复杂度

数据结构——非线性结构(图)_算法_49

2)时间复杂度

数据结构——非线性结构(图)_邻接矩阵_50

1.3 广度优先生成树

数据结构——非线性结构(图)_邻接矩阵_51


数据结构——非线性结构(图)_有向图_52


扩展:广度优先生成森林

数据结构——非线性结构(图)_有向图_53

2. 深度优先搜索(DFS遍历)

2.1 概述

1)树的深度优先遍历

  • 从根节点出发,能往更深处走就尽量往深处走。每当访问一个节点的时候,要检查是否还有与当前节点相邻的且没有被访问过的节点,如果有的话就往下一层钻。

2)图的深度优先遍历(Depth-First-Search)

  • 与树的先根遍历类似
  • 算法思想:首先访问图中某一起始顶点,然后由该顶点出发,访问与该顶点相邻且没有被访问的任意顶点w,在访问与w相邻且没有被访问的任意顶点x。当不能继续访问时,依次向后退到最近被访问的顶点,判断是否有邻接顶点被访问。
  • DFS算法是一个递归算法,需要借助一个递归工作栈,故其空间复杂度为O(|V|)。

3)深度优先遍历序列

数据结构——非线性结构(图)_算法_54


数据结构——非线性结构(图)_算法_55


tip

  • 利用深度优先遍历可以判断图G中是否存在回路。对于无向图来说,若深度优先遍历过程中遇到了回边,则必定存在环

2.2 复杂度分析

1)空间复杂度

数据结构——非线性结构(图)_有向图_56


2)时间复杂度

数据结构——非线性结构(图)_有向图_57

2.3 深度优先生成树

数据结构——非线性结构(图)_数据结构_58


数据结构——非线性结构(图)_有向图_59

扩展:深度优先生成森林

  • 非连通,需要调用多次DFS函数

数据结构——非线性结构(图)_有向图_60

3. 图的遍历和图的连通性

图的遍历算法可以用来判断图的连通性

3.1 对于无向图

数据结构——非线性结构(图)_图论_61

3.2 对于有向图

数据结构——非线性结构(图)_算法_62

六. 图的应用

1. 最小生成(代价)树

1.1 概述

1) 来源

数据结构——非线性结构(图)_邻接矩阵_63

2) 定义

一个带权的图中(网),有n个顶点,用n-1条边把一个连通图连接起来,并要使的权值的和最小。

数据结构——非线性结构(图)_邻接矩阵_64

3) 性质

数据结构——非线性结构(图)_邻接矩阵_65


数据结构——非线性结构(图)_邻接矩阵_66

1.2 求最小生成树的两种算法

都是基于贪心算法策略

1) Prim算法

从某一个顶点出发,找一条与顶点集权值最小的边相连

算法思想:

  • 从顶点开始扩展最小生成树
  • 从某一个顶点开始构建生成树;每次将代价最小的新顶点纳入生成树,直到所有顶点都纳入为止
  • 算法的执行非常类似于寻找图的最短路径的Dijkstra算法

算法演示:

数据结构——非线性结构(图)_图论_67

算法总结:

  • 同一个图最小生成树的方案可能不只一个,但是最小代价是相同的
  • 不同起点图构成的生成树可能方案是相同的

2) Kruskal算法

每次选边权值最小的相连,顶点已连接的,边就不需要连接了。

算法思想:

  • 按权值的递增次序选择合适的边来构造最小生成树
  • 每次选择一条权值最小的边,使这条边的两头连通(原本已经连通的就不选)直到所有节点都连通

算法演示:

数据结构——非线性结构(图)_数据结构_68

3) 两个算法的比较

数据结构——非线性结构(图)_图论_69

  • Prim算法的时间复杂度为O(|V|^2),不依赖于|E|
  • 在Kruskal算法中,采用堆来存放边的集合,因此每次选择最小权值的边只需O (log|E|) 的时间。由于生成树T中的所有边可视为一个等价类,因此每次添加新的边的过程类似于求解等价类的过程,由此可以采用并查集的数据结构来描述T,从而构造T的时间复杂度为O (|Elog|E|)

2. 最短路径

2.1 定义

数据结构——非线性结构(图)_算法_70

2.2 分类

数据结构——非线性结构(图)_邻接矩阵_71

数据结构——非线性结构(图)_图论_72

  • 单源最短路径:从源点到其余各顶点的最短路径

1)BFS求无权图的单源最短路径

数据结构——非线性结构(图)_有向图_73

数据结构——非线性结构(图)_数据结构_74

缺点:BFS算法只适用于无权图,或所有边的权值都相同的图

2)Dijkstra算法求单源最短路径

算法思想:

  • 基于贪心策略

算法时间复杂度:

  • 使用邻接矩阵表示时,时间复杂度为O (|V|^2)。
  • 使用带权的邻接表表示时,虽然修改dist[]的时间可以减少,但由于在dist[]中选择最小分量的时间不变,时间复杂度仍为O (|V|^2)

Prim算法和Dijkstra算法区别:

两者的区别在于,每次更新路径的不一样

  • prim更新的是已标记集合到未标记集合之间的距离
  • Dijkstra更新的是源点到未标记集合之间的距离

参考文献:
​​​​https://zhuanlan.zhihu.com/p/87748517​

算法不足:

数据结构——非线性结构(图)_图论_75

  • 其最短路径长度加上这条负边的权值结果可能小于原先确定的最短路径长度,而此时a在Dijkstra算法下是无法更新的

3)Floyd算法求各顶点之间最短路径

算法思想:

数据结构——非线性结构(图)_有向图_76

算法演示:

数据结构——非线性结构(图)_邻接矩阵_77


数据结构——非线性结构(图)_数据结构_78

数据结构——非线性结构(图)_邻接矩阵_79


数据结构——非线性结构(图)_数据结构_80


数据结构——非线性结构(图)_邻接矩阵_81


数据结构——非线性结构(图)_有向图_82


数据结构——非线性结构(图)_图论_83

算法时间复杂度:

数据结构——非线性结构(图)_数据结构_84

算法的缺点:

  • Floyd算法虽然用于负权值带权图,但不能解决负权回路图

2.3 三种算法的比较

数据结构——非线性结构(图)_图论_85

3. 有向无环图描述表达式

3.1 概述

数据结构——非线性结构(图)_有向图_86


有向无环图是描述含有公共子式的表达式的有效工具

数据结构——非线性结构(图)_有向图_87

  • 用二叉树来描述表达式时,有相同的子表达式
  • 利用有向无环图,则可实现对相同子式的共享,从而节省存储空间

3.2 DAG描述表达式

数据结构——非线性结构(图)_数据结构_88

3.3 解题方法

数据结构——非线性结构(图)_算法_89

4. 拓扑排序

4.1 AOV网

Activity on Vertex Network(AOV)网:一个有向图中,顶点表示活动,弧表示活动之间优先关系(不能存在回路)这样有向图为顶点表示活动的AOV网

数据结构——非线性结构(图)_图论_90


特点:

  • 活动Vi是活动Vj的直接前驱,活动Vj是活动Vi的直接后继,这种前驱和后继关系具有传递性,且任何活动Vi不能以它自己作为自己的前驱或后继

4.2 拓扑排序概述

定义:

  • 对一个有向图构造拓扑序列的过程,即找一条从顶点Vi到Vj的一条路径且顶点序列中Vi必须在Vj之前

作用:

  • 解决一个工程能否顺利进行的问题

目的:

  • 找到做事的先后顺序

数据结构——非线性结构(图)_算法_91

4.3 拓扑排序常用方法

数据结构——非线性结构(图)_有向图_92

数据结构——非线性结构(图)_图论_93

4.4 拓扑排序复杂度

数据结构——非线性结构(图)_算法_94


由于输出每个顶点的同时还要删除以它为起点的边

  • 故采用邻接表存储时拓扑排序的时间复杂度为O(|V|+|E|)
  • 采用邻接矩阵存储时拓扑排序的时间复杂度为O(|V|^2)

4.5 逆拓扑排序

数据结构——非线性结构(图)_邻接矩阵_95


特点:

  • 逆拓扑排序序列可能不唯一

5. 关键路径

5.1 AOE网

定义:

数据结构——非线性结构(图)_邻接矩阵_96


数据结构——非线性结构(图)_图论_97

性质:

数据结构——非线性结构(图)_图论_98

AOV网和AOE网的异同:

  • 同:都是有向无环图
  • 异:AOE网:边有权值;AOV网:边无权值,仅表示顶点之间前后关系

数据结构——非线性结构(图)_有向图_99


数据结构——非线性结构(图)_邻接矩阵_100

5.2 关键路径概述

  • 解决工程完成需要的最短时间问题,分析他们拓扑关系,找到当中最关键的流程,这个流程时间就是最短时间
  • 路径上各个活动持续的时间之后称为路径长度,从源点到终点具有最大长度的路径叫做关键路径,关键路径上的活动叫做关键活动

数据结构——非线性结构(图)_邻接矩阵_101


数据结构——非线性结构(图)_图论_102

找关键活动时所需的参量:

数据结构——非线性结构(图)_邻接矩阵_103


ve(k) = e(i)

数据结构——非线性结构(图)_图论_104


l(i) = vl(k)-weight

数据结构——非线性结构(图)_有向图_105

5.3 求关键路径的步骤

数据结构——非线性结构(图)_邻接矩阵_106


数据结构——非线性结构(图)_算法_107


数据结构——非线性结构(图)_图论_108


数据结构——非线性结构(图)_算法_109

5.4 关键路径的特性

数据结构——非线性结构(图)_数据结构_110


数据结构——非线性结构(图)_数据结构_111


参考文献:王道数据结构


标签:连通,遍历,复杂度,非线性,路径,算法,顶点,数据结构,结构
From: https://blog.51cto.com/u_15923298/5971076

相关文章

  • 网络拓扑结构可视化呈现方案
    随着数字化进程的加速,企业网络中设备的数量日益快速增长,网络规模逐渐庞大,组网结构、IT环境变的无比复杂,需要花费大量的时间和资源去监测网络运行状态,诊断解决故障问题。面......
  • 结构 Structs
    与引用类型Class不一样,结构体是一种值类型的数据结构,通过使用Struct关键字,我们可以在一个单一的变量中直接存储各种各样复杂的数据结构。语法:[访问修饰符]struct结构体......
  • js中的数据结构
    原始类型  数值字符串布尔值特殊值:undefined  null  合成类型 对象es6唯一的标识符symboljs中有三种方法确定一个值得类型typeofinstanceofObject.p......
  • [oeasy]python0033_任务管理_jobs_切换任务_进程树结构_fg
    ​ 查看进程回忆上次内容上次先进程查询ps-elf查看所有进程信息ps-lf查看本终端相关进程信息杀死进程kill-9PID给进程发送死亡信号运行多个py......
  • python程序的流程控制结构
    文章目录​​一.程序的顺序结构​​​​二.程序的分支结构​​​​1.单分支结构​​​​2.二分支结构​​​​(1).基本形式​​​​(2).紧凑形式​​​​3.多分支结......
  • Web前端——CSS结构
    文章目录​​一.CSS概述​​​​1.来源​​​​2.发展​​​​3.使用CSS的好处​​​​二.CSS定义​​​​1.CSS层叠样式表(CascadingStyleSheet)​​​​2.定义CSS......
  • 实验5 结构体应用编程
    #include<stdio.h>#include<string.h>#defineN3typedefstructstudent{intid;charname[20];charsubject[20......
  • 实验5 结构体应用编程
    实验三#include<stdio.h>#include<string.h>#defineN100typedefstruct{charnum[10];//学号ints1;//期末成绩ints2......
  • 循环结构--1~100的累加
    不管是在我们学习的哪一门语言中,都少不了控制结构的身影,计算机程序执行的流程也由他们三大结构组成。我今天就来说说“1+2+3+...100”的累加如何用不同的循环语句来表示!  ......
  • Microsoft Azure解决方案:如何通过 Microsoft 云服务来管理自己的打印基础结构
    51CTO博客地址:​ ​​​​https://blog.51cto.com/14669127​​​Azure培训视频地址:​ ​​​https://space.bilibili.com/2000820534​​配置通用打印是一种新式打印解......