【数据结构与算法之图结构】图的基本概念

末蓝、 2024-03-25 14:13 135阅读 0赞

#### 【数据结构与算法之图结构】图的基本概念 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之图结构】图的基本概念
         *   *   *  1 图的定义
                 *  2 图的常见术语

图是最复杂的数据结构，如果数据元素之间存在一对多、多对多的关系，这种数据的组织结构就叫做 图。

###### 1 图的定义 ######

图Gragh 由顶点( 图中的节点称为图的顶点) 的非空有限集合 V 与边的集合E (顶点之间的关系) 构成。

【无向图】图G中的每一条边都没有方向，则称G 为无向图。

![在这里插入图片描述][8aa21c0960654b3a87a6bbf269ce32e1.png_pic_center]

【有向图】若图G 的每一条边都有方向，则称G 为有向图。

![在这里插入图片描述][abb84a8db06b48458a5a1291530a62a9.png_pic_center]

###### 2 图的常见术语 ######

【顶点的度】

依附于某顶点v 的边数称为该顶点的度，记作TD(v) 。

有向图中还有出度和入度的概念：

*  入度：以顶点v为终点的弧的数目，记作ID(v)
 *  出度：以v为起始点的弧的数目，记作OD(v)

有向图中，TD(v) = ID(v) + OD(v)

【路径】

对于无向图G，若存在顶点序列( v 1 , v 2 , . . . v m v\_1,v\_2,...v\_m v1,v2,...vm) ，使得顶点对 ( v i , v i + 1 v\_i,v\_\{i+1\} vi,vi\+1) ∈ E( i = 1 , 2 , . . . , m − 1 i = 1,2,...,m-1 i=1,2,...,m−1) ，则称该顶点序列为顶点 v 1 v\_1 v1 到  v m v\_m vm 之间的一条路径。路径上所包含的边数 m - 1为该路径的长度。

【子图】

对于图G = (V,E) 与 图G’ = (V’ , E’)，若存在V’ ∈ V，E‘ ∈ E，则称图G’ 是 G的子图。

![在这里插入图片描述][7cbd811405194675bfc49ff1fb0a8811.png_pic_center]

【连通图】

若无向图的顶点 v i v\_i vi 到顶点 v j v\_j vj ( i ≠ j) 有路径，则称  v i 和 v j v\_i 和 v\_j vi和vj 之间是连通的，如果无向图中的任意两个顶点都是连通的，则该无向图为连通图，否则就是非连通。

无向图的最大连通子图称为该图的连通分量，连通图的连通分量只有一个，就是它本身。

从图的遍历角度看，从连通图中的任意顶点出发进行深搜或广搜，都可以访问到图中的所有顶点。

对于非连通图，则需要分别从不同的连通分量中的顶点触发进行搜索才能访问到图中的所有顶点。

`对于有向图`，若图中一对顶点  v i v\_i vi 和  v j ( i ≠ j ) v\_j(i ≠ j) vj(i=j) 均有从 v i v\_i vi 到 v j v\_j vj 以及从 v j v\_j vj 到 v i v\_i vi 的有向路径，则称 v i v\_i vi 和  v j v\_j vj 是连通的。

若有向图中任意两个顶点都是连通的，则该有向图是强连通的。有向图中的最大强连通子图称为该有向图的强连通分量，强连通的有向图只有一个强连通分量，即它本身。

非强连通的有向图可能存在多个强连通分量，也可能不存在强连通分量。

【生成树】

若图G 为包含n个顶点的连通图，则G中包含其全部n个顶点的极小连通子图称为G 的生成树。

`G的生成树一定包含且仅包含G的n - 1条边`

![在这里插入图片描述][5cd58736efae4678b49da7988705b7e1.png_pic_center]

如果连通图是一个网络(图的边上带权)，则其生成树中的边也带权，那么称该网络中所有带权生成树中权值最小的生成树为最小生成树，也叫最小代价生成树。

[8aa21c0960654b3a87a6bbf269ce32e1.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c09fc61cb6be408788d3da86bb9f98d1.png
[abb84a8db06b48458a5a1291530a62a9.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/f7956ca6d33a496c84b578474d750abc.png
[7cbd811405194675bfc49ff1fb0a8811.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/88970abf63d84a648ed51b51087e80bb.png
[5cd58736efae4678b49da7988705b7e1.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c143f3a7d8334bb7b27554c0855e67b5.png