Cytoscape.js 双连通分量与割点分析:`eles.htbc()` / `hopcroftTarjanBiconnected()` 完整指南

原创2026-09-22 16:12:161,757 阅读
文章标签:数据可视化

Cytoscape.js 双连通分量与割点分析:eles.htbc() / hopcroftTarjanBiconnected() 完整指南

导读

本文系统讲解 Cytoscape.js 提供的 Hopcroft-Tarjan 双连通分量分析能力,覆盖 htbc()、htb()、hopcroftTarjanBiconnected()、hopcroftTarjanBiconnectedComponents() 四组等价 API 的返回值结构、子图语义与调用方式,并结合仓库源码剖析其基于 DFS 的 low 值算法实现、割点判定规则与自环、孤立节点等边界处理,帮助你在网络可视化项目中准确识别割点与双连通块,用于健壮性分析、图分割与网络拓扑洞察。

一、功能定位:找出"图在哪里断开"

在无向图论中,割点(cut vertex / articulation point) 是指移除后会使图分裂为更多连通分量的节点;双连通分量(biconnected component) 则是不含割点的最大连通子图,块内任意两条边都位于同一个简单环上(桥边和孤立点构成退化分量)。

Cytoscape.js 将 Hopcroft-Tarjan 算法封装为集合方法 eles.htbc(),可以在不引入外部图算法库的情况下,直接对当前图(或图中任意子集)计算:

  • 全部双连通分量(每个分量是一个同时包含节点与边的 collection);
  • 全部割点(以节点 collection 形式返回)。

该 API 是 src/collection/algorithms/index.mjs 中统一导出的图算法族成员,与 dijkstra、kargerStein、tarjanStronglyConnected 等并列,注册到所有集合(collection)原型上,因此任意节点/边集合都可以直接调用。

二、API 签名与四个等价别名

在 index.d.ts 的类型声明中,四个名称均指向同一功能,返回类型完全一致:

hopcroftTarjanBiconnected(): { cut: NodeCollection; components: CollectionReturnValue };
hopcroftTarjanBiconnectedComponents(): { cut: NodeCollection; components: CollectionReturnValue };
htb(): { cut: NodeCollection; components: CollectionReturnValue };
htbc(): { cut: NodeCollection; components: CollectionReturnValue };

对应别名在 hopcroft-tarjan-biconnected.mjs 源码末尾统一导出:

export default {
  hopcroftTarjanBiconnected,
  htbc: hopcroftTarjanBiconnected,
  htb: hopcroftTarjanBiconnected,
  hopcroftTarjanBiconnectedComponents: hopcroftTarjanBiconnected
};

四个名称共用同一个实现函数,你可以在不同场景按可读性或缩写习惯任选其一。

三、返回值详解

依据 hopcroftTarjanBiconnected.md,该函数返回如下形式的对象:

{
  cut, /* Collection of nodes identified as cut vertices */
  components /* An array of collections corresponding to each biconnected component */
}
字段 类型 含义
cut 节点集合(eles.spawn(cutVertices),见 源码第 103-108 行) 被识别为割点的所有节点
components 集合数组 每个双连通分量对应一个 collection,同时包含该分量内的节点与边

需要特别指出的是:components 中的每个分量不仅是节点列表,而是同时混入节点与边的完整集合(由源码 component.merge(edge) 与 component.merge(node) 构建,见 源码第 21-36 行)。因此你可以直接对分量调用 select()、addClass() 等集合方法做可视化高亮。

四、子图语义:只在调用集合内计算

原文档特别强调了一个关键语义:

Note that this function identifies biconnected components and cut vertices only within the subset of the graph in the calling collection.

也就是说,算法运行在调用该方法的集合所代表的子图上,而不是整张图。这一点在源码中有三处显式体现:

  1. 每个节点参与计算时,其关联边先与调用集合求交集(第 47-49 行):
    let edges = eles.getElementById(currentNode)
                    .connectedEdges()
                    .intersection(eles);
    
  2. 构建分量时,节点及其关联边同样与调用集合求交集(第 22-28 行);
  3. 顶层循环仅遍历调用集合内的节点(第 91-101 行)。

这意味着你可以只对感兴趣的局部子图(例如某个复合节点的子节点集合、或某个社区)调用 htbc(),割点判定与分量划分将完全局限于该子集的连通结构内,非常便于聚焦分析。

五、基本用法示例

原文档给出的最小可运行示例为:

var ht = cy.elements().htbc();

ht.components[0].select();

在此基础上可以扩展出更实用的用法——例如在 ready 回调中分析全图,并对割点与各分量施加不同样式:

var cy = cytoscape({
  container: document.getElementById('cy'),
  elements: [ /* 节点与边数据 */ ],
  style: [
    { selector: 'node', style: { 'background-color': '#ccc' } },
    { selector: 'node.cut', style: { 'background-color': '#e33', 'border-width': 2 } },
    { selector: 'edge', style: { 'width': 2 } }
  ],
  ready: function () {
    var ht = this.elements().htbc();

    // 高亮割点
    ht.cut.addClass('cut');

    // 依次遍历每个双连通分量
    ht.components.forEach(function (comp, i) {
      console.log('Component #' + i, comp.map(function (ele) {
        return ele.id();
      }));
    });
  }
});

