马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
导读
各人好，很高兴又和各人见面啦！！！
在上一篇中，我们体系梳理了图论底子概念——极点度、路径盘算、结点间隔、子图分别与连通性判断，为明白复杂图布局打下根基。
本篇将聚焦图论焦点骨架：树与丛林。通过对比无向图与有向图中的天生树规则，团结可视化案例分析极小连通子图的计划逻辑，带您把握权值网络、完全图等延伸概念的数学本质。
无论您是算法角逐选手照旧网络分析研究者，此文都将成为您突破图布局认知瓶颈的关键指南。
一、图中的树与丛林
1.1 天生树与天生丛林
在无向图中存在两个特有的概念：
- 天生树：天生树指的是在连通图中包罗全部极点的一个极小连通子图。
- 天生丛林：天生丛林指的是在非连通图中，全部连通分量的天生树的聚集。
1.1.1 天生树
天生树是连通图中的概念，它具有以下特点：
- 树中的极点数目 = 图中的极点数目
- 树中边的数目 = 树中的极点数目 - 1
- 树中无环
这里我们以下面这个连通图 G G G 为例：
在图 G G G 中，当我们去掉边集 E ′ = { ( a , b ) , ( b , c ) , ( a , c ) } E' = \{(a, b), (b, c), (a, c)\} E′={(a,b),(b,c),(a,c)} 中的此中恣意一条边，此时的子图 G ′ G' G′ 还可以或许继承保持连通性，这里我们以去掉边 ( a , b ) (a, b) (a,b) 为例：
该子图 G ′ G' G′ 就是 G G G 的一棵天生树。对于天生树而言，边的数目既不能增长，也不能镌汰：
- 当我们再去掉恣意一条边时，该连通图就酿成了一个非连通图；
- 当我们再加上一条边时，该连通图中就会出现环；
1.1.2 天生丛林
天生丛林好坏连通图中的概念，它是由非连通图的全部连通分量的天生树构成，这里我们以下图 G G G 为例：
在这个非连通图中，它有两个联通分量：
- 连通分量 G 1 = ( V 1 , E 1 ) G_1 = (V_1, E_1) G1=(V1,E1) ：
- V 1 = { a , b , c , d } V_1 = \{a, b, c, d\} V1={a,b,c,d}
- E 1 = { ( a , b ) , ( b , c ) , ( c , d ) , ( d , a ) } E_1 = \{(a, b), (b, c), (c, d), (d, a)\} E1={(a,b),(b,c),(c,d),(d,a)}
- 连通分量 G 2 = ( V 2 , E 2 ) G_2 = (V_2, E_2) G2=(V2,E2) ：
- V 2 = { e } V_2 = \{e\} V2={e}
- E 2 = { ∅ } E_2 = \{\varnothing\} E2={∅}
其对应的天生丛林为：
1.1.3 天生树、天生丛林与连通分量
结点的关系
在无向图中，根据是否存在非连通的结点，我们可以将无向图分为两类：
- 连通图：无向图中全部的极点都相互连通
- 非连通图：无向图中存在非连通的极点
不管是连通图还好坏连通图，它们都存在各自的连通分量：
- 连通图：连通图的连通分量只有一个，就是它自己
- 非连通图：非连通图的连通分量的数目与互不相交的最大连通子图数目雷同
在连通图中，其子图可以或许以最少的边确保全部结点的连通性时，该子图就是连通图的最小连通子图，也称为天生树；
在非连通图中，每个连通分量的最小连通子图就构成了天生丛林；
如今我们不难发现，最小连通子图，即天生树只存在于连通图中，而天生丛林只存在于非连通图中。因此我们可以得到一个结论：
- 天生树的结点数目 = 连通图的极点数目 = 连通图的连通分量的极点数目
- 天生丛林的结点数目 = 非连通图的极点数目 = 非连通图的全部连通分量的极点数目
在非连通图中，单棵天生树的极点数目与该树对应的连通分量的极点数目相当，但是不便是该非连通图的极点数目。这个肯定要服膺！！！
这个点比力绕，我们照旧以图为例，更加直观的来明白；
这里有一个图 G = ( V , E ) G = (V, E) G=(V,E) ，此中：
- 极点集 V = { a , b , c , d , e , f , g , h } V = \{a, b, c, d, e, f, g, h\} V={a,b,c,d,e,f,g,h}
- 边集 E = { ( a , b ) , ( a , c ) , ( a , d ) , ( b , c ) , ( c , d ) , ( e , f ) , ( f , g ) , ( g , e ) } E = \{(a, b), (a, c), (a, d), (b, c), (c, d), (e, f), (f, g), (g, e) \} E={(a,b),(a,c),(a,d),(b,c),(c,d),(e,f),(f,g),(g,e)}
图中存在3个连通分量：
- 连通分量 G 1 = ( V 1 , E 1 ) G_1 = (V_1, E_1) G1=(V1,E1) ：
- V 1 = { a , b , c , d } V_1 = \{a, b, c, d\} V1={a,b,c,d}
- E 1 = { ( a , b ) , ( a , c ) , ( a , d ) , ( b , c ) , ( c , d ) } E_1 = \{(a, b), (a, c), (a, d), (b, c), (c, d)\} E1={(a,b),(a,c),(a,d),(b,c),(c,d)}
该连通分量对应天生树为：
固然，该连通分量的天生树有许多课，这里我们只选取了此中一棵；
- 连通分量 G 2 = ( V 2 , E 2 ) G_2 = (V_2, E_2) G2=(V2,E2) ：
- V 2 = { e , f , g } V_2 = \{e, f, g\} V2={e,f,g}
- E 2 = { ( e , f ) , ( f , g ) , ( g , e ) } E_2 = \{(e, f), (f, g), (g, e)\} E2={(e,f),(f,g),(g,e)}
该连通分量对应天生树为：
固然，该连通分量的天生树有许多课，这里我们只选取了此中一棵；
- 连通分量 G 3 = ( V 3 , E 3 ) G_3 = (V_3, E_3) G3=(V3,E3) ：
- V 3 = { h } V_3 = \{h\} V3={h}
- E 3 = { ∅ } E_3 = \{\varnothing\} E3={∅}
该连通分量对应的天生树有且仅有一棵：
可以看到该非连通图中，每个连通分量所对应的天生树的结点数目都与该连通分量的极点数目雷同；
由这三棵树构成的天生丛林为：
该天生丛林的结点数目与该非连通图的极点数目雷同。
因此我们就可以得到非连通图的天生树、天生丛林、连通分量与图的极点数目之间的关系：
- 单棵天生树的结点数目 = 其连通分量的极点数目 < 非连通图的极点数目
- 天生丛林的结点数目 = 非连通图的极点数目 > 任一连通分量的极点数目
由于在图中不存在空图的环境，对于非连通图来说，其极点数目肯定大于任一连通分量的极点数目。
边的关系
天生树中边的数目是须要满意图连通性的最少数目，即，当极点为 n n n 时，对应边的数目为 n − 1 n -1 n−1
天生丛林中，每棵子树的边都满意天生树的条件，即，原图有 n n n 个极点，有 m m m 棵天生树时，那么对应的边的数目则为 n − m n - m n−m；
在连通分量中，每个连通分量的边的数目都是当前图中保持连通的最大边的数目，即，当非连通图中有 n n n 条边，那么该图所对应的全部连通分量的边的数目之和为 n n n;
认识了无向图中的树与丛林，接下来我们就来看一下有向图所对应的树与丛林；
1.2 有向图中的树与丛林
1.2.1 有向树与有向丛林
在有向图中，也存在两个特有的概念：
- 有向树：有向树指的是一个极点的入度为0，别的极点的入度均为1的有向图。
- 有向丛林：有向丛林指的是由多个互不相交的有向树构成的聚集。
须要注意的是这里的有向图不是特指的强连通图，而是任一有向图，而且在图中只要存在满意有向树的子图，就可以是一棵有向树，如下所示：
在这个有向图中，就存在多棵有向树，如：
固然，该图对应的有向树远不止这些，我们只是例举了这三棵树。此中只要是互不相交的有向树就能构成一个有向丛林，而这例举的三棵树都不想交，因此它们就可以构成一个有向丛林：
但是我们须要重点关注的是有向图中的天生有向树与天生有向丛林：
1.2.2 生产有向树与天生有向丛林
天生有向树：天生有向树指的是有向图中的全部极点，存在一个极点的入度为0、别的极点的入度均为1且无环的子图；
天生有向丛林：天生有向丛林指的是有向图中互不相交的且包罗原图全部极点的天生有向树构成的聚集；
在天生有向树中，有几个特点：
- 包罗该有向图中的全部极点
- 从根结点出发，可以到达原图中的任一结点
- 从根结点出发，到任一结点有且仅有一条路径
- 无环
在天生有向丛林中，有几个特点：
- 全部的子树的极点之和 = 原图中的极点数目
- 每棵子树都是一棵天生有向树
- 每棵子树都不与别的任一子树相交
下面我们照旧通过图示来明白：
照旧这个有向图，它存在两个不相交的有向子图：
- 有向子图 G 1 = ( V 1 , E 1 ) G_1 = (V_1, E_1) G1=(V1,E1)
- V 1 = { a , b , c , d } V_1 = \{a, b, c, d\} V1={a,b,c,d}
- E 1 = { < a , b > , < b , a > , < b , c > , < c , d > , < d , a > } E_1 = \{<a, b>, <b, a>, <b, c>, <c, d>, <d, a>\} E1={<a,b>,<b,a>,<b,c>,<c,d>,<d,a>}
其对应的天生子树为：
- 有向子图 G 2 = ( V 2 , E 2 ) G_2 = (V_2, E_2) G2=(V2,E2)
- V 2 = { e } V_2 = \{e\} V2={e}
- E 2 = { ∅ } E_2 = \{\varnothing\} E2={∅}
其对应的天生子树为：
该有向图 G G G 对应的天生有向丛林为：
在这个丛林中有两棵子树，而且这两棵子树都是对应子图的天生有向树；
1.2.3 有向树与天生有向树的区别
在有向图中，有向树与天生有向树是有许多雷同的点：
- 无环：两种有向树都满意无环的条件
- 连通：从根结点出发，都能通过有向边到达树中的别的任一结点
- 路径唯一：从根结点出发，到任一结点的路径存在且唯一
- 入度束缚：根结点的入度为0，除根结点外，别的结点的入度均为1
但是这二者也有一些差别之处：
- 极点数目差别
- 有向树中，并没有对极点数目举行束缚，即，只要是有向图中的子图且满意有向树的特性，就可以得到一棵有向树；
- 天生有向树中，对极点数目举行了束缚，必须包罗原图中的全部极点
- 连通性差别
- 有向树不要求原图中全部极点都必须连通，即，原图中的单个极点即可构成一棵有向树；
- 天生有向树则要求原图中必须存在一个根结点可以或许通过有向边访问到其他全部的结点；
根据有向树与天生有向树之间的差异，二者所构成的丛林也同样存在差异：
1.2.4 有向丛林与天生有向丛林的区别
雷同点
- 构成布局雷同
- 有向丛林：由多棵不相交的有向树构成
- 天生有向丛林：由多棵不相交的天生有向树构成
有向丛林与天生有向丛林的别的雷同点实际上就是有向树与天生有向树之间的雷同点，这我就不再赘述；
差别点
- 极点要求差别
- 有向丛林：丛林中的结点总数可以比原图的极点总数少
- 天生有向丛林：丛林中的结点总数必须与原图的极点总数相当
- 与原图关系差别
- 有向丛林：丛林中的子树只须要原图中的子图满意有向树的条件即可
- 天生有向丛林：丛林中的子树肯定是对应有向图的天生有向树，且子树的数目与原图中互不相交的子图的数目雷同
二、权
权值：权值指的是图中的每条边上标明的具有某种意义的数值；
带权图：带权图指的是图中的边上带有权值的图，也称为网；
带权路径长度：带权路径长度指的是路径上全部边的权值之和
在哈夫曼树中我们就打仗了权值与带权路径长度的概念，如今我们又再一次与它们相遇了，这里我们直接通过图来举行分析：
在上图中每条边上都被赋予了一个值，这些值就是边的权值。
而像上图如许边上被赋予了权值的图就是带权图，也可以将其称为网
从结点a到结点d的路径有两条：
- 路径1： a − − > b − − > c − − > d a-->b-->c-->d a−−>b−−>c−−>d，该路径上的权值之和为 1 + 2 + 3 = 6 1 + 2 + 3 = 6 1+2+3=6
- 路径2： a − − > d a-->d a−−>d，该路径上的权值之和为 1 1 1
不管是路径1照旧路径2，其路径上的权值之和就是该路径的带权路径长度。
三、特殊图
3.1 希奇图与稠密图
希奇图：希奇图指的是边的数目很少的图；
稠密图：稠密图指的是边的数目许多的图；
希奇图与稠密图时相对而言的，一样寻常环境下，当图 G = ( V , E ) G = (V, E) G=(V,E) 满意 ∣ E ∣ < ∣ V ∣ l o g 2 ∣ V ∣ |E| < |V|log_2|V| ∣E∣<∣V∣log2∣V∣ 时，可以将图 G G G 视为希奇图；反之，为稠密图。
希奇图与稠密图的概念，我们仅做相识即可，不必过于穷究，这里就不再睁开。
3.2 完全图
完全图又称为简朴完全图，因此我们不思量多重图。
所谓的完全图，实际上指的是一个图中恣意两个结点之间都相互毗连，即：
- 在有向图中，恣意两个结点直接都存在两条弧 < a , b > <a, b> <a,b> 与 < b , a > <b, a> <b,a>
- 在无向图中，恣意两个结点之间都存在一条边 ( a , b ) (a, b) (a,b)
我们可以通过边的数目来判断一个图是否为完全图，而对于有向图和无向图而言，其边的数目的判断是差别等的，下面我们就分别来看一下两种图中怎样判断是否为完全图
3.2.1 无向完全图
对于无向图，边的取值范围 ∣ E ∣ ∈ [ 0 , n ( n − 1 ) 2 ] |E| \in [0, \frac{n(n-1)}2] ∣E∣∈[0,2n(n−1)] ，当无向图的边的数目为 n ( n − 1 ) 2 \frac{n(n-1)}2 2n(n−1) 时，则该无向图称为无向完全图：
上图中，边的数目满意 ∣ E ∣ = 3 × ( 3 − 1 ) 2 = 3 |E| = \frac{3 × (3 - 1)}{2} = 3 ∣E∣=23×(3−1)=3这就是一个无向完全图。
在上图中，边的数目 ∣ E ∣ = 4 < 4 × ( 4 − 1 ) 2 = 6 |E| = 4 < \frac{4 × (4 - 1)}{2} = 6 ∣E∣=4<24×(4−1)=6 因此这不是一个完全图。
3.2.2 有向完全图
在有向图中，边的取值范围 ∣ E ∣ ∈ [ 0 , n ( n − 1 ) ] |E| \in [0, n(n-1)] ∣E∣∈[0,n(n−1)] ，当无向图的边的数目为 n ( n − 1 ) n(n-1) n(n−1) 时，则该有图称为有向完全图：
上图中，边的数目满意 ∣ E ∣ = 2 × ( 2 − 1 ) = 2 |E| = 2 × (2 - 1) = 2 ∣E∣=2×(2−1)=2这就是一个有向完全图。
在上图中，边的数目 ∣ E ∣ = 3 < 3 × ( 3 − 1 ) = 6 |E| = 3 < 3 × (3 - 1) = 6 ∣E∣=3<3×(3−1)=6 因此这不是一个完全图。
结语
从天生树的边数公式到有向丛林的分解逻辑，本文深入分析了图论中树形布局的焦点原理。
这些知识是学习图算法（如Kruskal、Prim）的必经之路，更为交际网络层级分析、交通拓扑优化提供理论支持。
假如本文助您理清知识脉络：
✅ 点击关注，追踪后续《图的存储及根本操纵》深度分析
✅ 点赞支持，鼓励更多原创技能内容
✅ 收藏备用，构建算法知识体系
✅ 转发分享，与偕行共探图论奥秘
下期剧透：毗连矩阵怎样用二维数组高效形貌图布局？稠密图存储的时空代价怎样衡量？我们将在下一篇发表答案！您的每一次互动，都是我们打磨佳构的动力源泉！🔥
|
发表于 2025-9-30 14:34:19