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

柔光的暖阳◎ 2024-04-26 02:26 92阅读 0赞

> ? 本文由 [程序喵正在路上][Link 1] 原创，CSDN首发！  
> ? 系列专栏：[数据结构与算法][Link 2]  
> ? 首发时间：2022年11月8日  
> ? 欢迎关注?点赞?收藏?留言?  
> ? 一以贯之的努力 不得懈怠的人生

#### 阅读指南 ####

*  图的定义
 *  有向图
 *  无向图
 *  简单图、多重图
 *  顶点的度、入度、出度
 *  顶点-顶点的关系描述
 *  连通图、强连通图
 *  子图
 *  连通分量、强连通分量
 *  生成树
 *  生成森林
 *  边的权、带权图/网
 *  几种特殊形态的图

## 图的定义 ##

图  G G G 由顶点集  V V V 和边集  E E E 组成，记为  G = ( V , E ) G=(V, E) G=(V,E)，其中  V ( G ) V(G) V(G) 表示图  G G G 中顶点的有限非空集； E ( G ) E(G) E(G) 表示图  G G G 中顶点之间的关系（边）集合。若  V = \{ v 1 , v 2 , . . . , v n \} V=\\\{v\_1, v\_2, ... , v\_n\\\} V=\{ v1,v2,...,vn\}，则用  ∣ V ∣ |V| ∣V∣ 表示图  G G G 中顶点的个数，也称为图  G G G 的阶， E = \{ ( u , v ) ∣ u ∈ V , v ∈ V \} E = \\\{(u, v) | u \\in V, v \\in V\\\} E=\{(u,v)∣u∈V,v∈V\}， 用  ∣ E ∣ |E| ∣E∣ 表示图  G G G 中边的条数

注意：线性表可以是空表，树可以是空树，但图不可以是空图，即  V V V 一定是非空集，但  E E E 可以是空集

## 有向图 ##

若  E E E 是有向边（也称弧）的有限集合时，则图  G G G 为有向图。弧是顶点的无序对，记为  < v , w > <v, w> <v,w>，其中  v 、 w v、w v、w 是顶点， v v v 称为弧尾， w w w 称为弧头， v 、 w v、w v、w 称为从顶点  v v v 到顶点  w w w 的弧，也称为  v v v 邻接到  w w w，或  w w w 邻接自  v v v。 < v , w > ≠ < w , v > <v, w>\\ \\neq\\ <w, v> <v,w>=<w,v>

![在这里插入图片描述][7846b7e8619f459ba057dac2999509f4.png]  
上图可以表示为

G 1 = ( V 1 , E 1 ) G\_1 = (V\_1, E\_1) G1=(V1,E1)  
 V 1 = \{ A , B , C , D , E \} V\_1 = \\\{A, B, C, D, E\\\} V1=\{ A,B,C,D,E\}  
 E 1 = \{ < A , B > , < A , C > , < A , D > , < A , E > , < B , A > , < B , C > , < B , E > , < C , D > \} E\_1 = \\\{<A, B>, <A, C>, <A, D>, <A, E>, <B, A>, <B, C>, <B, E>, <C, D>\\\} E1=\{ <A,B>,<A,C>,<A,D>,<A,E>,<B,A>,<B,C>,<B,E>,<C,D>\}

## 无向图 ##

若  E E E 是无向边（简称边）的有限集合时，则图  G G G 为无向图。边是顶点的无序对，记为  ( v , w ) (v, w) (v,w) 或  ( w , v ) (w, v) (w,v)，因为  ( v , w ) = ( w , v ) (v, w) = (w, v) (v,w)=(w,v)，其中  v 、 w v、w v、w 是顶点。可以说顶点  w w w 和顶点  v v v 互为邻接点。边  ( v , w ) (v, w) (v,w) 依附于顶点  w w w 和  v v v，或者说边  ( v , w ) (v, w) (v,w) 和顶点  v 、 w v、w v、w 相关联

