dfs和bfs存储图的连通分量和连通(图)

dfs 和 bfs 使用邻接列表和邻接矩阵来存储图形。时间复杂度是O(NE)和O(N2)。如果遍历整个图，空间复杂度是O(N)如果解离根已知如果节点更靠近，那么BFS更好. 如果每个节点作为一个整体有很多边，那么 BFS 会消耗大量的内存。如果一棵树很深，解很少，那么 DFS 可能会很慢（相反，如果有很多解，并且都比较深，那么BFS会很慢）如果一个问题的深度是无限的，广度是有限的，那么DFS不能得到解决方案，但是BFS可以，反之亦然

1.连通性：连通性是指从顶点V到W有一条无向路径，则称V和W是连通的。

二、连通分量：无向图的最大连通子图。

连通分量的两个特征

1.最大顶点数：当前图再增加一个，不再连通。

2.最大边数：包含连接到子图中所有顶点的所有边。（所有顶点的所有包含边都在）

三、循环

起点与终点相等的路径。

四、连通图

图中的所有顶点都是连接的。

五、强联通和弱联通

如果有向图中的顶点 V 和 W 之间存在双向路径c语言无向图连通分量c语言无向图连通分量，则称 V 和 W 是强连通的。

六、强连通图

有向图中任意数量的顶点都是强连通的

七、强连通分量

有向图的最大强连通图

每次调用DFS(x)/BFS(x)，都会遍历x所在的连通分量。那么如果一个图不是连通图呢，我们对所有未访问的点执行一次所需的DFS(x)/BFS(x)，然后就可以遍历图的所有点了。

注意时间复杂度，如果有N个顶点和E条边。邻接表存储图的时间复杂度为O(N+E)，邻接矩阵的时间复杂度为O(N²)；