android - 图实现 Android

Question

我需要在内存中有一个图形（或一些等效的数据结构），它应该保存一组 IDS（数字），并且要求图形（或一些数据结构）可能有大约 10000 个节点。下面解释了场景。我应该选择任何 API 还是我自己的自定义实现。请考虑内存和速度（请随时告诉我任何建议。）

例如：

我会在每个实例中获取所有叶节点。即在下图中，我只需要 6、7、8。

如果程序从图中删除 6，则输出将为 4,5,7,8

抱歉再次强调。请考虑内存和速度，因为它应该在 android 上运行。

谢谢

Answer 1

您可能还想看看以下帖子：Java 中是否存在有向无环图 (DAG) 数据类型，我应该使用它吗？

你想要的是一个 DAG（有向 Acyclig Graph）库。

Answer 2

你在考虑什么 API 实现？我想不出任何适合您需要的 Java 集合。

如果您只是实现自己的，则可以在构建和修改树时跟踪叶子，因此每当您需要获取叶子时，您已经有了它们的列表。如果您使用 aa HashSet 来跟踪叶子，我认为您应该能够执行所有树操作而不会因为 HashSet 而导致额外的时间复杂度损失。

当然，您将使用额外的内存，但由您决定这是否会成为问题。我会说即使有 10k 可能的叶子并在 android 上运行，也不应该有任何问题。