![在这里插入图片描述][8c0eda2241174f18aa101280fd1b0bcc.png]

上图可以表示为

G 2 = ( V 2 , E 2 ) G\_2 = (V\_2, E\_2) G2=(V2,E2)  
 V 2 = \{ A , B , C , D , E \} V\_2 = \\\{A, B, C, D, E\\\} V2=\{ A,B,C,D,E\}  
 E 2 = \{ ( A , B ) , ( B , D ) , ( B , E ) , ( C , D ) , ( C , E ) , ( D , E ) \} E\_2 = \\\{(A, B), (B, D), (B, E), (C, D), (C, E), (D, E)\\\} E2=\{(A,B),(B,D),(B,E),(C,D),(C,E),(D,E)\}

## 简单图、多重图 ##

简单图 —— 不存在重复边；不存在顶点到自身的边

多重图 —— 图  G G G 中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则  G G G 为多重图

简单图和多重图也有无向图和有向图之分

## 顶点的度、入度、出度 ##

对于无向图：顶点  v v v 的度是指依附于该顶点的边的条数，记为  T D ( v ) TD(v) TD(v)

在具有  n n n 个顶点、 e e e 条边的无向图中， ∑ i = 1 n T D ( v i ) = 2 e \\sum\_\{i=1\}^\{n\}TD(v\_i) = 2e ∑i=1nTD(vi)=2e，即无向图的全部顶点的度的和等于边数的  2 2 2 倍

对于有向图：

*  入度是以顶点  v v v 为终点的有向边的数目，记为  I D ( v ) ID(v) ID(v)
 *  出度是以顶点  v v v 为起点的有向边的数目，记为  O D ( v ) OD(v) OD(v)
 *  顶点  v v v 的度等于其入度和出度之和，即  T D ( v ) = I D ( v ) + O D ( v ) TD(v) = ID(v) + OD(v) TD(v)=ID(v)\+OD(v)

在具有  n n n 个顶点、 e e e 条边的有向图中， ∑ i = 1 n I D ( v i ) = ∑ i = 1 n O D ( v i ) = e \\sum\_\{i=1\}^\{n\}ID(v\_i) = \\sum\_\{i=1\}^\{n\}OD(v\_i) = e ∑i=1nID(vi)=∑i=1nOD(vi)=e

## 顶点-顶点的关系描述 ##

*  路径 —— 顶点  V p V\_p Vp 到顶点  V q V\_q Vq 之间的一条路径是指顶点序列  V p , V i 1 , V i 2 , … , V i m , V q V\_p, V\_\{i\_1\}, V\_\{i\_2\}, \\dots , V\_\{i\_m\}, V\_q Vp,Vi1,Vi2,…,Vim,Vq
 *  回路 —— 第一个顶点和最后一个顶点相同的路径称为回路或者环
 *  简单路径 —— 在路径序列中，顶点不重复出现的路径称为简单路径
 *  简单回路 —— 除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路
 *  路径长度 —— 路径上边的数目
 *  点到点的距离 —— 从顶点  u u u 出发到顶点  v v v 的最短路径若存在，则此路径的长度称之为从  u u u 到  v v v 的距离；若从  u u u 到  v v v 根本不存在路径，则记该距离为无穷（ ∞ \\infty ∞）
 *  无向图中，若从顶点  v v v 到顶点  w w w 有路径存在，则称  v v v 和  w w w 是连通的
 *  有向图中，若从顶点  v v v 到顶点  w w w和从顶点  w w w 到顶点  v v v 之间都有路径，则称这两个顶点是强连通的

## 连通图、强连通图 ##

若无向图  G G G 中任意两个顶点都是连通的，则称图  G G G 为连通图，否则称为非连通图

若有向图中任意一对顶点都是强连通的，则称此图为强连通图

对于  n n n 个顶点的无向图  G G G：

*  若  G G G 是连通图，则最少有  n − 1 n-1 n−1 条边
 *  若  G G G 是非连通图，则最多有  C n − 1 2 C\_\{n-1\}^\{2\} Cn−12 条边

