当前位置 博文首页 > Change_Improve的博客：数据结构——图-基本知识点（第七章）

最大化 缩小

    Change_Improve的博客：数据结构——图-基本知识点（第七章）

    作者：[db:作者] 时间：2021-09-20 13:48

    ?目录

    1. 图的定义

    1.1 各种图定义

    1.2 图的顶点与边间关系

    1.3 连通图相关术语

    1.4 图的定义与术语总结

    2. 图的抽象数据类型

    3. 图的存储结构

    3.1 邻接矩阵

    3.2 邻接表

    3.3 十字链表

    3.4 邻接多重表

    3.5 边集数组

    4. 图的遍历

    4.1 深度优先遍历

    4.2 广度优先遍历

    5. 最小生成树

    5.1 普里姆（ Prim ）算法

    5.2 克鲁斯卡（ Kruskal ）算法

    6. 最短路径

    6.1 迪杰斯特拉（ Dijkstra ）算法

    6.2 弗洛伊德（ Floyd ）算法

    7. 拓扑排序

    7.1 拓扑排序介绍

    7.2 拓扑排序算法

    8. 关键路径

    8.1 关键路径算法原理

    8.2 关键路径算法

    9. 总结回顾

    ?????? 图：图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。

    1. 图的定义

    在线性表中，数据元素之间是被串起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素都可能和下一层中多个元素相关，但只能和上一层中一个元素相关。简而言之，线性表是一对一的关系，树形结构是一对多关系，而图是多对多的关系。

    图是一种较线性表和树更加复杂的数据结构。在图形结构中。结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

    ?????? 图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V,E），其中，G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。

    ?????? 对于图的定义，需要明确注意的几点地方：

    ?????? ■?? 线性表中把数据元素叫元素，树中将数据元素叫结点，在图中数据元素，则称之为顶点（Vertex）（也可以称为Node）。

    ?????? ■?? 线性表中可以没有数据元素，称为空表。树中可以没有结点，叫做空树。而图结构中，不允许没有顶点。在定义中，若V是顶点的集合，则强调了顶点集合V有穷非空（此处有争议，国内部分教材强调点集非空，在http://enwikipedia.org/wiki/Null_graph提出点集可为空）。

    ?????? ■?? 线性表中，相邻的数据元素之间具有线性关系，在树结构中相邻两层的结点具有层次关系，而图中，任意两点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

    1.1 各种图定义

    ?????? 无向边：若顶点vi到vj之间的边没有方向，则称这条边为无向边（ Edge ），用无序偶对 \begin{pmatrix} v_{i},v_{j} \end{pmatrix} 来表示。

    ?????? 无向图：如果图中任意两个顶点之间的边都是无向边，则称该图为无向图（Undirected graphs）。

    ?????? 下图就是一个无向图，由于是无方向的，连接顶点 A 与 D 的边，可以表示成无序对（A , D），也可以写成（D , A）。

    ?????? 对于下图的中的无向图 G_{1}= \begin{pmatrix} V_{1},\begin{Bmatrix} E_{1} \end{Bmatrix}\end{pmatrix} ，其中顶点集合 V_{1}=\begin{Bmatrix} A,B,C,D \end{Bmatrix} ；边集合 E_{1}=\begin{Bmatrix} \bigl(\begin{smallmatrix} A,B \end{smallmatrix}\bigr) ,\bigl(\begin{smallmatrix} B,C \end{smallmatrix}\bigr) ,\bigl(\begin{smallmatrix} C,D \end{smallmatrix}\bigr) ,\bigl(\begin{smallmatrix} D,A \end{smallmatrix}\bigr) ,\bigl(\begin{smallmatrix} A,C \end{smallmatrix}\bigr) \end{Bmatrix}

    ?????? 有向边：若从顶点 v_{i} 到 v_{j} 的边有方向，则称这条边为有向边，也称为弧（Arc）。用有序偶 <v_{i},v_{j}> 来表示，v_{i} 称为弧尾（Tail），v_{j} 称为弧头（Head）。

    ?????? 有向图：如果图中任意两个顶点之间的边都是有向边，则称该图为有向图（Directed graphs）。

    ?????? 下图就是一个有向图，连接顶点 A 到 D 的有向边就是弧，A 是弧尾，D 是弧头，<A, D>表示弧，注意不能写成 <D , A>。

    ?????? 对于下图的有向图 G2 来说， G_{2}=\bigl(\begin{smallmatrix} V_{2},\begin{Bmatrix} E_{2} \end{Bmatrix} \end{smallmatrix}\bigr) ，其中顶点集合 V_{2}=\begin{Bmatrix} A,B,C,D \end{Bmatrix} ；弧集合 E_{2}=\begin{Bmatrix} <A,D>,<B,A>,<C,A>,<B,C> \end{Bmatrix} 。

    ?????? 注意：无向边用小括号“（）”表示，而有向边则是用尖括号“<>”表示。

    ?????? 在图中，若不存在顶点到其自身的边，而同一条边不重复出现，则称这样的图为简单图。现阶段所学的和讨论的都是简单图，下图所示的两个图就不属于我们要讨论的范围。

    无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。

    含有 n 个顶点的无向完全图有 \frac{n*\bigl(\begin{smallmatrix} n-1 \end{smallmatrix}\bigr)}{2} 条边。比如下图所示就是无向完全图，因为每个顶点都要与除它以外的顶点连接，顶点 A 与 BCD 三个顶点连线，共有四个顶点，自然是 4*3 ，但由于顶点 A 与顶点 B 连线后，计算 B 与 A 连线就是重复，因此整体除以 2 ，共有 6 条边。

    ?????? 有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。

    ?????? 含有 n 个顶点的有向完全图有 n*\bigl(\begin{smallmatrix} n-1 \end{smallmatrix}\bigr) 条边，如下图所示。

    ?????? 结论：对于具有 n 个顶点和 e 条边数的图，无向图 0\leqslant e \leqslant \frac{n*\bigl(\begin{smallmatrix} n-1 \end{smallmatrix}\bigr)}{2}，有向图 0\leqslant e\leqslant n*\bigl(\begin{smallmatrix} n-1 \end{smallmatrix}\bigr) 。

    ?????? 有很少条边或弧的图称为稀疏图，反之称为稠密图。这里稀疏图和稠密图是模糊的概念，都是相对而言的。

    ?????? 权：有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权（Weight）。这些权可以表示一个顶点到另一个顶点的距离或耗费。

    ?????? 网：带权的图通常称为网（Network）。下图所示就是一张带权的图，即标识中国四大城市的直线距离的网，此图中的权就是两地的距离。

    ?????? 子图：假设有两个图 G= \begin{pmatrix}V,\begin{Bmatrix} E \end{Bmatrix}\end{pmatrix}和 G{}'= \begin{pmatrix}V{}',\begin{Bmatrix} E{}' \end{Bmatrix}\end{pmatrix} ，如果 V′?V 且 E′?E ，则称 G′ 为 G 的子图（Subgraph）。例如下图所示带底纹的图均为左侧无向图与有向图的子图。

    1.2 图的顶点与边间关系

    1. 无向图

    ?????? 邻接点：对于无向图 G= \begin{pmatrix}V,\begin{Bmatrix} E \end{Bmatrix}\end{pmatrix}，如果（v,v′）∈ E ，则称顶点 v 和 v′ 互为邻接点（Adjacent），即 v 和 v′ 相邻接。

    ?????? 边（v , v′）依附（incident）于顶点 v 和 v′ ，或者说（v , v′）与顶点 v 和 v′ 相关联。

    ?????? 度：顶点 v 的度（Degree）是和 v 相关联的边的数目，记为 TD（v）。

    ?????? 例如下图所示，顶点 A 与 B 互为邻接点，边（A , B）依附于顶点 A 与 B 上，顶点 A 的度为 3 。而此时图的边数是 5 ，各个顶点度的和 = 3+2+3+2 = 10 ，推敲后发现，边数其实就是各顶点度数和的一半，多出来的一半是因为重复两次记数。简记为： e=\frac{1}{2} \sum_{i=1}^{n} TD\bigl(\begin{smallmatrix} v_{i} \end{smallmatrix}\bigr) 。

    2. 有向图

    ?????? 对于有向图 G= \begin{pmatrix}V,\begin{Bmatrix} E \end{Bmatrix}\end{pmatrix}，如果 <v,v′>∈E ，则称顶点 v 邻接到顶点 v′ ，顶点 v′ 邻接自顶点 v 。弧 <v，v′> 和顶点 v，v′ 相关联。

    ?????? 入度：以顶点 v 为头的弧的数目称为 v 的入度（InDegree），记为 ID（v）。

    ?????? 出度：以 v 为尾的弧的数目称为 v 的出度（OutDegree），记为 OD（v）。

    ?????? 度：顶点 v 的度为 TD（v）= ID（v）+OD（v） 。

    ?????? 例如下图所示，顶点 A 的入度是 2（从 B 到 A 的弧，从 C 到 A 的弧），出度是 1（从 A 到 D 的弧），所以顶点 A 的度为2+1=3 。此有向图的弧有 4 条，而各顶点的出度和 = 1+2+1+0 = 4 ，各顶点的入度和 = 2+0+1+1 = 4 。所以得到： e=\sum_{i=1}^{n} ID\bigl(\begin{smallmatrix} v_{i} \end{smallmatrix}\bigr) = \sum_{i=1}^{n} OD\bigl(\begin{smallmatrix} v_{i} \end{smallmatrix}\bigr)?

    ?????? 无向图 G= \begin{pmatrix}V,\begin{Bmatrix} E \end{Bmatrix}\end{pmatrix}中从顶点 v 到顶点 v′ 的路径（Path）是一个顶点序列 \bigl(\begin{smallmatrix} v=v_{i,0},v_{i,1},.. ,v_{i,m}=v{}' \end{smallmatrix}\bigr) ，其中 \bigl(\begin{smallmatrix} v_{i,j-1},v_{i,j} \end{smallmatrix}\bigr) \in E,1\leqslant j\leqslant m 。例如下图所示就列举了顶点 B 到顶点 D 四种不同的路径。

    ?????? 如果 G 是有向图，则路径也是有向的，顶点序列应满足<v_{i,j-1},v_{i,j} > \in E,1\leqslant j\leqslant m。例如下图所示，顶点 B 到顶点 D 有两种路径。而顶点 A 到 B ，就不存在路径。

    ?????? 树中根节点到任意结点的路径是唯一的，但是图中顶点与顶点之间的路径却是不唯一的。

    ?????? 路径的长度是路径上的边或弧的数目。例如上图左侧路径长为 2 ，右侧路径长度为 3 。

    ?????? 回路或环：第一个顶点到最后一个顶点相同的路径称为回路或环（Cycle）。

    ?????? 简单回路：序列中顶点不重复出现的路径称为简单回路。

    ?????? 简单回路或简单环：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

    ?????? 下图所示中的两个图的粗线都构成环，左侧的环因第一个顶点和最后一个顶点都是 B ，且 C、D、A 没有重复出现，因此是一个简单环。而右侧的环由于顶点 C 的重复，它就不是简单环了。

    1.3 连通图相关术语

    ?????? 连通图：在无向图 G 中，如果从顶点 v 到顶点 v′ 有路径，则称 v 和 v′ 是连通的。如果对于图中任意两个顶点 v_{i} 、v_{j}\in E，v_{i} 和 v_{j} 都是连通的，则称 G 是连通图（Connected Graph）。

    ?????? 下图所示的图1，它的顶点 A 到顶点 B、C、D 都是连通的，但显然顶点 A 与顶点 E 或 F 就无路径，因此不能算是连通图。下图的图2，顶点 A、B、C、D 相互都是连通的，所以它本身就是连通图。

    ?????? 连通分量：无向图中的极大连通子图称为连通分量。

    ?????? 注意连通分量的概念，它强调：

    ?????? ■?? 要是子图；

    ?????? ■?? 子图要是连通的；

    ?????? ■?? 连通子图含有极大项点数；

    ?????? ■?? 具有极大项点数的连通子图包含依附于这些顶点的所有边。

    ?????? 下图图1 是一个无向非连通图。但是它有两个连通分量，即图2 和图3 。而图4 ，尽管是图1 的子图，但是它却不满足连通子图的极大顶点数（图2 满足）。因此它不是图1 的无向图的连通分量。

    ?????? 强连通图：在有向图 G 中，如果对于每一对 v_{i} 、v_{j}\in V 、v_{i}\neq v_{j} ，从 v_{i} 到 v_{j} 和从 v_{j} 到 v_{i} 都存在路径，则称 G 是强连通图。

    ?????? 强连通分量：有向图中的极大连通子图称做有向图的强连通分量。

    ?????? 例如下图所示，图1 并不是强连通图，因为顶点 A 到顶点 D 存在路径，而D到A就不存在路径。图2 就是强连通图，而且显然图2 是图1 的极大强连通子图，即是它的强连通分量。

    ?????? 连通图的生成树定义：

    ?????? 一个连通图的生成树是一个极小的连通子图，它含有图中全部的 n 个顶点，但只有足以构成一棵树的 n-1 条边。

    ?????? 比如下图所示的图1 是一普通图，但显然它不是生成树，当去掉两条构成环的边后，比如图2 或图3 ，就满足 n 个顶点 n-1 条边且连通的定义了。它们都是一棵生成树。从这里也可知道，如果一个图有 n 个顶点和小于 n-1 条边，则是非连通图，如果它多于 n-1 条边，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。比如图2 和图3 ，随便加哪两顶点的边都构成环不过有 n-1 条边并不一定是生成树，比如图4 。

    ?????? 有向树：如果一个有向图恰有一个顶点的入度为 0 ，其余顶点的入度均为 1 ，则是一棵有向树。

    ?????? 有向树的理解比较容易，所谓入度为 0 其实就相当于树中的根节点，其余顶点入度为 1 就是说树的非根结点的双亲只有一个。

    ?????? 森林：一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但有足以构成若干棵不相交的有向树的弧。

    ?????? 如下图所示的图1 是一个有向图。去掉一些弧后，它可以分解为两棵有向树，如图2 和图3 ，这两棵就是图1 有向图的生成森林。

    1.4 图的定义与术语总结

    ?????? 图按照有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧尾和弧头之分。

    ?????? 图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。

    ?????? 图中顶点之间有邻接点、依附的概念。无向图顶点的边叫做度，有向图顶点分为入度和出度。

    ?????? 图的边上或弧上带权则称为网

    ?????? 图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则则称为环，当中不重复叫做简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称强连通分量。

    ?????? 无向图中连通且 n 个顶点 n-1 条边叫生成树。有向图中一顶点入度为 0 其余顶点入度为 1 的叫有向树。一个有向图由若干棵有向树构成生成森林。

    2. 图的抽象数据类型

    ?????? 图作为一种数据结构，它的抽象数据类型带有自己特点，正因为它的复杂，运用广泛，使得不同的应用需要不同的运算集合，构成不同的抽象数据操作。下图所示为图的基本操作：

    



    

    上一篇：xy_learning的博客：数组和链表的优雅去重——时间复杂度O(n)且 
    

    下一篇：没有了