在学习数据结构图时，自己对
极大连通子图
、
极小连通子图
一类概念的理解，如有不妥，希望大家指正：
1、
极大连通子图（即连通分量）
、
极小连通子图
都为图的连通子图，极大即包含边最多，极小即包含边最少；
2、对于连通图
极大连通子图
（包含边最多的连通子图）即本身（包含所有边）。
极小连通子图
为某一顶点子集所确定的连通子图中包含边最少的连通子图（n个顶点，无向连通图最少n-1条边，有向连通图最少n条边——成环）。图全部顶点所确定的极小连通子图即为连通图的
生成树
。
3、对于非连通图
极大连通子图
即为非连通图中连通的每一个部分（每一个连通部分包含边最多的连通子图即为该连通部分本身）。
极小连通子图
为非连通图中每一连通部分的极小连通子图。由每一连通部分所有顶点所确定的极小连通子图即为该连通部分的
生成树
，各连通部分的生成树构成非连通图的
生成森林
。
版权声明：本文为ITcainiao_原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。