moon_toolkit

MoonBit 通用图算法工具箱 🌙

提供从基础图数据模型到高级图算法的完整能力，面向编译器构建、包依赖解析、路径规划、网络分析、游戏 AI、状态机处理等场景。

功能特性

图数据模型

• 泛型有向图 Graph[N, E]
• 节点/边增删改查
• 邻接表存储，支持邻居快速遍历

遍历

• BFS 广度优先遍历（含最短路径还原）
• DFS 深度优先遍历（迭代式，含后序遍历）

最短路径

• Dijkstra 算法（非负权图）

数据结构

• Union-Find（并查集，用于 MST 和连通性）
• MinHeap（最小堆，优先队列）

即将支持

• A* 启发式搜索
• Bellman-Ford（含负环检测）
• Prim / Kruskal（最小生成树）
• 拓扑排序与环检测
• Tarjan SCC / Kosaraju（强连通分量）
• Hopcroft-Karp（二分图最大匹配）
• Edmonds-Karp / Dinic（网络流）
• DOT 格式导出（Graphviz 兼容）

安装

# 从 mooncakes.io 安装（待发布）
moon add oldpig/moon_toolkit

# 或本地开发
git clone https://github.com/oldpig/moon_toolkit.git
cd moon_toolkit
moon build

使用示例

// 创建一个图
let g = Graph::new[@int, @int]()
let a = g.add_node(0)
let b = g.add_node(1)
let c = g.add_node(2)
g.add_edge(a, b, 1)
g.add_edge(b, c, 2)

// BFS 遍历
let order = bfs(g, a)
// order = [0, 1, 2]

// Dijkstra 最短路
let (dist, prev) = dijkstra(g, a)
// dist = [0, 1, 3]

开发

# 构建
moon build

# 运行测试
moon test

# 检查
moon check

项目状态

🚧 开发中 — 核心数据结构和基础算法已实现，更多算法持续添加中。

• 图数据模型 Graph[N, E]
• BFS / DFS 遍历
• Dijkstra 最短路
• Union-Find 并查集
• MinHeap 最小堆
• A* 启发式搜索
• Bellman-Ford
• Prim / Kruskal MST
• 拓扑排序
• Tarjan SCC
• 网络流

许可证

Apache-2.0

参赛信息

本项目参加 2026 MoonBit 国产基础软件开源大赛。

• 参赛者：徐健凯 (@oldpig)
• GitHub：https://github.com/oldpig/moon_toolkit
• Gitlink：https://gitlink.org.cn/oldpig/moon_toolkit