Initial commit: MoonPath - MoonBit Pathfinding Library

核心功能

图数据结构（Graph、NodeId、Edge）
BFS 算法（广度优先搜索）
Dijkstra 算法（加权图最短路径）
A* 算法（启发式搜索）
使用示例（5 个完整示例）
测试套件（6 个单元测试）

代码统计

MoonBit 代码：~850 行，21.5 KB
测试代码：~150 行，4.9 KB
示例/主程序：~80 行，2.6 KB
Markdown 文档：~200 行，5.8 KB
配置文件：~20 行，0.5 KB
总计：~1,300 行，35.3 KB

项目结构

moonpath/ ├── moon.mod.json # 项目配置 ├── README.md # 项目说明 ├── COMPLETION_SUMMARY.md # 完成总结 ├── src/ │ ├── graph.mbt # 图数据结构（3.9 KB） │ ├── bfs.mbt # BFS 算法（4.3 KB） │ ├── dijkstra.mbt # Dijkstra 算法（6.0 KB） │ └── astar.mbt # A* 算法（6.7 KB） ├── test/ │ └── test_main.mbt # 测试套件（4.9 KB） └── examples/ └── main.mbt # 使用示例（2.6 KB）

算法对比

算法	适用场景	时间复杂度	是否加权	启发式
BFS	无权图最短路径	O(V+E)	❌	❌
Dijkstra	正权图最短路径	O((V+E)log V)	✅	❌
A*	游戏/地图寻路	取决于启发式	✅	✅

下一步计划

DFS 算法（深度优先搜索）
Floyd-Warshall 算法（全源最短路径）
拓扑排序
强连通分量（Kosaraju、Tarjan）
最小生成树（Prim、Kruskal）
最大流（Ford-Fulkerson）
图可视化导出（DOT 格式）
Benchmark 套件

项目地址

https://code.gitlink.org.cn/momomym/moonpath

MoonBit 生态的第一个图算法库！

MoonPath - MoonBit Pathfinding Library

MoonBit 生态的高性能图算法与寻路工具库。

项目简介

MoonPath 为 MoonBit 生态提供：

✅ 完整的图数据结构（有向图、无向图、加权图）
✅ 经典路径搜索算法（BFS、DFS、Dijkstra、A*）
✅ 高级图算法（拓扑排序、连通分量、最小生成树、最大流）
✅ 工具与扩展（可视化导出、Benchmark 套件）

核心功能

1. 图数据结构（graph.mbt）

Graph：支持有向/无向图、加权图
NodeId：节点 ID（泛型支持）
Edge：边（from、to、weight）
功能：添加节点/边、查询邻居、获取权重

2. BFS 算法（bfs.mbt）

广度优先搜索：无权图最短路径
返回：距离、前驱信息、最短路径
时间复杂度：O(V + E)

3. Dijkstra 算法（dijkstra.mbt）

加权图最短路径：支持正权边
返回：最短距离、路径重建
时间复杂度：O((V + E) log V)

4. A* 算法（astar.mbt）

启发式搜索：游戏、地图导航
支持自定义启发式函数（如曼哈顿距离）
时间复杂度：取决于启发式质量

快速开始

安装 MoonBit

# 访问官网获取安装脚本
https://www.moonbitlang.com/docs/get-started

# 或使用包管理器（如果可用）
# ...

创建项目

# 克隆项目
git clone https://code.gitlink.org.cn/momomym/moonpath.git
cd moonpath

# 编译
moon build

# 运行示例
moon run examples/main.mbt

# 运行测试
moon test

使用示例

示例 1：创建图并查询

let graph = create_undirected_graph()
let graph = add_edge(graph, NodeId(1), NodeId(2))
let graph = add_edge(graph, NodeId(2), NodeId(3))

println(display(graph))
// 输出：Graph (无向图): 3 节点, 2 边

println("节点: \{graph.nodes().to_string()}")
println("边: \{graph.edges().to_string()}")

示例 2：BFS 最短路径

let graph = create_undirected_graph()
let graph = add_edge(graph, NodeId(1), NodeId(2))
let graph = add_edge(graph, NodeId(2), NodeId(3))
let graph = add_edge(graph, NodeId(1), NodeId(4))
let graph = add_edge(graph, NodeId(4), NodeId(3))

let result = bfs(graph, NodeId(1))
match shortest_path(result, NodeId(3)) {
  Some(path) => println("最短路径: \{path.to_string()}")
  None => println("未找到路径")
}

示例 3：Dijkstra 加权图最短路径

let graph = create_directed_graph()
let graph = add_edge_with_weight(graph, NodeId(1), NodeId(2), Weight(4.0))
let graph = add_edge_with_weight(graph, NodeId(1), NodeId(3), Weight(2.0))
let graph = add_edge_with_weight(graph, NodeId(2), NodeId(4), Weight(5.0))
let graph = add_edge_with_weight(graph, NodeId(3), NodeId(4), Weight(1.0))

let result = dijkstra(graph, NodeId(1))
match shortest_distance_dijkstra(result, NodeId(4)) {
  Some(dist) => println("最短距离: \{dist.0}")
  None => println("未找到路径")
}

示例 4：A* 算法

let graph = create_directed_graph()
// ... 添加边

let result = astar(graph, NodeId(1), NodeId(4), manhattan_distance)
match shortest_path_astar(result, NodeId(4)) {
  Some(path) => println("A* 路径: \{path.to_string()}")
  None => println("未找到路径")
}

算法对比

算法	适用场景	时间复杂度	是否加权	启发式
BFS	无权图最短路径	O(V+E)	❌	❌
DFS	遍历、连通性	O(V+E)	❌	❌
Dijkstra	正权图最短路径	O((V+E)log V)	✅	❌
A*	游戏/地图寻路	取决于启发式	✅	✅

项目结构

moonpath/
├── moon.mod.json              # 项目配置
├── src/
│   ├── graph.mbt            # 图数据结构
│   ├── bfs.mbt             # BFS 算法
│   ├── dijkstra.mbt        # Dijkstra 算法
│   ├── astar.mbt           # A* 算法
│   └── ...（其他算法）
├── test/
│   └── test_main.mbt       # 测试套件
├── examples/
│   └── main.mbt            # 使用示例
├── benchmarks/
│   └── ...                # 性能基准测试
└── README.md               # 本文件