是否有用于图形操作和算法的JavaScript库？

Question

我需要的是纯数学图的JavaScript实现.要明确我不是指像sigma.js或d3.js这样的图形可视化库.

我正在寻找的库将实现以下功能:

• 创建有向和无向图形对象
• 创建加权和未加权的graps对象
• 向图表添加/删除顶点和边缘
• 向顶点和边添加标签(即附加元数据)
• 实现基本类似图搜索和遍历算法,深度优先搜索,广度优先搜索,Dijkstra算法,A*和他人.

有谁知道一个人是否已经存在？

Answer 1

现在有一个库:graphlib

Graphlib是一个JavaScript库,为无向和有向多图提供数据结构以及可与它们一起使用的算法.

实现:

• 有向图和无向图(A - > B表示B - > A)
• 多图(A - > B中多个不同的命名边)
• 复合图(节点可以有子元素,形成"子图")
• Dijkstra算法(最短路径)
• Floyd-Warshall算法(支持负权重的最短路径)
• Prim的算法(最小生成树)
• Tarjan的算法(强连接组件)
• 拓扑排序(有向无环图的依赖排序)
• 前后遍历(每个节点上的回调)
• 查找所有周期并测试图表是否为非循环
• 查找所有连接的组件

支持NPM,Bower和浏览器,MIT许可证.

Answer 2

当前维护的已弃用的替代方案graphlib（也包括 Typescript 支持）是graphology。

当与一些扩展（例如graphology-shortest-path.

Answer 3

几个月前，我创建了一个存储库，其中包含 JavaScript 中不同 CS 算法的实现。带图的算法也很少。我计划扩展它（生成树，启发式算法可能是彩色图），但从那时起我认为仍然很少有算法可以帮助你。