cut 是标准 collection,可以继续链式调用 select()、addClass()、json() 等全部集合 API;components 中的每个元素同样如此。

六、源码级原理剖析

该实现位于 src/collection/algorithms/hopcroft-tarjan-biconnected.mjs,是一个基于深度优先搜索(DFS)的经典 Hopcroft-Tarjan 线性时间算法,核心机制如下。

6.1 DFS 编号与 low 值

每个节点记录三个状态(第 42-46 行):

nodes[currentNode] = {
  id : id,      // DFS 访问顺序编号
  low : id++,   // 子树中通过回边能到达的最小编号
  cutVertex : false
};

biconnectedSearch(root, currentNode, parent) 从根出发递归搜索:

  • 树边:访问未遍历的邻居 otherNodeId 后,用子节点的 low 值更新父节点(第 75-76 行):
    nodes[currentNode].low = Math.min(nodes[currentNode].low, nodes[otherNodeId].low);
    
  • 回边:访问已编号的邻居时,用其 DFS 编号更新 low 值(第 83-84 行):
    nodes[currentNode].low = Math.min(nodes[currentNode].low, nodes[otherNodeId].id);
    

每条被遍历的边在首次遇到时压入边栈 stack(第 64-71 行),并由 visitedEdges 去重,确保无向图中的每条边只处理一次。

6.2 割点判定规则

  • 非根节点:当子节点 otherNodeId 满足 nodes<a href="https://link.gitcode.com/i/27d9436d8274409710ce8071e37654f5" target="_blank">currentNode].id <= nodes[otherNodeId].low 时([第 78-81 行),说明该子树无法通过回边绕回当前节点上方,当前节点即为割点,并立即用边栈构建一个双连通分量:
    if (nodes[currentNode].id <= nodes[otherNodeId].low) {
      nodes[currentNode].cutVertex = true;
      buildComponent(currentNode, otherNodeId);
    }
    
  • 根节点:根节点的割点性由子树数量决定。算法统计根出发的 DFS 子树边数 edgeCount,若 edgeCount > 1 则根是割点(第 95-98 行):
    edgeCount = 0;
    biconnectedSearch(nodeId, nodeId);
    nodes[nodeId].cutVertex = (edgeCount > 1);
    

6.3 分量构建与边界情况

buildComponent(x, y) 从边栈顶部一直弹出到边 (x, y) 为止,形成该双连通块的所有边,再将边的端点节点与节点自身的关联边合并进分量(第 10-38 行)。实现中还覆盖了三个经典边界情况:

  • 孤立节点:没有任何关联边(edges.size() === 0)的节点被作为单元素分量直接加入 components(第 51-52 行);
  • 自环边:当节点是割点时,只把该节点的自环边合并进分量,避免跨分量污染(第 30-34 行);
  • 非连通图:顶层 eles.forEach 会为每个未访问的节点启动新一轮 DFS,因此调用集合本身不必是连通的,所有连通块都会被完整分析。

七、测试用例验证

仓库在 test/collection-hopcroft-tarjan-biconnected.mjs 中为该功能提供了两组关键断言,可直接运行测试复现:

  • 单分量无割点(第 102-115 行):cy0 与 cy2 各返回 components.length === 1 且 cut 为空数组。其中 cy2 包含自环边(2-5、2-8),验证自环不会导致误判割点;
  • 多分量多割点(第 117-129 行):cy1 返回 8 个双连通分量,割点为 1-2、1-7、1-8、1-10 四个节点;components[0] 是孤立节点 1-0 的单元素分量,恰好印证了上文所述的孤立节点处理逻辑。

测试数据表明,每个分量 collection 中节点与边按算法遍历顺序混排(例如 components[1] 为 [ "1-21", "1-2", "1-4", "1-24", "1-3", "1-20" ]),因此按索引消费 components 时不宜假设特定顺序,更稳妥的做法是按元素 group() 或 isNode()/isEdge() 分别过滤。

八、与相关算法的区分

使用时应将本方法与另一割集类算法区分开:

  • eles.htbc()(本方法):无向图上的双连通分量 + 割点,cut 是节点集合,适用于检测"移除哪些节点会破坏连通性";
  • eles.tarjanStronglyConnected():有向图上的强连通分量,cut 是边集合(见 tarjanStronglyConnected.md),适用于有向依赖分析;
  • eles.kargerStein():随机化最小割算法,返回最小割边集合与划分,适用于全局最小割估算。

三者同属于 src/collection/algorithms 目录下的图算法族,可根据图的类型与目标(节点脆弱性 / 环路依赖 / 最小割)选择对应入口。

九、典型应用场景

  • 网络健壮性分析:定位通信网、社交网中的关键节点(割点),评估单点故障影响范围;
  • 图结构分解:将复杂图按双连通块拆分,便于分块渲染、局部样式或按块进行布局计算;
  • 环路可视化:双连通分量内的边必然位于环上,可据此高亮环状结构,辅助环路识别与展示;
  • 交互辅助:对用户圈选(cy.$(':selected'))或复合节点的子集合调用 htbc(),实现子图级的结构洞察。

十、延伸阅读

登录后查看全文
cytoscape.js