浅谈数据结构之图（一）

待我称王封你为后i 2023-06-16 04:52 12阅读 0赞

### 浅谈数据结构之图（一） ###

*   *  基本概念
     *  图的存储结构
     *  图的遍历

## 基本概念 ##

**1. 图的定义**  
图(graph)是由一些点(vertex)和这些点之间的连线(edge)所组成的；其中，点通常被成为"顶点(vertex)"，而点与点之间的连线则被成为"边或弧"(edege)。通常记为，G=(V,E)。  
**2. 图的种类**  
根据边是否有方向，将图可以划分为：**无向图**和**有向图**。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 1]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 2]  
**3. 邻接点和度**  
**3.1 邻接点**  
一条边上的两个顶点叫做邻接点。  
例如，上面无向图G0中的顶点A和顶点C就是邻接点。  
在有向图中，除了邻接点之外；还有"入边"和"出边"的概念。 顶点的入边，是指以该顶点为终点的边。而顶点的出边，则是指以该顶点为起点的边。  
例如，上面有向图G2中的B和E是邻接点；<B,E>是B的出边，还是E的入边。  
**3.2 度**  
在无向图中，某个顶点的度是邻接到该顶点的边(或弧)的数目。  
例如，上面无向图G0中顶点A的度是2。  
在有向图中，度还有"入度"和"出度"之分。 某个顶点的入度，是指以该顶点为终点的边的数目。而顶点的出度，则是指以该顶点为起点的边的数目。 顶点的度=入度+出度。  
例如，上面有向图G2中，顶点B的入度是2，出度是3；顶点B的度=2+3=5。

## 图的存储结构 ##

**1. 邻接矩阵**  
邻接矩阵是指用矩阵来表示图。它是采用矩阵来描述图中顶点之间的关系(及弧或边的权)。 假设图中顶点数为n，则邻接矩阵定义为：  
![在这里插入图片描述][20191124153001381.png]  
通常采用两个数组来实现邻接矩阵：一个一维数组用来保存顶点信息，一个二维数组来用保存边的信息。 邻接矩阵的缺点就是比较耗费空间。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 4]  
**2. 邻接表**  
邻接表是图的一种链式存储表示方法。它是改进后的"邻接矩阵"，它的缺点是不方便判断两个顶点之间是否有边，但是相对邻接矩阵来说更省空间。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 6]

## 图的遍历 ##

**深度优先遍历**  
图的深度优先搜索(Depth First Search)，和树的前序遍历比较类似。  
它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。  
显然，深度优先搜索是一个递归的过程。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 7]  
**广度优先遍历**  
广度优先搜索算法(Breadth First Search)，又称为”宽度优先搜索”或”横向优先搜索”，简称BFS。  
它的思想是：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。  
换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2…的顶点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 8]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191124152229875.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191124152241221.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191124152246132.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70
[20191124153001381.png]: https://img-blog.csdnimg.cn/20191124153001381.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191124153104411.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191124153109563.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191124153206837.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20191124153215300.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20191124153526197.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20191124153729865.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2N1aXhoYW8xMTA=,size_16,color_FFFFFF,t_70