图形实现 Android

Question

我需要在内存中有一个图形（或等效的数据结构），其中应包含一组ID（数字），并且要求是该图形（或某个数据结构）可能有大约10000个节点。以下为情景说明。我应该选择任何API还是自己的自定义实现。请考虑内存和速度（请随时告诉我任何建议）。

例如：

每次都会得到所有叶子节点。即，在下面的图中，我只需要6、7、8。

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

对不起，再次强调，请考虑内存和速度，因为它应该在Android上运行。

谢谢

- Sree Aurovindh

Answer 1

您可能还想查看以下帖子：Java 中是否有面向有向无环图 (DAG) 的数据类型，应该使用它吗？ 您需要的是一个 DAG (有向无环图) 库。

- Dan

---

谢谢。我会尝试实现相同的功能。 - Sree Aurovindh

Answer 2

你正在考虑哪种API实现？我想不出任何适合你需求的Java集合。

如果你自己实现，可以在构建和修改树的过程中跟踪叶子节点，这样每当你需要获取叶子节点时，你已经有了它们的列表。如果你使用HashSet来跟踪叶子节点，我认为你应该能够执行所有树操作，而不会因为HashSet而产生额外的时间复杂度开销。

当然，你将使用额外的内存，但这取决于你是否认为这将是一个问题。我认为即使有10k个可能的叶子节点并在Android上运行，也不应该成为任何问题。

- Alex Florescu

---

谢谢。我想我应该将你的解决方案添加到Dan的解决方案中，以得出新的东西。会告诉你我的结果。 - Sree Aurovindh