数据结构与算法---5（图）

「爱情、让人受尽委屈。」 2022-02-26 06:28 366阅读 0赞

# 图 #

在线性表中，数据元素之间是被串起来的，仅有线性关系，每个数据元素都只有一个直接前驱和直接后继；在树形结构中，数据元素之间有着明显的层次结构，但是每一个元素肯定值只有一个直接前驱的，这些都是一对一或者一对多的关系；但是图却是一种多对多的关系

**图的定义：图是由顶点的有穷非空集合和顶点之间边的集合组成；正常表示为G(V, E)，其中G表示一个图，V表示图G中顶点的集合，E是图G中边的集合**

对于图，我们有几个值的注意的地方：

*  线性表中我们把数据元素叫做元素，树中将数据元素叫做结点，在图中我们把数据元素叫做顶点
 *  图在定义的时候我们就要求顶点集合是有穷非空的
 *  图中，任意两个顶点之间可能有关系，顶点之间的逻辑关系用边来表示，边集是可以是空的

## 各种图定义 ##

无向边：若顶点![\_V\{\_\{i\}\}][V_i]到![\_V\{\_\{j\}\}][V_j]之间的边没有方向，则称这条边为无向边，用无序偶对（![\_V\{\_\{i\}\}][V_i]，![\_V\{\_\{j\}\}][V_j]）来表示；如果图中任意两个顶点之间的边都是无向边，则称该图为无向图；（![\_V\{\_\{i\}\}][V_i]，![\_V\{\_\{j\}\}][V_j]）也可以写成（![\_V\{\_\{j\}\}][V_j]，![\_V\{\_\{i\}\}][V_i]）

有向边：若从顶点![\_V\{\_\{i\}\}][V_i]到![\_V\{\_\{j\}\}][V_j]的边有方向，则称这条边为有向边，也称为弧，用有序偶<![\_V\{\_\{i\}\}][V_i],![\_V\{\_\{j\}\}][V_j]>来表示，![\_V\{\_\{i\}\}][V_i]称为弧尾，![\_V\{\_\{j\}\}][V_j]称为弧头；如果图中任意两个顶点之前的边都是有向边，则称该图为有向图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70][]

在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图，我们课程中讨论的都是简单图，下面的图就不属于我们讨论的范围

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 1][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 2][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 3][]

（这个图少了两根线）

有很少条边或者弧的图称为稀疏阵，繁殖称之为稠密图，这里稀疏和稠密是模糊的概念；有些图的边有相关的数字，这种与图的边或弧相关的数叫做权，这些权可以表示从一个顶点到另一个顶点的距离和耗费，这种带权的图通常称为网，下面就是一张网：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 5][]

## 图的顶点与边间关系 ##

对于无向图G=(V, \{E\}， 如果边（V, V'）属于E，则称顶点V和V'互为邻接点，即V和V'相邻接；边（V, V'）依附于顶点V和V'。或者说（V, V'）与顶点V和V'相关联；顶点的度是和V相关联的边的数目，记为TD(V)；

对于有向图G=(V, \{E\}，如果边<V, V'>属于E，则称顶点V邻接到顶点V'，顶点V'邻接自顶点V；弧<V, V'>和顶点V, V'相关联，以顶点V为头的弧的数目称为V的入度，记为ID(V)；以V为尾的的弧的数目称为V的出度，记为OD(V)；顶点V的度为TD(V) = ID(V) + OD(V)

一个顶点和另一个顶点之间路径可能有多种，路径的长度是路径上的边或弧的数目；第一个顶点和最后一个顶点相同的路径称为环或者回路，序列中顶点不重复出现的路径称为简单路径，除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路或者简单环

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 6][]

上图中第一个是简单回路，第二个不是简单回路

### 连通图的相关术语 ###

在无向图G中，如果从顶点V到顶点V'有路径，则称V和V'是连通的；如果对于图中任意两个顶点V、V'都是连通的，则称G为连通图

无向图中的极大连通子图称为连通分量；注意连通分量的概念：

*  要是子图
 *  子图是要连通的
 *  连通子图含有极大顶点数
 *  具有极大顶点数的连通子图包含依附于这些顶点的所有边

在有向图G中，如果对于每一对顶点V,V'，从V到V'和从V'到V都存在路径，则称G为强连接图；有向图的极大强连通子图称为有向图的强连通分量

下面我们再来看看连通图的生成树的概念：

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 7][]

