完全图、连通图、非连通图、连通分量、强连通图、生成树的概念

大家好，欢迎来到IT知识分享网。

图

对于n个结点的图来说：

无向完全图：有n（n-1）/2 条边，如下：4个顶点有6条边

连通图：无向图中，任意两个顶点是连通的（一个顶点不必与另一个顶点直接相连，可以通过其它顶点到达即可）最少有n-1条边；如下：4个顶点最少需要3条边才能够连通

非连通图，即边数少于n-1条，最多有（n-1）*(n-2)/2条，如下：5个结点，非连通，最多有6条边

连通分量：无向图中（区别于有向图）的极大连通子图，极大即要求拥有连通子图的所有边，例如，如果A1中少了a-d这条边就不是极大连通子图了

强连通图：从a到b和从b到a都有路径。最少有n条边，假若少了A-D的路径，则A可以到D，但是D到不了A，就不满足条件。

强连通分量：有向图中的极大强连通子图，对比无向图中连通分量

生成树：包含图中全部顶点的一个极小连通子图（生成树不唯一）。若去除一条边，则生成树会变成非连通图；若多加上一条边，则会形成回路

注意：极大连通子图要求连通子图包含所有边，极小连通子图要求使图保存连通的前提下使边数最少。

简单路径：顶点不重复出现的路径称为简单路径

区分：无向图关于连通图和连通分量，有向图关于强连通图和强连通分量