算法快学笔记（十）：截图“图”的面纱

素颜马尾好姑娘i 2022-03-20 09:44 205阅读 0赞

# 1. 介绍 #

数据结构领域，图（Graph）是一种复杂的非线性结构，在图结构中，每个元素都可以有零个或多个前驱，也可以有零个或多个后继，也就是说，元素之间的关系是任意的。

本文对图的基础支持做一个简单的总结。

# 2. 定义 #

## 2.1 图的定义 ##

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

## 2.2 图的分类 ##

### 2.2.1 有向/无向/完全 ###

按照方向分为无向图和有向图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70]  
上图中，左图为无向图是由顶点和边构成，右图为有向图是由顶点和弧（有向边构成）。弧有弧头和弧尾区别。

在用数学方式表示时，无向边用()表示，有向边用<>表示。现在我们讲解的图全是简单图。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 1]  
如果任意两个顶点之间都存在边叫完全图，有向的边叫有向完全图。如果无重复的边或者顶点到自身的边叫简单图。上图左侧为简单图

## 2.3 网 ##

有些图的边或弧具有与它相关的数字，这种带权的图通常称为网，下面就是一个带权的图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 2]

### 2.4 度 ###

*  无向图：顶点的边数是度
 *  有向图：
    
     *  入度：方向指向顶点的边；
     *  出度：方向背向顶点的边。
     *  顶点的度=出度+入度。

## 2.5 路径长度 ##

路径的长度是路径上边或是弧的数目。对于相同的两个顶点，不同的路径可能会有不同的路径长度。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 3]  
上图中,左侧路径的长度为2,右侧路径的长度为3

### 2.6 连通 ###

*  无向图：任意两个顶点是相通的就是连通图。下图中，左侧为非连通的，右侧为连通的  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 4]
 *  有向图：任意两个顶点是相通的就是强连通图，下面左侧的图中，不存在D->A不是连通的，所以不是强连通图，而右侧的则为强连通图。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 5]

# 3. 图的存储 #

图的结构比价复杂，任意两个顶点之间都可能存在关系，不能用简单的顺序存储结构来表示。如果运用多重链表，即一个数据域多个指针域组成的结点表示图中一个结点，则造成大量存储单元浪费。

## 3.1 邻接矩阵 ##

邻接矩阵用两个数组保存数据。一个一维数组存储图中顶点信息，一个二维数组存储图中边或弧的信息，结构如下。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 6]

邻接矩阵表示带权图的方法如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 7]  
带权图值的说明如下：

1.  0：在主对角线上表示指向自己，否则表示权值
2.  无穷大：表示两个顶点不通
3.  权值

特点：

1.  0表示无边，1表示有边
2.  顶点的度是行内数组之和。
3.  求取顶点邻接点，将行内元素遍历下。
4.  无向图：无向图中二维数组是个对称矩阵
5.  有向图：各行之和是出度，各列之和是入度。

**缺点：邻接矩阵对于边数相对顶点较少的图，就是对存储空间极大的浪费。**

## 3.2 邻接表 ##

邻接表：数组和链表相结合的存储方法为邻接表。  
存储结构如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 8]

*  图中顶点用一个一维数组存储。
 *  图中每个顶点的所有邻接点构成一个线性表。

从图中得知，顶点表的各个结点由data和Firstedge两个域表示，data是数据域，存储顶点信息，firstedge是指针域，指向边表的第一个结点，即顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中坐标，next存储边表中下一个结点指针。比如v1顶点与v2、v0互为邻接点，则在v1边表中，adjvex分别为0和2。

有向图也可以用邻接表，出度表叫邻接表，入度表尾逆邻接表。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 9]

## 3.3 十字链表 ##

在邻接表中针对有向图，分为邻接表和逆邻接表，导致无法从一个表中获取图的入读和出度的情况，于是诞生了十字链表,相关结构如下：

1.  顶点结构

<table> 
 <thead> 
  <tr> 
   <th>data</th> 
   <th>firstin</th> 
   <th>firstout</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

*  firstin：入边表头指针，指向顶点入边表的第一个结点。
 *  firstout：出边表头指针，指向顶点出边表第一个结点。

1.  边结构

<table> 
 <thead> 
  <tr> 
   <th>tailvex</th> 
   <th>headvex</th> 
   <th>headlink</th> 
   <th>taillink</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

*  tailvex是指弧起点在顶点表的下标
 *  headvex弧终点在顶点表的下标
 *  headlink入边表指针域，指向终点相同的下一条边
 *  taillink是指边表指针域，指向起点相同的下一条边。

示例如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 10]

十字链表把邻接表和逆邻接表整合在了一起，便于统计顶点的出度和入度，且算法的时间复杂度和邻接表相同。

## 3.4 邻接多重表 ##

如果使用邻接存储无向图，操作顶点很方便，但是对于边的操作比较麻烦（例如删除边），使用邻接多重表可以解决该问题，邻接多重表的边结构的定义如下：

<table> 
 <thead> 
  <tr> 
   <th>ivex</th> 
   <th>ilikn</th> 
   <th>jvex</th> 
   <th>jlink</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

ivex和jvex是与某条边依附的两个顶点在顶点表中的下标。ilink指向依附项点ivex的下一条边，jlink指向依附顶点jvex的下一条边。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 11]

## 3.5 边集数组 ##

边集数组由两个一位数组构成，一个用来存储顶点信息，一个用来存储边信息。边集数组关注的重点是对边的操作，比较适合一次对边进行处理的操作，如果想要获取某个顶点的度可能就不大适合。

边的结构表示为：

<table> 
 <thead> 
  <tr> 
   <th>begin</th> 
   <th>end</th> 
   <th>weight</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

例子如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 12]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70]: /images/20220320/bc78e09fee824d4da601e20142c2887f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 1]: /images/20220320/72c0d71912ff4ee19ceae35e964d6ac4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 2]: /images/20220320/dc3f2ee4f7b444adab9d9e6600026d62.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 3]: /images/20220320/84b7a231cc514ee9b05182b68e7e8d7a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 4]: /images/20220320/d0e57a4282b240a992bad189224c79e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 5]: /images/20220320/9ba09b7f4534442a950251418e7b1d86.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 6]: /images/20220320/2876fbac644a424a8487b6a0f33cc085.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 7]: /images/20220320/af576dd558b146408768789ca81ede4f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 8]: /images/20220320/3296e691ff6f4bf9aeb86653c91272ba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 9]: /images/20220320/1750b3a339654eabb4f1a81547b0deb6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 10]: /images/20220320/fc2038dadac8410cac526808cfeda244.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 11]: /images/20220320/9de583a979844a51821ebfad05f07f70.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1bjc1NDU1MjY_size_16_color_FFFFFF_t_70 12]: /images/20220320/512360f84d9047e1864a9c30118ef4c4.png