对于  n n n 个顶点的有向图  G G G：

*  若  G G G 是强连通图，则最少有  n n n 条边（形成回路）

## 子图 ##

设有两个图  G = ( V , E ) G = (V, E) G=(V,E) 和  G ′ = ( V ′ , E ′ ) G' = (V', E') G′=(V′,E′)，若  V ′ V' V′ 是  V V V 的子集，且  E ′ E' E′ 是  E E E 的子集，则称  G ′ G' G′ 是  G G G 的子图

若有满足  V ( G ′ ) = V ( G ) V(G') = V(G) V(G′)=V(G) 的子图  G ′ G' G′，则称其为  G G G 的生成子图，也就是比如说一个子图中有原图的所有点，但少了一些边，那么可以说这个子图是原图的生成子图

## 连通分量、强连通分量 ##

无向图中的极大连通子图称为连通分量，其中，极大连通子图是指子图必须连通，且包含尽可能多的顶点和边

有向图中的极大强连通子图称为有向图的强连通分量，其中，极大强连通子图是指子图必须强连通，同时保留尽可能多的边

## 生成树 ##

连通图的生成树是包含图中全部顶点的一个极小连通子图（边尽可能少，但要保持连通）

若图中顶点数为  n n n，则它的生成树有  n − 1 n - 1 n−1 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路

## 生成森林 ##

在非连通图中，每个连通分量的生成树构成了非连通图的生成森林

## 边的权、带权图/网 ##

*  边的权 —— 在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值
 *  带权图/网 —— 边上带有权值的图称为带权图，也称为网
 *  带权路径长度 —— 当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

## 几种特殊形态的图 ##

*  无向完全图 —— 无向图中任意两个顶点之间都存在边
    
     *  若无向图的顶点数  ∣ V ∣ = n |V| = n ∣V∣=n，则  ∣ E ∣ ∈ \[ 0 , C n 2 \] = \[ 0 , n ( n − 1 ) 2 \] |E| \\in \[0, C\_n^2\] = \[0, \\frac\{n(n - 1)\}\{2\}\] ∣E∣∈\[0,Cn2\]=\[0,2n(n−1)\]
 *  有向完全图 —— 有向图中任意两个顶点之间都存在方向相反的两条弧
    
     *  若有向图的顶点数  ∣ V ∣ = n |V| = n ∣V∣=n，则  ∣ E ∣ ∈ \[ 0 , 2 C n 2 \] = \[ 0 , n ( n − 1 ) \] |E| \\in \[0, 2C\_n^2\] = \[0, n(n - 1)\] ∣E∣∈\[0,2Cn2\]=\[0,n(n−1)\]
 *  边数很少的图称为稀疏图，反之称为稠密图，边数没有绝对的界限，一般来说  ∣ E ∣ < ∣ V ∣ l o g ∣ V ∣ |E| < |V|log|V| ∣E∣<∣V∣log∣V∣ 时，可以将  G G G 视为稀疏图
 *  树 —— 不存在回路，且连通的无向图。对于  n n n 个顶点的树，必有  n − 1 n - 1 n−1 条边
 *   n n n 个顶点的图，若  ∣ E ∣ > n − 1 |E| > n - 1 ∣E∣>n−1，则一定有回路
 *  有向树 —— 一个顶点的入度为  0 0 0，其余顶点的入度均为  1 1 1 的有向图，称为有向树，有向树不一定是强连通图

[Link 1]: https://blog.csdn.net/weixin_62511863?spm=1011.2421.3001.5343
[Link 2]: https://blog.csdn.net/weixin_62511863/category_11984530.html?spm=1001.2014.3001.5482
[7846b7e8619f459ba057dac2999509f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/6eb91b42b3af4720a25cf80452a8c09b.png
[8c0eda2241174f18aa101280fd1b0bcc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/2fd5894e0f9d47e7bb64d6dcd81a47dc.png