【数据结构】图的基础概念介绍

Bertha 。 2022-10-22 11:53 480阅读 0赞

### 图的基础概念 ###

*  数据结构回顾
 *  图（Graph）
 *   *  有向图（Directed Graph）
     *   *  出度、入度
     *  无向图（Undirected Graph）
     *  混合图（Mixed Graph）
     *  简单图、多重图
     *  无向完全图（Undirected Complete Graph）
     *  有向完全图（Directed Complete Graph）
     *  有权图（Weighted Graph）
     *  连通图（Connected Graph）
     *  连通分量（Connected Component）
     *  强连通图（Strongly Connected Graph）
     *  强连通分量（Strongly Connected Component）
 *  图的实现方案
 *   *  邻接矩阵（Adjacency Matrix）
     *   *  邻接矩阵 – 有权图
     *  邻接表（Adjacency List）
     *   *  邻接表 – 有权图

# 数据结构回顾 #

线性结构：数组、链表、栈、队列、哈希表(底层数组)

树形结构：二叉树、B树、堆、Trie、哈夫曼树、并查集

图形结构：图属于单独一类的数据结构  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]

# 图（Graph） #

图由顶点（vertex）和边（edge）组成，通常表示为 G = (V, E)

*  G 表示一个图，V 是顶点集，E 是边集
 *  顶点集 V 有穷且非空
 *  `任意两个顶点之间`都可以用边来表示它们之间的关系，边集 E 可以为空

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]  
图结构的应用非常广泛：

*  社交网络
 *  地图导航
 *  游戏开发
 *  。。。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]

## 有向图（Directed Graph） ##

有向图的边是有明确方向的：  
![在这里插入图片描述][2021031714103960.png]  
有向无环图（Directed Acyclic Graph，简称 DAG）

*  如果一个有向图，从任意顶点出发无法经过若干条边回到该顶点，那么它就是一个有向无环图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]

### 出度、入度 ###

出度、入度适用于有向图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 4]  
出度（Out-degree）

*  一个顶点的出度为 x，是指有 x 条边以该顶点为起点
 *  例如：顶点 11 的出度是 3 （有 3 条边，从顶点11 指出）

入度（In-degree）

*  一个顶点的入度为 x，是指有 x 条边以该顶点为终点
 *  例如：顶点 11 的入度是 2（有 2 条边，指入顶点 11 ）

## 无向图（Undirected Graph） ##

无向图的边是无方向的  
![在这里插入图片描述][20210317142634610.png]  
无向图可以通过有向图表示出来，但是有向图无法通过无向图来表示。

下面这个有向图就相当于上面的无向图。  
![在这里插入图片描述][20210317142718856.png]

## 混合图（Mixed Graph） ##

混合图的边可能是无向的，也可能是有向的  
![在这里插入图片描述][20210317142930770.png]

## 简单图、多重图 ##

平行边

*  在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边
 *  在有向图中，关联一对顶点的有向边如果多于1条，并且它们的的方向相同，则称这些边为平行边

多重图（Multigraph）

*  有平行边 或者 有自环的图  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 5]

简单图（Simple Graph）

*  既没有平行边也不没有自环的图  
    ![在这里插入图片描述][20210317143708876.png]

## 无向完全图（Undirected Complete Graph） ##

无向完全图的任意两个顶点之间都存在边

*  n 个顶点的无向完全图有 n(n − 1) / 2 条边
 *  (n − 1) + (n − 2) + (n − 3) + ⋯ + 3 + 2 + 1  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 6]

## 有向完全图（Directed Complete Graph） ##

有向完全图的任意两个顶点之间都存在方向相反的两条边

*  n 个顶点的有向完全图有 n(n − 1) 条边  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 7]

稠密图（Dense Graph）：边数接近于或等于完全图

稀疏图（Sparse Graph）：边数远远少于完全图

## 有权图（Weighted Graph） ##

有权图的边可以拥有权值（Weight）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 8]

## 连通图（Connected Graph） ##

如果顶点 x 和 y 之间存在可相互抵达的路径（`直接`或`间接`的路径） ，则称 x 和 y 是连通的

