数据结构——非线性结构（图）

一. 非线性结构的概述

二. 图的基本概念

1. 定义

2. 无向图、有向图

2.1 无向图

2.2 有向图

2.3 简单图

2.4 多重图

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

3.1 对于无向图

3.2 对于有向图

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

5. 点到点的关系

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

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

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

---

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

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

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 邻接矩阵法的性质

性质1：

性质2：

2. 邻接表法

2.1 来源

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

2.2 定义（采用顺序存储和链式存储结合）

2.3 邻接表法的性质

性质1：

性质2：

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

tip

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

3. 十字链表（只能存储有向图）

3.1 来源

3.2 定义

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

3.3 十字链表法性能分析

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

4. 邻接多重表（只能存储无向图）

4.1 来源

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

4.2 定义

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

4.3 邻接多重表性能分析

5. 四种存储结构的比较

四. 图的基本操作

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

五. 图的遍历

1）什么是图的遍历？

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

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

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

3）为什么需要图的遍历

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

4）图遍历的关键是什么？

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

1. 广度优先搜索（BFS遍历）

1.1 概述

1）树的广度优先搜索

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

2）图的广度优先搜索（Breadth-First-Search）

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

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

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

4）广度优先遍历序列

tip

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

1.2 复杂度分析

1）空间复杂度

2）时间复杂度

1.3 广度优先生成树

扩展：广度优先生成森林

2. 深度优先搜索（DFS遍历）

2.1 概述

1）树的深度优先遍历

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

2）图的深度优先遍历（Depth-First-Search）

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

3）深度优先遍历序列


tip

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

2.2 复杂度分析

1）空间复杂度

2）时间复杂度

2.3 深度优先生成树

扩展：深度优先生成森林

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

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

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

3.1 对于无向图

3.2 对于有向图

六. 图的应用

1. 最小生成（代价）树

1.1 概述

1) 来源

2) 定义

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

3) 性质

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

都是基于贪心算法策略

1) Prim算法

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

算法思想：

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

算法演示：

算法总结：

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

---

2) Kruskal算法

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

算法思想：

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

算法演示：

3) 两个算法的比较

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

2. 最短路径

2.1 定义

2.2 分类

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

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

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

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

算法思想：

• 基于贪心策略
  

算法时间复杂度：

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

Prim算法和Dijkstra算法区别：

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

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

参考文献：
https://blog.csdn.net/dutmathjc/article/details/105888831
https://zhuanlan.zhihu.com/p/87748517

算法不足：

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

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

算法思想：

算法演示：

算法时间复杂度：

算法的缺点：

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

2.3 三种算法的比较

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

3.1 概述

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

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

3.2 DAG描述表达式

3.3 解题方法

4. 拓扑排序

4.1 AOV网

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

特点：

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

4.2 拓扑排序概述

定义：

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

作用：

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

目的：

• 找到做事的先后顺序

4.3 拓扑排序常用方法

4.4 拓扑排序复杂度

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

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

4.5 逆拓扑排序

特点：

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

5. 关键路径

5.1 AOE网

定义：

性质：

AOV网和AOE网的异同：

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

5.2 关键路径概述

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

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

ve(k) = e(i)

l(i) = vl(k)-weight

5.3 求关键路径的步骤

---

5.4 关键路径的特性

---

参考文献：王道数据结构