数据可视化【免费下载链接】cytoscape.jsGraph theory (network) library for visualisation and analysis项目地址https://gitcode.com/gh_mirrors/cy/cytoscape.js点击查看免费下载导读本文围绕 cytoscape.js 集合方法eles.hierholzer()展开讲解如何利用 Hierholzer 算法在图中查找欧拉回路Eulerian circuit与欧拉路径Eulerian trail。该方法允许你限定在调用集合所包含的节点与边子集上运行算法并通过found与trail返回判定结果和按访问顺序排列的元素序列。读完本文你将掌握该方法的完整 API、选项语义、返回值结构以及底层判定欧拉图的实现原理和测试验证方式可直接在自己的图分析任务中使用。一、方法概述与适用场景eles.hierholzer()是 cytoscape.js 集合collection提供的图论算法之一用于执行Hierholzer 算法在图中寻找一条经过每条边恰好一次的路径trail。若路径首尾相接形成闭合回路则称为欧拉回路若只要求经过每条边恰好一次而不必闭合则称为欧拉路径。该方法的特点是只在调用集合的子图上运行。如 hierholzer.md 所述this function performs Hierholzers algorithm on only the subset of the graph in the calling collection也就是说只有集合内的节点和边参与计算集合外的元素被完全忽略既可以处理无向图也可以处理有向图既可以求闭合的欧拉回路也可以求首尾不同的欧拉路径取决于图本身是否满足相应条件。实际应用场景包括路径规划与遍历问题、图结构完整性校验判断一个网络是否可以一笔画、电路板布线、社交网络中的闭环检测等需要每条边恰好走一次的分析任务。二、返回值结构调用hierholzer()后返回一个对象结构如下{ found, /* true 或 false */ trail /* 欧拉路径/回路中的有序元素集合若找到 */ }字段说明字段类型含义foundboolean是否在指定子图中找到欧拉路径/回路。若子图不满足欧拉条件存在 2 个以上奇度节点、有向图入出度失衡、图不连通导致有边无法被覆盖等则为falsetrailCollection按访问顺序排列的元素集合节点与边交替出现节点 → 边 → 节点 → 边 → …以节点收尾仅在found为true时有效从源码看trail是通过this.spawn( trail, true )生成的一个新集合见 hierholzer.mjs因此你可以直接对trail继续使用集合 API例如选中、遍历、添加样式等。三、参数选项eles.hierholzer( options )接受一个配置对象源码中的默认值定义在 hierholzer.mjsconst hierholzerDefaults defaults({ root: undefined, directed: false });选项类型默认值说明rootstring选择器或单个元素集合undefined算法的起始节点。若不提供默认取调用集合中的第一个节点作为起点directedbooleanfalse是否按有向图处理。默认false即假设图为无向图几点关键语义对应 hierholzer.md 的 Regarding optional options 部分root 的两种传法传入字符串时会被当作选择器selector通过this.filter(root)[0].id()解析为具体节点 id传入元素对象时取root[0].id()。见 hierholzer.mjs默认起点若未提供root使用调用集合的第一个元素eles[0].id()作为起点见 hierholzer.mjs默认无向directed默认为false图按无向处理只有当图存在 2 个奇度节点时起点会被自动调整为其中一个奇度节点详见下文起点选择。此外源码还支持位置参数的旧式调用形式当options不是普通对象时会将arguments[0]、arguments[1]分别解析为root与directed见 hierholzer.mjs例如eles.hierholzer(#k, true)。四、算法核心欧拉图的判定条件Hierholzer 算法的第一步是判定子图是否可能存在欧拉路径/回路。源码依据图的有向性做了两套度检查4.1 无向图directed: false遍历集合中每个节点计算其度ele.degree(true)true表示包含自环。当且仅当奇度节点数量不超过 2时才可能存在欧拉路径let d ele.degree(true); if (d % 2) { if (!oddIn) oddIn id; else if (!oddOut) oddOut id; else dflag true; // 超过 2 个奇度节点不满足欧拉条件 }见 hierholzer.mjs。全部节点度为偶数 → 存在欧拉回路恰好 2 个节点度为奇数 → 存在欧拉路径且路径从其中一个奇度节点出发、终止于另一个超过 2 个奇度节点 →dflag置真直接返回found: false。4.2 有向图directed: true遍历每个节点计算d1 indegree - outdegree与d2 outdegree - indegreeif (d1 1) { // 入度比出度多 1 if (oddIn) dflag true; else oddIn id; } else if (d2 1) { // 出度比入度多 1 if (oddOut) dflag true; else oddOut id; } else if ((d2 1) || (d1 1)) { dflag true; // 差值大于 1不可能存在欧拉路径 }见 hierholzer.mjs。其理论依据是有向欧拉回路要求每个节点入度等于出度有向欧拉路径最多允许一个出度比入度多 1的起点和一个入度比出度多 1的终点任何差值超过 1 的节点都会使判定失败。关于度的实现细节集合的degree()/indegree()/outdegree()定义在 degree.mjs其中自环loop在degree()中按 2 计数在indegree()/outdegree()中分别按 1 计入includeLoops参数默认为true。4.3 起点startVertex的选择判定通过后源码按以下优先级确定起点见 hierholzer.mjs若存在奇度/失衡节点oddOut oddIn有向图要求显式提供的root必须是oddOut出度多的那个节点否则返回found: false无向图root必须是两个奇度节点之一否则返回found: false未提供root时自动取oddOut作为起点若所有节点度都平衡纯欧拉回路情形未提供root时取调用集合第一个节点的 id。也就是说用户提供的root如果与欧拉路径的法定起点冲突算法会直接判定found: false这是方法返回false的一种常见原因。五、示例完整可运行代码文档 hierholzer.md 给出的官方示例var hierholzer cy.elements().hierholzer({ root: #k, directed: true }); hierholzer.trail.select();下面是一个更完整的可运行版本包含图构建、调用与结果展示import cytoscape from cytoscape; const cy cytoscape({ container: document.getElementById(cy), elements: { nodes: [ { data: { id: a } }, { data: { id: b } }, { data: { id: c } }, { data: { id: d } } ], edges: [ { data: { id: e1, source: a, target: b } }, { data: { id: e2, source: b, target: c } }, { data: { id: e3, source: c, target: d } }, { data: { id: e4, source: d, target: a } } ] } }); // 在有向全图上寻找欧拉回路指定起点为 a const res cy.elements().hierholzer({ root: #a, directed: true }); if (res.found) { console.log(找到欧拉回路访问顺序); res.trail.forEach(ele { console.log(ele.isNode() ? 节点 ele.id() : 边 ele.id()); }); // 高亮整条路径 res.trail.select(); } else { console.log(该子图不存在欧拉回路/路径); }5.1 限定子集运行由于算法只作用于调用集合你可以先过滤再调用例如只考察一部分节点和边// 只考虑由节点 a、b 及其连边构成的子图 const subset cy.$(#a, #b).closedNeighborhood(); const res subset.hierholzer({ directed: false }); if (res.found) { res.trail.addClass(eulerian-trail); }5.2 利用返回结果做可视化trail是有序集合可配合动画演示遍历过程let idx 0; const eleIds res.trail.map(ele ele.id()); const timer setInterval(() { if (idx eleIds.length) { clearInterval(timer); return; } cy.getElementById(eleIds[idx]).addClass(visited); idx; }, 300);六、源码实现逐步剖析hierholzer方法定义在 src/collection/algorithms/hierholzer.mjs并通过 src/collection/algorithms/index.mjs 与其余算法一起挂载到集合原型上因此任何集合cy.elements()、cy.nodes()、过滤后的子集都可以调用。6.1 数据结构构建算法先建立两个索引结构见 hierholzer.mjsnodes[id]节点 id 到邻接边 id 列表的映射有向图取outgoers()中的边无向图取connectedEdges()中的边edges[id]边 id 到端点数组的映射有向图存[undefined, target]无向图存[source, target]。6.2 walk子游程subtour扩展核心的walk(v)函数见 hierholzer.mjs从顶点v出发沿着尚未使用的边不断前进把经过的节点 边交替压入subtour数组头部直到当前节点没有剩余邻接边为止形成一段闭合/终止的子游程。6.3 主循环拼接子游程subtour walk(startVertex); while (subtour.length ! 1) { if (nodes[subtour[0]].length 0) { // 当前顶点已无剩余边弹出“节点边”并入最终 trail trail.unshift(eles.getElementById(subtour.shift())); trail.unshift(eles.getElementById(subtour.shift())); } else { // 当前顶点还有剩余边从该顶点继续扩展子游程 subtour walk(subtour.shift()).concat(subtour); } }见 hierholzer.mjs。这是 Hierholzer 算法的经典实现反复提取子回路subtour并将其拼接到主路径中。6.4 最终校验遍历结束后再次检查所有节点的邻接边列表只要还有未使用的边就说明子图不连通、存在孤立边例如分离的环此时返回found: false见 hierholzer.mjs。只有全部边都被覆盖才设置result.found true并生成trail集合。七、测试验证仓库在 test/collection-hierholzer.mjs 中提供了两组针对同一张混合图的测试有向测试directed: true, root: #0期望找到欧拉回路且路径上的节点顺序为[0, 1, 2, 3, 4, 5, 6]测试中通过res.trail.stdFilter(isNode).map(ele2id)只提取节点 id 进行断言。无向测试directed: false, root: #0期望找到欧拉路径节点顺序为[0, 1, 6, 4, 3, 2, 5]。这两组用例的图包含 8 个节点与 16 条边含多重边如两条0→1、两条1→2等直观验证了同一张图在有向与无向两种模式下的判定与轨迹不同多重边平行边被正确计数并逐条经过found标志与trail的顺序与文档描述一致。测试文件中的ele2id与isNode辅助函数见 collection-hierholzer.mjs展示了如何从trail中提取节点序列进行断言这也是你自己使用trail时常用的处理方式。八、注意事项与边界情况root必须存在于调用集合中若传入选择器在集合中匹配不到元素this.filter(root)[0]为undefined再调用.id()会抛错请确保起点节点在子集中root与法定起点的冲突当图存在奇度/失衡节点时root必须与算法推导的起点一致否则返回found: false而非报错子图必须连通若调用集合中的边分布在多个连通分量中最终校验阶段会因存在未使用边而判定found: false自环与多重边自环在无向度计算中按 2 计数算法可以正确处理包含自环与平行边的图结果集合trail是新建的集合spawn对它的修改不会影响原图元素但高亮类、选中状态会作用于底层元素可用于可视化复杂度从实现看算法在构建邻接表时对每个节点的邻接边做filter删除操作整体适用于常规规模的图分析场景实际性能与图规模、边密度相关建议在较大图上实测验证。九、小结eles.hierholzer()是 cytoscape.js 集合算法库中一个实现完整、行为可预期的图论方法它以调用集合为子图边界通过度检查无向奇度判定 / 有向入出度判定快速预判欧拉图再以 Hierholzer 的子游程拼接策略构建有序的trail集合。文档、源码src/collection/algorithms/hierholzer.mjs与测试test/collection-hierholzer.mjs三者相互印证你可以放心地将它用于欧拉路径探测、图结构校验与可视化演示等任务。赞分享数据可视化【免费下载链接】cytoscape.jsGraph theory (network) library for visualisation and analysis项目地址https://gitcode.com/gh_mirrors/cy/cytoscape.js点击查看免费下载相关推荐如何快速掌握欧拉路径算法从有向图到无向图的完整指南如何快速掌握欧拉路径算法从有向图到无向图的完整指南 在图论算法中欧拉路径Eulerian Path是一个经典且实用的问题它指的是在图中找到一条能够恰好示例工程OI-wiki 图论专题欧拉图、欧拉回路与 Hierholzer 算法全解析OI wiki 图论专题欧拉图、欧拉回路与 Hierholzer 算法全解析 欧拉图是图论中一笔画问题的严格数学形式是否存在一条恰好经过每条边一次、且能文档知识库教育教程Interview_DS_Algo 图论专题实战欧拉路径与欧拉回路判定及 Hierholzer 算法全解析Interview_DS_Algo 图论专题实战欧拉路径与欧拉回路判定及 Hierholzer 算法全解析 本篇文章以 Graph/Euler https:/示例工程上一篇CleanRL SAC 运行时基准解析MuJoCo v4 连续控制任务的 SPS 吞吐实测与复现指南下一篇GPLv3许可下的开源美学Paper Theme Suite的版权与二次开发说明创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 cytoscape.js 中 Hierholzer 算法：求有向图与无向图的欧拉回路（Eulerian Trail）
数据可视化【免费下载链接】cytoscape.jsGraph theory (network) library for visualisation and analysis项目地址https://gitcode.com/gh_mirrors/cy/cytoscape.js点击查看免费下载导读本文围绕 cytoscape.js 集合方法eles.hierholzer()展开讲解如何利用 Hierholzer 算法在图中查找欧拉回路Eulerian circuit与欧拉路径Eulerian trail。该方法允许你限定在调用集合所包含的节点与边子集上运行算法并通过found与trail返回判定结果和按访问顺序排列的元素序列。读完本文你将掌握该方法的完整 API、选项语义、返回值结构以及底层判定欧拉图的实现原理和测试验证方式可直接在自己的图分析任务中使用。一、方法概述与适用场景eles.hierholzer()是 cytoscape.js 集合collection提供的图论算法之一用于执行Hierholzer 算法在图中寻找一条经过每条边恰好一次的路径trail。若路径首尾相接形成闭合回路则称为欧拉回路若只要求经过每条边恰好一次而不必闭合则称为欧拉路径。该方法的特点是只在调用集合的子图上运行。如 hierholzer.md 所述this function performs Hierholzers algorithm on only the subset of the graph in the calling collection也就是说只有集合内的节点和边参与计算集合外的元素被完全忽略既可以处理无向图也可以处理有向图既可以求闭合的欧拉回路也可以求首尾不同的欧拉路径取决于图本身是否满足相应条件。实际应用场景包括路径规划与遍历问题、图结构完整性校验判断一个网络是否可以一笔画、电路板布线、社交网络中的闭环检测等需要每条边恰好走一次的分析任务。二、返回值结构调用hierholzer()后返回一个对象结构如下{ found, /* true 或 false */ trail /* 欧拉路径/回路中的有序元素集合若找到 */ }字段说明字段类型含义foundboolean是否在指定子图中找到欧拉路径/回路。若子图不满足欧拉条件存在 2 个以上奇度节点、有向图入出度失衡、图不连通导致有边无法被覆盖等则为falsetrailCollection按访问顺序排列的元素集合节点与边交替出现节点 → 边 → 节点 → 边 → …以节点收尾仅在found为true时有效从源码看trail是通过this.spawn( trail, true )生成的一个新集合见 hierholzer.mjs因此你可以直接对trail继续使用集合 API例如选中、遍历、添加样式等。三、参数选项eles.hierholzer( options )接受一个配置对象源码中的默认值定义在 hierholzer.mjsconst hierholzerDefaults defaults({ root: undefined, directed: false });选项类型默认值说明rootstring选择器或单个元素集合undefined算法的起始节点。若不提供默认取调用集合中的第一个节点作为起点directedbooleanfalse是否按有向图处理。默认false即假设图为无向图几点关键语义对应 hierholzer.md 的 Regarding optional options 部分root 的两种传法传入字符串时会被当作选择器selector通过this.filter(root)[0].id()解析为具体节点 id传入元素对象时取root[0].id()。见 hierholzer.mjs默认起点若未提供root使用调用集合的第一个元素eles[0].id()作为起点见 hierholzer.mjs默认无向directed默认为false图按无向处理只有当图存在 2 个奇度节点时起点会被自动调整为其中一个奇度节点详见下文起点选择。此外源码还支持位置参数的旧式调用形式当options不是普通对象时会将arguments[0]、arguments[1]分别解析为root与directed见 hierholzer.mjs例如eles.hierholzer(#k, true)。四、算法核心欧拉图的判定条件Hierholzer 算法的第一步是判定子图是否可能存在欧拉路径/回路。源码依据图的有向性做了两套度检查4.1 无向图directed: false遍历集合中每个节点计算其度ele.degree(true)true表示包含自环。当且仅当奇度节点数量不超过 2时才可能存在欧拉路径let d ele.degree(true); if (d % 2) { if (!oddIn) oddIn id; else if (!oddOut) oddOut id; else dflag true; // 超过 2 个奇度节点不满足欧拉条件 }见 hierholzer.mjs。全部节点度为偶数 → 存在欧拉回路恰好 2 个节点度为奇数 → 存在欧拉路径且路径从其中一个奇度节点出发、终止于另一个超过 2 个奇度节点 →dflag置真直接返回found: false。4.2 有向图directed: true遍历每个节点计算d1 indegree - outdegree与d2 outdegree - indegreeif (d1 1) { // 入度比出度多 1 if (oddIn) dflag true; else oddIn id; } else if (d2 1) { // 出度比入度多 1 if (oddOut) dflag true; else oddOut id; } else if ((d2 1) || (d1 1)) { dflag true; // 差值大于 1不可能存在欧拉路径 }见 hierholzer.mjs。其理论依据是有向欧拉回路要求每个节点入度等于出度有向欧拉路径最多允许一个出度比入度多 1的起点和一个入度比出度多 1的终点任何差值超过 1 的节点都会使判定失败。关于度的实现细节集合的degree()/indegree()/outdegree()定义在 degree.mjs其中自环loop在degree()中按 2 计数在indegree()/outdegree()中分别按 1 计入includeLoops参数默认为true。4.3 起点startVertex的选择判定通过后源码按以下优先级确定起点见 hierholzer.mjs若存在奇度/失衡节点oddOut oddIn有向图要求显式提供的root必须是oddOut出度多的那个节点否则返回found: false无向图root必须是两个奇度节点之一否则返回found: false未提供root时自动取oddOut作为起点若所有节点度都平衡纯欧拉回路情形未提供root时取调用集合第一个节点的 id。也就是说用户提供的root如果与欧拉路径的法定起点冲突算法会直接判定found: false这是方法返回false的一种常见原因。五、示例完整可运行代码文档 hierholzer.md 给出的官方示例var hierholzer cy.elements().hierholzer({ root: #k, directed: true }); hierholzer.trail.select();下面是一个更完整的可运行版本包含图构建、调用与结果展示import cytoscape from cytoscape; const cy cytoscape({ container: document.getElementById(cy), elements: { nodes: [ { data: { id: a } }, { data: { id: b } }, { data: { id: c } }, { data: { id: d } } ], edges: [ { data: { id: e1, source: a, target: b } }, { data: { id: e2, source: b, target: c } }, { data: { id: e3, source: c, target: d } }, { data: { id: e4, source: d, target: a } } ] } }); // 在有向全图上寻找欧拉回路指定起点为 a const res cy.elements().hierholzer({ root: #a, directed: true }); if (res.found) { console.log(找到欧拉回路访问顺序); res.trail.forEach(ele { console.log(ele.isNode() ? 节点 ele.id() : 边 ele.id()); }); // 高亮整条路径 res.trail.select(); } else { console.log(该子图不存在欧拉回路/路径); }5.1 限定子集运行由于算法只作用于调用集合你可以先过滤再调用例如只考察一部分节点和边// 只考虑由节点 a、b 及其连边构成的子图 const subset cy.$(#a, #b).closedNeighborhood(); const res subset.hierholzer({ directed: false }); if (res.found) { res.trail.addClass(eulerian-trail); }5.2 利用返回结果做可视化trail是有序集合可配合动画演示遍历过程let idx 0; const eleIds res.trail.map(ele ele.id()); const timer setInterval(() { if (idx eleIds.length) { clearInterval(timer); return; } cy.getElementById(eleIds[idx]).addClass(visited); idx; }, 300);六、源码实现逐步剖析hierholzer方法定义在 src/collection/algorithms/hierholzer.mjs并通过 src/collection/algorithms/index.mjs 与其余算法一起挂载到集合原型上因此任何集合cy.elements()、cy.nodes()、过滤后的子集都可以调用。6.1 数据结构构建算法先建立两个索引结构见 hierholzer.mjsnodes[id]节点 id 到邻接边 id 列表的映射有向图取outgoers()中的边无向图取connectedEdges()中的边edges[id]边 id 到端点数组的映射有向图存[undefined, target]无向图存[source, target]。6.2 walk子游程subtour扩展核心的walk(v)函数见 hierholzer.mjs从顶点v出发沿着尚未使用的边不断前进把经过的节点 边交替压入subtour数组头部直到当前节点没有剩余邻接边为止形成一段闭合/终止的子游程。6.3 主循环拼接子游程subtour walk(startVertex); while (subtour.length ! 1) { if (nodes[subtour[0]].length 0) { // 当前顶点已无剩余边弹出“节点边”并入最终 trail trail.unshift(eles.getElementById(subtour.shift())); trail.unshift(eles.getElementById(subtour.shift())); } else { // 当前顶点还有剩余边从该顶点继续扩展子游程 subtour walk(subtour.shift()).concat(subtour); } }见 hierholzer.mjs。这是 Hierholzer 算法的经典实现反复提取子回路subtour并将其拼接到主路径中。6.4 最终校验遍历结束后再次检查所有节点的邻接边列表只要还有未使用的边就说明子图不连通、存在孤立边例如分离的环此时返回found: false见 hierholzer.mjs。只有全部边都被覆盖才设置result.found true并生成trail集合。七、测试验证仓库在 test/collection-hierholzer.mjs 中提供了两组针对同一张混合图的测试有向测试directed: true, root: #0期望找到欧拉回路且路径上的节点顺序为[0, 1, 2, 3, 4, 5, 6]测试中通过res.trail.stdFilter(isNode).map(ele2id)只提取节点 id 进行断言。无向测试directed: false, root: #0期望找到欧拉路径节点顺序为[0, 1, 6, 4, 3, 2, 5]。这两组用例的图包含 8 个节点与 16 条边含多重边如两条0→1、两条1→2等直观验证了同一张图在有向与无向两种模式下的判定与轨迹不同多重边平行边被正确计数并逐条经过found标志与trail的顺序与文档描述一致。测试文件中的ele2id与isNode辅助函数见 collection-hierholzer.mjs展示了如何从trail中提取节点序列进行断言这也是你自己使用trail时常用的处理方式。八、注意事项与边界情况root必须存在于调用集合中若传入选择器在集合中匹配不到元素this.filter(root)[0]为undefined再调用.id()会抛错请确保起点节点在子集中root与法定起点的冲突当图存在奇度/失衡节点时root必须与算法推导的起点一致否则返回found: false而非报错子图必须连通若调用集合中的边分布在多个连通分量中最终校验阶段会因存在未使用边而判定found: false自环与多重边自环在无向度计算中按 2 计数算法可以正确处理包含自环与平行边的图结果集合trail是新建的集合spawn对它的修改不会影响原图元素但高亮类、选中状态会作用于底层元素可用于可视化复杂度从实现看算法在构建邻接表时对每个节点的邻接边做filter删除操作整体适用于常规规模的图分析场景实际性能与图规模、边密度相关建议在较大图上实测验证。九、小结eles.hierholzer()是 cytoscape.js 集合算法库中一个实现完整、行为可预期的图论方法它以调用集合为子图边界通过度检查无向奇度判定 / 有向入出度判定快速预判欧拉图再以 Hierholzer 的子游程拼接策略构建有序的trail集合。文档、源码src/collection/algorithms/hierholzer.mjs与测试test/collection-hierholzer.mjs三者相互印证你可以放心地将它用于欧拉路径探测、图结构校验与可视化演示等任务。赞分享数据可视化【免费下载链接】cytoscape.jsGraph theory (network) library for visualisation and analysis项目地址https://gitcode.com/gh_mirrors/cy/cytoscape.js点击查看免费下载相关推荐如何快速掌握欧拉路径算法从有向图到无向图的完整指南如何快速掌握欧拉路径算法从有向图到无向图的完整指南 在图论算法中欧拉路径Eulerian Path是一个经典且实用的问题它指的是在图中找到一条能够恰好示例工程OI-wiki 图论专题欧拉图、欧拉回路与 Hierholzer 算法全解析OI wiki 图论专题欧拉图、欧拉回路与 Hierholzer 算法全解析 欧拉图是图论中一笔画问题的严格数学形式是否存在一条恰好经过每条边一次、且能文档知识库教育教程Interview_DS_Algo 图论专题实战欧拉路径与欧拉回路判定及 Hierholzer 算法全解析Interview_DS_Algo 图论专题实战欧拉路径与欧拉回路判定及 Hierholzer 算法全解析 本篇文章以 Graph/Euler https:/示例工程上一篇CleanRL SAC 运行时基准解析MuJoCo v4 连续控制任务的 SPS 吞吐实测与复现指南下一篇GPLv3许可下的开源美学Paper Theme Suite的版权与二次开发说明创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考