如果无向图 G 中任意 2 个顶点都是连通的，则称 G 为连通图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 9]

## 连通分量（Connected Component） ##

连通分量：无向图的极大连通子图

*  连通图只有一个连通分量，即其自身
 *  非连通的无向图有多个连通分量

下面的无向图有 3 个连通分量：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 10]

## 强连通图（Strongly Connected Graph） ##

如果有向图 G 中任意2个顶点都是连通的，则称G为强连通图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 11]

## 强连通分量（Strongly Connected Component） ##

强连通分量：有向图的极大强连通子图

*  强连通图只有一个强连通分量，即其自身
 *  非强连通的有向图有多个强连通分量  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 12]

# 图的实现方案 #

图有 2种 常见的实现方案：

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

## 邻接矩阵（Adjacency Matrix） ##

邻接矩阵的存储方式，两个数组（一个一维数组 和 一个二维数组）

*  一维数组存放顶点信息
 *  二维数组存放边信息

邻接矩阵比较适合稠密图

*  不然会比较浪费内存

邻接矩阵表示`无向图`：在二维数组中，对角实际是对称的，会浪费一半的空间

*  例如：`V0`到`V2`连通，那么`V2`到`V0`也连通，不存在方向  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 13]  
    邻接矩阵表示`有向图`：在二维数组中，不存在对称一说，但也会浪费一些空间
 *  例如：自身到自身，`V0`到`V0`，`V2`到`V2`，属于无意义边  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 14]

### 邻接矩阵 – 有权图 ###

有权图：若顶点之间不存在边，就用无穷大表示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 15]

## 邻接表（Adjacency List） ##

采用数组+链表（纵向使用数组，横向采用链表，有种哈希表的感觉）

邻接表 表示无向图：`V0`直连谁，`V0`就指向谁

*  例如：`V0`直连`V1`、`V2`、`V3`，所以`V0`指向`V1`、`V2`、`V3`（无前后顺序）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 16]

逆邻接表就是反过来：谁直连V0，V0就指向谁  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 17]

### 邻接表 – 有权图 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 18]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]: /images/20221022/e49ad42ee92d4789a02c1152cf7442ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]: /images/20221022/7bfc6e0c33f644fc876f8173256b99a9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 2]: /images/20221022/a1f51ecc539b483e98826ecc7ca69a45.png
[2021031714103960.png]: /images/20221022/9f3a0246bfc04bc0b734590008d19eb6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 3]: /images/20221022/e26bed5969414e3c8cce9771fe2ea5d6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 4]: /images/20221022/c1202cdf3fae4ab09f56bd054efed408.png
[20210317142634610.png]: /images/20221022/d817a712d2b441f7ad27bea3661b98aa.png
[20210317142718856.png]: /images/20221022/cd5d1cec038e46e5a488fd1878696785.png
[20210317142930770.png]: /images/20221022/53893cde751146acb218e470b1ee58aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 5]: /images/20221022/305a8531aa3743e1b3288898736f4f2e.png
[20210317143708876.png]: /images/20221022/e7906cfb9607404ba0a481ec1160df08.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 6]: /images/20221022/b6b1033abc774a6d9b7f3d27ce8c9324.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 7]: /images/20221022/5d1e858203274b50a3bd0fe9b7357926.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 8]: /images/20221022/5731a6c562904048a7f51b13cac4bd56.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 9]: /images/20221022/4c76b3b006f0436fb8ae32afd10f9caa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 10]: /images/20221022/f5f84cfa41da4258a63f30452f64b189.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 11]: /images/20221022/2f65d126eb754b018125f3dea4e43495.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 12]: /images/20221022/9b69c636b6684975b27ab991c4fe9d01.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 13]: /images/20221022/aaa0705e42904c3aa2fb58b2d92791c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 14]: /images/20221022/84c4238a61484a3790269f3b38db9fc2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 15]: /images/20221022/5d573fab7be3486694cec83ac8a45291.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 16]: /images/20221022/43bcf0f4f7474e24a3a491bd0150c9e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 17]: /images/20221022/a55f947f0f71461a91dfd14ac82cf3c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 18]: /images/20221022/334128d9f2a54e4bac733c02dac2aded.png