java - Java中查找包含循环的图中一定距离内的所有边

Question

我有一个Node的图表通过 Edge 连接的对象需要通过以下方式探索的对象:

我的起始位置为 Edge source并需要找到所有其他Edge对象，使得沿路径经过的边的长度总和不超过 MAX_RANGE以及在每个 Edge 执行一些操作满足条件。

我对这个问题的解决方案是递归地分支，跟踪我所走的距离( Edge#getEdgeConnections() 返回一个 ArrayList<Edge> ，其中包含连接到它所调用的 Edge 的所有 Edge 对象):

private final ArrayList<Edge> occupiedEdges = new ArrayList<>();

private void doStuffWithinRangeOf(Edge source) {
    doStuffAtEdge(source);
    for (Edge connection : source.getEdgeConnections()) {
        doStuffAtBranch(connection, source, 0);
    }
}

private void doStuffAtBranch(Edge edge, Edge source, double distance) {
    double newDistance = distance + edge.getLength();
    doStuffAtEdge(edge);
    for (Edge connection : edge.getEdgeConnections()) {
        if (!connection.equals(source) 
                && !isOccupied(connection) 
                && (newDistance < MAX_AP_RANGE)) {
            doStuffAtBranch(connection, edge, newDistance);
        }
    }
}

private void duStuffAtEdge(Edge edge) {
    occupiedEdges.add(edge);
    ... // Some amount of work that mustn't be done more than once per Edge
}

private boolean isOccupied(Edge edge) {
    return occupiedEdges.contains(edge);
}

现在，这应该可以正常工作，除了一件事 - 该图包含几种循环情况。

因此，如果递归算法从较长的路径开始循环，则在选择较短的路径时可能会错过指定范围内的一些边缘，如下所示

  ----------- C ---- D - E    // The algorithm explores AB, BC, CD and makes them occupied
  |           |
  B           |               // DE is too far along this path, and isn't occupied
  |           |
  ------------A               // When the algorithm explores along AC, it finds that CD 
                              // is already occupied and stops
                              // even though DE is really within range

现在，我想到的解决方案是采用不同的搜索模式，其中我将有一个“边界”边缘的列表(或 map )，并按距离增加的顺序探索它们(每次向该边界添加新的边缘)探索边缘的时间)。

可能涉及到大量的边，所以我不想每次都循环遍历整个列表来找到距离源最近的边。

是否有某种类型的集合能够以这种方式自动保持顺序，并且能够高效地添加/删除元素？

SortedMap 是我正在寻找的吗？在这种情况下我将如何使用它？

编辑: 感谢所有回复者。我最终使用了 PriorityQueue带有包装类(有关详细信息和代码，请参阅 my answer)。

Answer 1

我建议调整您的算法，而不是使用其他数据结构:

您已经实现了某种 depth-first-search浏览你的图表。如果您使用某种breadth-first-search相反，您可以在到达指定范围并访问范围内的每个边缘一次时停止(通过使用您已经实现的 isOccupied 逻辑)。