当前位置:   article > 正文

408数据结构-图的基本概念 自学知识点整理

408数据结构-图的基本概念 自学知识点整理

*第六章个人感觉是最难的,请各位抓稳扶手,系好安全带。


图的定义

通俗来讲,一个图由一些点和连接这些点的若干边组成,边的两头必须都有顶点,否则不是图。
注:G: GraphV: VertexE: Edge
对图 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=\left\{ {{v}_{1}},{{v}_{2}},\cdots ,{{v}_{n}} \right\} V={v1,v2,,vn},则用 ∣ V ∣ \left| V \right| V表示图 G G G中顶点的个数, E = { ( u , v ) ∣ u ∈ V , v ∈ V } E=\left\{ \left( u,v \right)\left| u\in V,v\in V \right. \right\} E={(u,v)uV,vV},用 ∣ E ∣ \left| E \right| E表示图 G G G中边的条数。

注意:线性表可以是空表,树也可以是空树,但是图不可以是空图。这意味着,图中不能一个顶点也没有,图的顶点集 V V V一定非空,但边集 E E E可以为空,此时图中只有顶点而没有边。

图的基本概念及术语

有向图、无向图

E E E有向边(也称)的有限集合,则称图 G G G为有向图。
弧是顶点的有序对,记为 ⟨ v , w ⟩ \left\langle v,w \right\rangle v,w,其中 v , w v,w v,w是顶点, v v v称为弧尾 w w w称为弧头 ⟨ v , w ⟩ \left\langle v,w \right\rangle v,w称为从 v v v w w w的弧,也称 v v v邻接到 w w w。( ⟨ v , w ⟩ ≠ ⟨ w , v ⟩ \left\langle v,w \right\rangle \ne \left\langle w,v \right\rangle v,w=w,v

如图6.1(a)中,有向图 G 1 G_1 G1可表示为:
G 1 = ( V 1 , E 1 ) {{G}_{1}}=\left( {{V}_{1}},{{E}_{1}} \right) G1=(V1,E1)
V 1 = { 1 , 2 , 3 } {{V}_{1}}=\left\{ 1,2,3 \right\} V1={1,2,3}
E 1 = { ⟨ 1 , 2 ⟩ , ⟨ 2 , 1 ⟩ , ⟨ 2 , 3 ⟩ } {{E}_{1}}=\left\{ \left\langle 1,2 \right\rangle ,\left\langle 2,1 \right\rangle ,\left\langle 2,3 \right\rangle \right\} E1={1,2,2,1,2,3}

E E E无向边(也称)的有限集合,则称图 G G G无向图
边是顶点的无序对,记为 ( v , w ) \left( v,w \right) (v,w) ( w , v ) \left( w,v \right) (w,v)。可以说 w w w v v v互为邻接点。边 ( v , w ) \left( v,w \right) (v,w)依附于 w w w v v v,或称边 ( v , w ) \left( v,w \right) (v,w) v , w v,w v,w相关联。( ( v , w ) = ( w , v ) \left( v,w \right) = \left( w,v \right) (v,w)=(w,v)

如图6.1(b)中,无向图 G 2 G_2 G2可表示为:
G 2 = ( V 2 , E 2 ) {{G}_{2}}=\left( {{V}_{2}},{{E}_{2}} \right) G2=(V2,E2)
V 2 = { 1 , 2 , 3 , 4 } {{V}_{2}}=\left\{ 1,2,3,4 \right\} V2={1,2,3,4}
E 2 = { ( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) } {{E}_{2}}=\left\{ \left( 1,2 \right),\left( 1,3 \right),\left( 1,4 \right),\left( 2,3 \right),\left( 2,4 \right),\left( 3,4 \right) \right\} E2={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

无向与有向可以类比标量与向量进行理解。比如从 v v v w w w有一条弧 ⟨ v , w ⟩ \left\langle v,w \right\rangle v,w,就可以认为有一条有向线段从 v v v指向 w w w
(图片来自王道考研408数据结构2025)
图片来自王道考研408数据结构2025

简单图、多重图

对一个图 G G G,若其满足:①不存在重复边;②不存在顶点到自身的边。则称图 G G G简单图。上图6.1中的图 G 1 G_1 G1和图 G 2 G_2 G2均为简单图。
若图 G G G中某两个顶点之间的边数大于 1 1 1条,又或者允许顶点通过一条边与自身关联,则称图 G G G多重图
多重图和简单图的定义是相对的。(408初试数据结构考察简单图!!!)
之后讨论的所有图只有简单图,多重图只需了解其概念即可。

顶点的度、入度和出度

对于无向图,顶点 v v v的度是指依附于顶点 v v v的边的条数,记为 T D ( v ) TD(v) TD(v)无向图的全部顶点的度之和等于边数的 2 2 2,因为每条边和两个顶点相关联。
n n n个顶点、 e e e条边的无向图中, ∑ i = 1 n T D ( v i ) = 2 ∣ E ∣ \sum\limits_{i=1}^{n}{TD\left( {{v}_{i}} \right)}=2\left| E \right| i=1nTD(vi)=2E
在图6.1(b)中,每个顶点的度均为 3 3 3

对于有向图,顶点 v v v的度分为入度和出度,入度是以顶点 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\limits_{i=1}^{n}{ID\left( {{v}_{i}} \right)}=\sum\limits_{i=1}^{n}{OD\left( {{v}_{i}} \right)}=e i=1nID(vi)=i=1nOD(vi)=e
在图6.1(a)中,顶点 2 2 2的出度为 2 2 2、入度为 1 1 1

顶点-顶点的关系描述

  • 路径:顶点 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}}}},\cdots ,{{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根本不存在路径,则记该距离为无穷( ∞ ∞ )。

连通、连通图

无向图中,若从顶点 v v v到顶点 w w w有路径存在,则称 v v v w w w连通的。若图 G G G中任意两个顶点都是连通的,则称图 G G G连通图,否则为非连通图
对于 n n n个顶点的无向图 G G G:若 G G G是连通图,则最少有 n − 1 n-1 n1条边;若 G G G是非连通图,则最多可能有 C n − 1 2 C_{n-1}^{2} Cn12条边。

有向图中,若有一对顶点 v v v w w w,从 v v v w w w w w w v v v之间都有有路径存在,则称 v v v w w w这两个顶点是强连通的。若图中任意一对顶点都是强连通的,则称此图为强连通图
对于 n n n个顶点的有向图 G G G:若 G G G是强连通图,则最少有 n n n条边(形成回路)。

注意:在无向图中讨论连通性,在有向图中讨论强连通性

子图

设有两个图 G ( V , E ) G\left( V,E \right) G(V,E) G ′ ( V ′ , E ′ ) {{G}^{'}}\left( {{V}^{'}},{{E}^{'}} \right) 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\left( {{G}^{'}} \right)=V\left( G \right) V(G)=V(G)的子图 G ′ {{G}^{'}} G,则称其为 G G G生成子图

连通分量

无向图中的极大连通子图称为连通分量
其中,“极大连通子图”的含义是:子图必须连通,在此基础上,包含尽可能多的顶点和边
(图片来自王道考研408数据结构2025)
图片来自王道考研408数据结构2025
有向图中的极大强连通子图称为强连通分量
其中,“极大强连通子图”的含义是:子图必须强连通,在此基础上,保留尽可能多的
(图片来自王道考研408数据结构2025)
图片来自王道考研408数据结构2025

生成树、生成森林

连通图的生成树包含图中全部顶点的一个极小连通子图
极小连通子图的含义是:子图要保持连通,在此基础上,包含尽可能少的边。
若一个连通图有 n n n个顶点,则它的生成树含有 n − 1 n-1 n1条边。构造生成树的方式并不唯一。对生成树而言,若砍去它的一条边,则会变成非连通图;若加上一条边,则会形成一个回路(环)。

在非连通图中,连通分量的生成树构成了非连通图的生成森林
也就是说,对非连通图,其所有的极大连通子图的生成树的集合,构成这个非连通图的生成森林。
(知识点回顾:树与森林

注意:区分极大连通子图和极小连通子图。极大连通子图要求子图必须连通,而且包含尽可能多的顶点和边;极小连通子图是既要保持子图连通又要使得边数最少的子图。

边的权、带权图/网

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

几种特殊形态的图

  • 无向完全图:对一个无向图,若其任意两个顶点之间都存在边,则称这样的无向图为无向完全图。容易得到,对一个顶点数为 n n n的无向完全图,其边的数量为 C n 2 C_{n}^{2} Cn2
  • 有向完全图:对一个有向图,若其任意两个顶点之间都存在方向相反的两条弧,则称这样的有向图为有向完全图。若一个有向完全图有 n n n个顶点,则其边数为 2 C n 2 2C_{n}^{2} 2Cn2 n ( n − 1 ) n(n-1) n(n1)
  • 稀疏图稠密图:边数很少的图称为稀疏图,反之称为稠密图。稀疏和稠密本身是模糊的概念,没有绝对的界限,稀疏图和稠密图常常是相对而言的。一般来说,当图 G G G满足 ∣ E ∣ < ∣ V ∣ log ⁡ ∣ V ∣ \left| E \right|<\left| V \right|\log \left| V \right| E<VlogV时,可以将 G G G视为稀疏图。当然这个定义也不绝对,作了解即可。
  • 不存在回路,且连通无向图 n n n个顶点的树,必有 n − 1 n-1 n1条边。森林中各个子图是极小且连通的。
    n n n个顶点的图中有大于 n − 1 n-1 n1条的边,则其中一定有回路。
  • 有向树:一个顶点的入度为 0 0 0、其余顶点的入度均为 1 1 1有向图,称为有向树。这个入度为 0 0 0的顶点可以视为树中的根结点。需要注意的是,树是连通图,但有向树并不是强连通图。

这些基本概念需要结合课后习题熟记于心,不然后续内容会难以理解。
虽然都是些八股文,但还是得努努力背下来,要理解到位才行。下一篇博客应该会开始上代码。
以上。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/608841
推荐阅读
相关标签
  

闽ICP备14008679号