如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一颗有向树，对于有向树的理解比较容易，所谓入度为0其实就是相当于树的根节点，其余结点入度为1就相当于树的非根结点的双亲只有一个；一个有向图的生成森林由若干颗有向树组成，含有图中所有的顶点，但只有足以构成若干颗不相交的有向树的弧

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 8][]

图一是一个有向树，去掉一些弧后他可以分解为两颗有向树，这两颗树就是图一有向图的生成森林

## 图的定义和术语总结 ##

*  图按照有无方向可以分为无向图和有向图，无向图由顶点和边构成，有向图由顶点和弧组成，弧有弧头和弧尾之分
 *  图按照边或弧的多少分为稀疏图或者稠密图；如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图；若无重复的边或顶点到自身的图叫简单图
 *  图中顶点之间有邻接点、依附的概念；无向图顶点的边数叫做度，有向图顶点分为入度和出度
 *  图上的边或弧带权则被称为网
 *  图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复的叫做简单路径；若任意两顶点都是相通的，则图就是连通图，有向则称为强连通图；图中有子图，且子图极大连通则就是连通分量，有向的则称为强连通分量
 *  无向图中连通且N个顶点N-1条边叫生成树，有向图中一顶点入度为0其余顶点入度为1的叫有向树，一个有向图由若干颗有向树构成生成森林

## 图的存储结构 ##

由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在内存中的物理位置来表示元素之间的关系，也就是说图不可能用简单的顺序存储结构来表示；而多重链表的方式，即以一个数据域和多个指针组成的结点表示图中的一个顶点，尽管可以实现图结构，但是其实在树中我们已经讨论过了，这是有问题的，如果各个顶点度数相差很大，按度数最大的顶点设计结点结构会造成很多存储单元的浪费，而若按照每个顶点自己的度数设计不同的顶点结构，又带来操作上的不便

### 邻接矩阵 ###

图的邻接矩阵存储方式是用两个数组来表示图；一个一维数组存储图中顶点的信息，一个二维数组（称为邻接矩阵）存储图中的边或者弧的信息

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 9][]

可以看到邻接矩阵是一各对称阵

### 邻接表 ###

邻接矩阵是一种不错的存储结构，但是我们发现，对于边数相对顶点较少的图，这种结构是存在对存储空间的极大浪费，比如我们要处理下面的这个图结构：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 10][]

因此我们考虑另外一种存储结构，将数组和链表结合起来，就是邻接表

邻接表的办法是这样的：

*  图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易的读取顶点的信息，更加方便，另外对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的信息
 *  图中每个顶点的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点的边表，有向图则称为顶点作为弧尾的出边表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 11][]

## 图的遍历 ##

### 深度优先遍历（DFS） ###

从图中某个顶点出发，访问此顶点，然后从该顶点的未被访问的邻接点出发深度优先遍历图，直至图中所有和该顶点有路径相通的顶点被访问到；这里讲到的是连通图，对于非连通图，只需对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先搜索遍历后，若有结点还没有被访问，则另选图中的一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止

### 广度优先遍历（BFS） ###

广度优先遍历又称为广度优先搜索，广度优先搜索就相当于树的层序遍历

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 12][]

[V_i]: https://private.codecogs.com/gif.latex?_V%7B_%7Bi%7D%7D
[V_j]: https://private.codecogs.com/gif.latex?_V%7B_%7Bj%7D%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70]: /images/20220226/7524ebbc4b534ff7b1503859278c24f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 1]: /images/20220226/add4f794f8244fc0b2a38d8202ca51a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 2]: /images/20220226/23441cc06cb84c32a1731c516cc017c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 3]: /images/20220226/3ff41720672843a980ae1fe9e3915917.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 4]: /images/20220226/3d52d0fc7b784675bbd0a7551bb017d5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 5]: /images/20220226/91246ce860b640a3b5a1c7657e4b0bdd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 6]: /images/20220226/ee0f968245a5467ea6809eb7a7c5b667.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 7]: /images/20220226/faed0a7ac775437c9177b1059679e158.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 8]: /images/20220226/fe61a04fefe84d5e94c6799b0234ddbb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 9]: /images/20220226/ab2d4efa6b7b41ba9c284d686995d0c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 10]: /images/20220226/3a68cad71cf4424487a3e84fa334dde7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 11]: /images/20220226/0fa0a80a6bbf4e059f9977808a5d60a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkzMTU0MA_size_16_color_FFFFFF_t_70 12]: /images/20220226/18a2d06ebe5045959b7184f31f51140b.png