数据结构之图的基本介绍

向右看齐 2023-02-21 04:48 169阅读 0赞

# 图的基本介绍 #

线性表局限于一个直接前驱和一个直接后继的关系，树也只能有一个直接前驱也就是父节点。当我们需要表示多对多的关系时，就需要用到图。

## 图的基本概念 ##

图（Graph）是一种数据结构，由顶点（vertex）和边（edge）组成，通常表示为G=(V,E):

*  G：表示一个图
 *  V：表示图中顶点的集合，顶点集V有穷且非空
 *  E: 表示图中边的集合，边集E可以是空的

边：两个顶点之间的连接。

路径：一个顶点到另一个顶点的通路。

比如下面的无向图中，从顶点D到顶点C的路径有：

1.  D->B->C
2.  D->B->A->C

![无向图][20200628154242559.png]  
无向图（Undirected Graph）：顶点之间的路径没有方向，比如A-B，即可以是A->B也可以B->A，上面的图就是一个无向图。

有向图（Directed Graph）：顶点之间的路径有方向，比如A-B，只能是A->B，不能是B->A，下面的图就是一个有向图。

![有向图][20200628154302645.png]  
出度（Out-degree）：一个顶点的出度为x，是指有x条边以该顶点为起点，例如上面的有向图中，顶点A的出度是2。

入度（In-degree）：一个顶点的入度为x，是指有x条边以该顶点为终点，例如上面的有向图中，顶点C的入度是2。

> 出度、入度适用于有向图。

带权图（Weighted Graph）：边带权值的图也叫网。

![带权图][20200628154323819.png]

## 图的表示方式 ##

图的表示方式有两种：

*  邻接矩阵（Adjacency Matrix）
 *  邻接表（Adjacency List）

### 邻接矩阵 ###

邻接矩阵是表示图形中顶点之间相邻关系的矩阵，通常采用一个存放顶点信息的一位数组和一个存放边信息的二维数组实现。

使用邻接矩阵实现的无向图如下：

![邻接矩阵实现无向图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]  
说明：

*  邻接矩阵中的1代表两个顶点之间直连，0代表两个顶点之间不直连。
 *  顶点V1与顶点V0和顶点V2直连，所以邻接矩阵的第二行第一列和第三列为1。

使用邻接矩阵实现的有向图如下：

![邻接矩阵实现有向图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]

邻接矩阵比较适合稠密图，不然会比较浪费内存。

### 邻接表 ###

邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在，会造成空间的一定损失。

邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成。

使用邻接表实现的无向图如下：

![邻接表实现的无向图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 2]  
说明：

*  顶点V1与顶点V0和顶点V2直连，所以顶点V1对应的链表为V0->V3。

使用邻接表实现的有向图如下：

![邻接表实现有向图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 3]  
更多精彩内容关注本人公众号：架构师升级之路  
![在这里插入图片描述][20200627175030665.jpg]

[20200628154242559.png]: https://img-blog.csdnimg.cn/20200628154242559.png
[20200628154302645.png]: https://img-blog.csdnimg.cn/20200628154302645.png
[20200628154323819.png]: https://img-blog.csdnimg.cn/20200628154323819.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200628154350715.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200628154426790.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/202006281549467.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020062815452679.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[20200627175030665.jpg]: https://img-blog.csdnimg.cn/20200627175030665.jpg