| sidebar_position | 4 |
|---|
算子类别：Connectivity & Components（连通性、连通分量与割/切割分析）
算法数量：17 个
适用阶段：网络结构体检、孤岛/分区识别、稳健性评估、关键节点/关键边定位、故障/攻击面分析、强弱连通分析、桥接结构识别、SCC 压缩建模
产品定位：为“网络是否连通 / 分成几块 / 哪些节点或边一断就分裂 / 最少切多少才能断开 / 有向图如何压缩成组件级 DAG / 哪些边是局部桥梁”提供统一能力底座。
Connectivity & Components 算子集面向无向图与有向图的连通性分析，覆盖以下核心问题：
-
连通性与连通分量
- 无向图是否整体连通？
- 图分成多少个连通块？
- 每个连通块包含哪些节点？
- 典型算法：
is_connected,connected_components,number_connected_components
-
有向图强弱连通分析
- 有向图是否强连通？
- 忽略方向后是否弱连通？
- 哪些节点构成强连通分量或弱连通分量？
- 典型算法：
is_strongly_connected,strongly_connected_components,is_weakly_connected,weakly_connected_components
-
网络稳健性指标
- 最少移除多少节点会让网络断开？
- 最少移除多少边会让网络断开？
- 两个指定节点之间的最小割是多少？
- 典型算法：
node_connectivity,edge_connectivity
-
最小割与关键结构
- 哪些节点一起移除会让网络断开？
- 哪些边一起移除会让网络断开？
- 哪些节点是割点？
- 哪些边是桥？
- 典型算法：
minimum_node_cut,minimum_edge_cut,articulation_points,bridges
-
桥接结构与双连通分解
- 哪些区域内部更稳健？
- 哪些边连接了原本独立的结构块？
- 删除哪些边会造成组件分裂？
- 典型算法：
bridge_components,biconnected_component_edges,local_bridges
-
有向组件压缩
- 如何把强连通分量压缩成组件级 DAG？
- 如何从复杂有向图中提取高层级依赖结构？
- 典型算法：
condensation
| 能力类型 | 对应算子 | 功能描述 |
|---|---|---|
| 无向图整体连通性 | is_connected |
判断无向图是否为单一连通块 |
| 无向图连通分量 | connected_components |
输出每个连通分量的节点集合 |
| 无向图分量数量 | number_connected_components |
返回连通分量数量 |
| 有向图强连通性 | is_strongly_connected |
判断有向图中是否任意两点双向可达 |
| 有向图强连通分量 | strongly_connected_components |
输出 SCC（强连通分量）划分 |
| 有向图弱连通性 | is_weakly_connected |
忽略方向后判断有向图是否连通 |
| 有向图弱连通分量 | weakly_connected_components |
输出 WCC（弱连通分量）划分 |
| 稳健性指标（节点） | node_connectivity |
最少移除多少节点可使图断开，或使指定 s-t 断开 |
| 稳健性指标（边） | edge_connectivity |
最少移除多少边可使图断开，或使指定 s-t 断开 |
| 最小节点割集合 | minimum_node_cut |
给出使图断开或使 s-t 不连通的最小节点集合 |
| 最小边割集合 | minimum_edge_cut |
给出使图断开或使 s-t 不连通的最小边集合 |
| 关键节点（割点） | articulation_points |
删除后会增加无向图连通分量数量的节点 |
| 桥连通块分解 | bridge_components |
基于桥边分解出的 2-edge-connected components |
| 双连通分量边集合 | biconnected_component_edges |
输出无向图中双连通分量对应的边集合 |
| 强连通分量压缩 | condensation |
将有向图的 SCC 压缩为 DAG |
| 桥边识别 | bridges |
找出无向图中删除后会增加连通分量数量的边 |
| 局部桥识别 | local_bridges |
找出端点之间没有共同邻居的局部桥边，并可计算跨度 |
-
输入
G：NetworkX Graph / DiGraph- 无向连通性算法通常使用
Graph - 强连通、弱连通、SCC 压缩通常使用
DiGraph - 部分割与连通度算法同时支持有向图和无向图
- 无向连通性算法通常使用
-
常见输出
- 判定类：
bool - 分量类：
generator[set(node)] - 连通性指标：
int - 最小割：
set(node)或set(edge) - 割点：节点迭代器
- 桥边：边迭代器
- 双连通分量：
generator[list[edge]] - SCC 压缩图：
DiGraph
- 判定类：
说明：
- “强连通 / 弱连通”只对有向图有意义。
- “割点 / 桥 / 双连通分量 / 桥连通块”通常用于无向图的结构稳健性分析。
- “最小割 / 节点连通度 / 边连通度”可用于全局网络，也可用于指定节点对
s, t的局部稳健性分析。
功能说明
判断无向图中是否任意两个节点之间都存在路径可达。
产品价值
- 网络健康度的第一道体检
- 快速判断是否存在孤岛、断裂区域或未接入节点
- 适合作为后续全局算法的前置校验
典型场景
- 道路网络是否存在完全孤立区域
- 设备互联拓扑是否为一张完整网络
- 社交网络是否存在完全隔离圈子
- 供应链网络是否存在断裂子网
适用与特性
- 图类型：无向图
- 输出：
bool - 复杂度：
O(V + E)
功能说明
输出无向图中每个连通分量的节点集合。一个连通分量代表一个内部互相可达、但与其他分量不连通的子网络。
产品价值
- 识别网络被切成了哪些区域、社群或子系统
- 为后续分区统计、分区建模、分区调度提供边界
- 帮助定位孤立组件和异常断裂结构
典型场景
- 物流站点网络：分出互不连通的运营区域
- 设备互联网络：找出孤立子网
- 社交网络：识别互不接触的圈子
- 企业关系网络：识别互不关联的集团簇
适用与特性
- 图类型：无向图
- 输出：
generator[set(node)] - 复杂度：
O(V + E)
功能说明
返回无向图中的连通分量个数。
产品价值
- 快速量化网络碎片化程度
- 可作为网络健康 KPI
- 便于监控故障前后网络被分裂成多少块
典型场景
- 城市路网断裂后的分区数量评估
- 设备网络故障后的子网数量统计
- 协作网络中孤立团队数量统计
- 风控网络中独立团伙数量估算
适用与特性
- 图类型：无向图
- 输出：
int - 复杂度：
O(V + E)
功能说明
判断有向图是否满足任意两个节点之间都双向可达，即 u → v 且 v → u 都存在路径。
产品价值
- 判断有向网络是否形成完整闭环结构
- 适合分析互相调用、互相跳转、资金可回流等系统
- 可用于识别是否存在方向性阻断
典型场景
- 服务调用：是否任意服务都能经调用链互相到达
- 页面导航：是否任意页面都能到达并返回
- 交易网络：是否形成可回流的闭环网络
- 状态机分析：是否所有状态互相可达
适用与特性
- 图类型：有向图
- 输出：
bool - 复杂度：
O(V + E)
功能说明
输出有向图的强连通分量划分。每个 SCC 内任意两个节点都双向可达。
产品价值
- 识别循环模块、闭环群组、互相依赖结构
- 常用于依赖分析、死循环排查、模块化拆解
- 是有向图压缩和层级建模的重要基础
典型场景
- 服务依赖图：找出互相依赖成环的模块
- 流程图：找出可以回到起点的循环步骤群
- 交易网络：识别资金循环小团体
- 代码依赖：定位循环 import 或循环引用模块
适用与特性
- 图类型：有向图
- 输出：
generator[set(node)] - 复杂度：
O(V + E)
功能说明
将有向图视为无向图，忽略边方向后判断图是否连通。
产品价值
- 判断有向网络在结构上是否仍是一张网
- 即使方向上不互达，也能判断整体是否割裂
- 适合做有向网络的宏观连通体检
典型场景
- 邮件发送网络：忽略方向看组织是否连成整体
- 关注网络：忽略方向看用户是否割裂成多个群落
- 页面链接：忽略方向看站点是否被分割成孤岛
- 服务调用：判断业务域结构上是否互有关联
适用与特性
- 图类型：有向图
- 输出：
bool - 复杂度：
O(V + E)
功能说明
在忽略方向后，将有向图划分为若干互相连通的分量。
产品价值
- 识别方向网络的结构分区
- 为分区内进一步做 SCC、中心性、社区发现等分析提供边界
- 可用于识别孤立业务域或独立传播域
典型场景
- 关注网络：识别互不相连的社群域
- 邮件网络：识别组织内互不沟通的群体
- 服务调用：识别互不关联的业务系统
- 交易网络：识别没有交易连接的账户群
适用与特性
- 图类型：有向图
- 输出：
generator[set(node)] - 复杂度：
O(V + E)
功能说明
返回最少需要删除多少个节点才能让图断开；如果指定 s, t，则返回最少删除多少节点能让 s 与 t 不连通。
产品价值
- 量化网络抗节点故障或攻击的能力
- 评估关键设备、关键岗位、关键账户的冗余程度
- 可用于稳健性评分和加固预算评估
典型场景
- 数据中心：最少坏几台设备会断网
- 城市路网：最少封几个路口会割裂交通
- 协作网络：最少离开几个人团队会分裂
- 供应链网络：最少失效几个企业会造成断供
关键参数
s, t：指定源节点和目标节点，做局部连通度分析flow_func：最大流实现选择，影响性能
适用与特性
- 图类型：有向图 / 无向图
- 输出：
int - 复杂度：与最大流算法相关
功能说明
返回最少需要删除多少条边才能让图断开；如果指定 s, t，则返回最少删除多少条边能让 s 与 t 不连通。
产品价值
- 量化网络抗链路故障或边攻击的能力
- 用于链路冗余规划、网络加固和容灾设计
- 能判断系统是否存在低冗余连接瓶颈
典型场景
- 机房网络：最少断几条链路会割裂网络
- 道路网络：最少封几条路会导致分区
- 物流网络：最少中断几条线路会断供
- 通信网络：链路冗余能力评估
关键参数
s, t：指定源节点和目标节点flow_func：最大流实现选择cutoff：阈值提前停止，适合只判断是否低于某个冗余等级
适用与特性
- 图类型：有向图 / 无向图
- 输出：
int - 复杂度：与最大流算法相关
功能说明
输出一个最小节点集合，删除这些节点后图会断开；如果指定 s, t，则删除这些节点后 s 与 t 不再连通。
产品价值
- 直接给出最脆弱节点集合
- 支持故障演练、攻击面评估和加固优先级制定
- 比单纯连通度指标更具可执行性
典型场景
- 数据中心：最少哪几台设备一起故障会断网
- 交通网络：最少封哪几个路口会割裂城市路网
- 电网网络：最少哪几个站点失效会分区
- 组织网络：哪些关键人员离开会造成协作断裂
关键参数
s, t：指定源节点和目标节点，做局部割分析flow_func：最大流实现选择
适用与特性
- 图类型：有向图 / 无向图
- 输出：
set(node) - 复杂度：与最大流算法相关
功能说明
输出一个最小边集合，删除这些边后图会断开；如果指定 s, t，则删除这些边后 s 与 t 不再连通。
产品价值
- 直接定位最脆弱链路集合
- 支持备份线路规划、链路加固和故障演练
- 可用于评估跨区域、跨系统连接的脆弱性
典型场景
- 机房网络：最少切断哪几条链路会割裂网络
- 城市路网：最少封哪几条路会形成分区
- 物流网络：最少中断哪几条线路会断供
- 供应链网络：关键运输关系识别
关键参数
s, t：指定源节点和目标节点flow_func：最大流实现选择
适用与特性
- 图类型：有向图 / 无向图
- 输出：
set(edge) - 复杂度：与最大流算法相关
功能说明
在无向图中，如果删除某个节点会导致连通分量数量增加，则该节点是割点。
产品价值
- 识别典型单点故障节点
- 与节点连通度和最小节点割互补
- 适合快速定位结构上最明显的薄弱点
典型场景
- 城市路网：封闭哪些路口会导致交通割裂
- 数据中心：哪些设备故障会导致网络分裂
- 社交网络：哪些用户离开会把社群拆开
- 供应链网络：哪些企业失效会造成上下游断裂
适用与特性
- 图类型：无向图
- 输出：节点迭代器
- 复杂度：
O(V + E)
功能说明
找出无向图中所有 2-边连通分量。一个桥连通块内部通常不会因为单条边失效而被切开，块与块之间由桥边连接。
产品价值
- 将网络拆成内部边冗余更强的结构块
- 适合做网络分区、韧性模块识别和加固分层
- 可以辅助定位网络的骨架结构与脆弱连接
典型场景
- 路网：内部替代路线更丰富的区域块
- 数据中心：内部链路冗余更高的设备群
- 协作网络：内部联系更稳固的合作小组
- 通信网络：抗单链路故障的子网识别
适用与特性
- 图类型：无向图
- 输出：
generator[set(node)] - 复杂度：
O(V + E)
功能说明
输出无向图中双连通分量对应的边集合。双连通分量内部通常没有单个割点可以将该分量拆开。
产品价值
- 识别内部节点冗余更强的结构块
- 辅助分析哪些区域不容易因单点节点故障而分裂
- 可与
articulation_points一起用于块-割点结构分析
典型场景
- 路网：抗单路口封闭的区域识别
- 通信网络：抗单设备故障的链路块分析
- 社交网络：内部关系更稳固的群体结构
- 供应链网络：节点冗余较强的子系统识别
适用与特性
- 图类型：无向图
- 输出：
generator[list[edge]] - 复杂度：通常
O(V + E)
功能说明
将有向图中的每个强连通分量压缩为一个节点，得到一个新的有向无环图（DAG）。压缩图中的边表示不同强连通分量之间的依赖或可达关系。
产品价值
- 将复杂有向图抽象为组件级结构
- 适合从循环依赖中提取高层 DAG
- 可用于模块化分析、依赖分层和流程简化
典型场景
- 服务依赖：将互相依赖的一组服务压缩为一个模块
- 代码依赖：将循环引用包压缩后分析包间层级
- 交易网络：将资金循环团伙压缩后观察团伙间流向
- 流程网络：将循环步骤压缩后进行高层流程排序
适用与特性
- 图类型：有向图
- 输出：
DiGraph - 特点：输出图是 DAG
- 复杂度：通常
O(V + E)
功能说明
找出无向图中的桥边。桥边是删除后会增加连通分量数量的边，也称割边。
产品价值
- 直接识别单链路故障风险
- 适合链路加固、备份线路规划和网络脆弱性分析
- 与
articulation_points形成“关键边 + 关键点”的结构诊断组合
典型场景
- 道路网络：封闭后会割裂区域的道路
- 通信网络：断开后会导致子网隔离的链路
- 物流网络：中断后会导致供应断裂的运输线
- 设备网络：无备份路径的关键连接
适用与特性
- 图类型：无向图
- 输出：边迭代器
- 复杂度：
O(V + E)
功能说明
找出局部桥边。局部桥通常指边的两个端点之间没有共同邻居；如果移除该边，端点之间的最短替代路径会变长。可进一步计算该边的跨度。
产品价值
- 识别局部结构中的跨圈层连接
- 可发现不一定是全局桥、但在局部关系中非常关键的连接
- 适合社交网络、推荐网络和局部脆弱性分析
典型场景
- 社交网络：连接两个朋友圈的弱关系边
- 合作网络：连接两个团队的跨组协作关系
- 推荐网络：连接两个兴趣圈层的关键交互
- 风控网络：连接两个局部团伙的可疑关系
关键参数
with_span：是否返回局部桥的跨度weight：用于计算替代路径长度的边权字段
适用与特性
- 图类型：无向图
- 输出：边迭代器，或带跨度的边信息
- 适合局部桥接结构和弱连接分析
-
先回答“是否一张网”
- 无向图：
is_connected - 有向图结构上是否连通：
is_weakly_connected - 有向图方向上是否互达：
is_strongly_connected
- 无向图：
-
再做“分成几块、每块是谁”
- 无向图：
connected_components+number_connected_components - 有向图：
weakly_connected_components/strongly_connected_components
- 无向图：
-
做“韧性与断点定位”
- 节点冗余指标：
node_connectivity - 边冗余指标：
edge_connectivity - 最小节点割：
minimum_node_cut - 最小边割：
minimum_edge_cut
- 节点冗余指标：
-
找直观关键点与关键边
- 割点：
articulation_points - 桥边：
bridges - 局部桥边：
local_bridges
- 割点：
-
做组件级结构分析
- 桥连通块：
bridge_components - 双连通分量边集合：
biconnected_component_edges - 有向 SCC 压缩：
condensation
- 桥连通块：
- “这张无向图是不是连通的？如果不是，分成了几块？”
- “有向图在忽略方向后是否连通？方向意义上是否强连通？”
- “输出所有强连通分量，并按规模排序。”
- “将强连通分量压缩成 DAG，看看组件之间的依赖层级。”
- “这张网络最少断几条边或坏几个节点会被切开？”
- “给出一个最小节点割或最小边割集合。”
- “列出所有割点，用于单点故障排查。”
- “列出所有桥边，找出没有备份路径的关键链路。”
- “哪些边是局部桥，连接了不同的局部圈层？”
- “把网络拆成 bridge components，看看哪些区域内部更稳健。”
- “输出双连通分量的边集合，用于分析抗单点故障结构。”
-
先区分图类型
- 无向图使用
is_connected、connected_components、bridges、articulation_points等。 - 有向图使用
is_strongly_connected、strongly_connected_components、is_weakly_connected、weakly_connected_components、condensation等。
- 无向图使用
-
强连通和弱连通含义不同
- 强连通要求方向上双向可达。
- 弱连通只要求忽略方向后结构连通。
- 有向业务网络中，两者经常差异很大。
-
全局连通度与局部 s-t 连通度要区分
- 全局
node_connectivity/edge_connectivity衡量整张图最脆弱处。 - 指定
s, t后衡量两个节点之间的局部冗余能力。
- 全局
-
割点与桥边适合快速体检
articulation_points和bridges通常计算较快、解释直观。- 它们能快速定位明显单点或单边故障风险。
-
最小割更适合制定加固方案
minimum_node_cut和minimum_edge_cut直接给出需要加固或保护的节点/边集合。- 适合用于故障演练、攻击模拟和容灾规划。
-
SCC 压缩适合复杂有向图降维
- 原图中存在大量循环依赖时，可先做
condensation。 - 压缩后的图是 DAG，更适合做拓扑排序、层级分析和高层可视化。
- 原图中存在大量循环依赖时，可先做
-
局部桥不等于全局桥
bridges删除后会增加全图连通分量数量。local_bridges更强调局部邻域中的桥接作用，适合社交弱关系和跨圈层连接分析。
| 序号 | 算子名称 | 中文说明 |
|---|---|---|
| 1 | is_connected |
判断无向图是否连通 |
| 2 | connected_components |
无向图连通分量 |
| 3 | number_connected_components |
无向图连通分量数量 |
| 4 | is_strongly_connected |
判断有向图是否强连通 |
| 5 | strongly_connected_components |
强连通分量 |
| 6 | is_weakly_connected |
判断有向图是否弱连通 |
| 7 | weakly_connected_components |
弱连通分量 |
| 8 | node_connectivity |
节点连通度 |
| 9 | edge_connectivity |
边连通度 |
| 10 | minimum_node_cut |
最小节点割 |
| 11 | minimum_edge_cut |
最小边割 |
| 12 | articulation_points |
割点 |
| 13 | bridge_components |
桥连通块 |
| 14 | biconnected_component_edges |
双连通分量边集合 |
| 15 | condensation |
强连通分量压缩图 |
| 16 | bridges |
桥边 / 割边 |
| 17 | local_bridges |
局部桥 |