数据结构学习-【图】

Dear 丶 2023-06-19 04:19 144阅读 0赞

## 一、图的定 ##

在说图的定义之前 先要说明一下:

**线性表中我们把数据元素叫做元素，树中数据元素叫做结点，在图中数据元素，我们称之为顶点。**

下面说一下图的定义：

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70][]

注意：图中的 顶点集合不允许为空，但是边集合允许为空。

各种图的定义：

### 1.无向图 ###

**两个顶点之前的边没有方向，称为无向边，改图中所有的边都是由无向边组成的图，叫做无向图。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70 1][]

该图的表示法：

G1(V1,\{E1\})

顶点集合：V1=\{A,B,C,D\}; 边集合：E1\{(A,B),(B,C),(C,D),(D,A),(A,C)\}

### 2.有向图 ###

**改图所有的边都是由有向边构成**

**有向边又叫弧，例如下图顶点B到A的边就有方向，则称这条边有方向，也称为弧，B是弧头，A称弧尾，写成<A,B>**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70 2][]

改图的表示为：G2=(V2,\{E2\})

顶点集合：V2=\{A,B,C,D\}

弧集合：E2=\{<A,D>,<B,A>,<C,A>,<B,C>\}

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

共有n(n-1)/2条边

![20191204150547249.png][]

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

共有n(n-1)条边

![20191204150740134.png][]

**有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权。这些带权的图通常叫做网。**

![20191204151511522.png][]

## 二、图的存储结构 ##

### 1.图的邻接矩阵 ###

是用两个数组来表示，一个一维数组来存储图的顶点信息，一个二维数组存储图中的边或弧的信息。

第一个是无向图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70 3][]

第二个是有向图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70 4][]

第三个是带有权值的有向图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70 5][]

### 邻接表 ###

**定义：数组与链表相结合的存储方法叫做邻接表。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70 6][]

**无向图的邻接表**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70 7][]

**有向图的逆邻接表**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70 8][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191204143652385.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191204144324925.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191204144525110.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx,size_16,color_FFFFFF,t_70
[20191204150547249.png]: https://img-blog.csdnimg.cn/20191204150547249.png
[20191204150740134.png]: https://img-blog.csdnimg.cn/20191204150740134.png
[20191204151511522.png]: https://img-blog.csdnimg.cn/20191204151511522.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191205092010696.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191205094341976.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191205094447810.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20191205101026123.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20191205101059139.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20191205103718951.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzA2MDQx,size_16,color_FFFFFF,t_70