（数据结构）连通图
图存储结构分类之连通图连通：图中从一个顶点到达另一顶点，若存在至少一条路径，则称这两个顶点是连通着的图 1 顶点之间的连通状态示意图图 1 中，虽然 V1 和 V3 没有直接关联，但从 V1 到 V3 存在两条路径和，因此称 V1 和 V3 是连通的连通图（无向图）：任意两个顶点之间都能够连通图 2 连通图示意图图 2 中，因为此无向图中任意两顶点之间都是连通的，故此图就是一个连通图连通分量：若无
图存储结构分类之连通图
连通：图中从一个顶点到达另一顶点，若存在至少一条路径，则称这两个顶点是连通着的
图 1 顶点之间的连通状态示意图
图 1 中，虽然 V1 和 V3 没有直接关联，但从 V1 到 V3 存在两条路径 和
，因此称 V1 和 V3 是连通的
连通图（无向图）：任意两个顶点之间都能够连通
图 2 连通图示意图
图 2 中，因为此无向图中任意两顶点之间都是连通的，故此图就是一个连通图
连通分量：若无向图不是连通图，但图中存储某个子图符合连通图的性质，则称该子图为连通分量
此前的文章中提到过，由图中部分顶点和边构成的图为该图的一个子图，但此篇文章的子图指的是图中最大的连通子图（极大连通子图）
图 3 连通分量示意图
图 3 中，由于左侧的无向图不是连通图，所以可以将其分解为 3 个最大子图（右侧），且它们都满足连通图的性质，因此都是连通分量
强连通图
有向图中，若任意两个顶点 和
，满足从
到
以及从
到
都连通，也就是都含有至少一条通路，则称此有向图为强连通图（如下图 4）
图 4 强连通图
强连通分量：若有向图不是强连通图，但其包含的最大连通子图具有强连通图的性质，则称该子图为强连通分量
图 5 强连通分量
图 5 中，整个有向图不是强连通图，但其含有两个强连通分量
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
25
0- 0
已为社区贡献9条内容
所有评论(0)