java - 高效实现广度优先算法的动态队列

Question

我正在构建一个广度优先图形搜索算法，用于搜索伦敦地铁。

我已经弄清楚了算法，但您可能很清楚，该算法需要一个队列 ADS 来跟踪所有需要搜索的边缘（以正确的顺序）。

我一直在阅读有关管理队列和大量或大量排队项目（边缘）的效率问题。

谁能告诉我如何实现一个基于 Java ArrayList 的队列，它可以跟踪头部和尾部，并在内存增长时有效地管理内存？

任何提示/指针非常感谢！

Answer 1

我认为您的问题与该主题密切相关：Java 中的广度优先搜索

除非您有充分的理由，否则不要使用 ArrayList 。Java 已经提供了一组很棒的队列实现——有关详细信息，请参阅Queue接口。

在您的情况下，选择LinkedList作为您的队列实现可能就足够了。另请参阅http://www.codeproject.com/KB/java/BFSDFS.aspx，了解使用 LinkedList 作为队列的广度优先搜索实现的简单示例。

Answer 2

请记住，您将需要一个快速测试来查看您的对象是否已经在队列中。既不ArrayList也不Queue提供此功能（他们的contains检查是O(n)）。如果您可以通过添加一个额外的字段来修改您正在处理的对象，那么这很容易。如果没有，您将需要保持某种快速Set（HashSet可能是a）来跟踪队列中的对象。