java - 实现图的 BFS 搜索方法

Question

我正在实现我自己的图形类。我的无向图由一个映射表示，该映射将每个节点映射到存储其具有的边的列表。

    private Map<T, List<Edge<T>>> graphRep = new HashMap<>();

    private static class Edge<T> {
        int cost;
        T node;
        public Edge(T n, int w) {
            node = n;
            cost = w;
        }

我已经为我的图创建了一个递归深度优先遍历方法，它利用映射来存储起始节点到搜索节点之间的路径。它通过将起始节点到结束节点之间的路径上的每个节点映射到下一个节点来实现。

    @Override
    public List<T> depthFirstSearch(T start, T end) {
        Set<T> visited = new HashSet<T>();
        Map<T,T> path = new HashMap<>();
        recursiveDFS(start, end, visited,path);
        List<T> myList = new ArrayList<T>();
        T current = end;
        myList.add(current);
        while (current != start) {
            myList.add(path.get(current));
            current = path.get(current);
        }
        System.out.println(path);
        System.out.println(myList);
        Collections.reverse(myList);
        return myList;
    }

    private void recursiveDFS (T node, T end, Set<T> visited, Map<T, T> path) {
        // uppdatera path och visited
        visited.add(node);
        for (Edge<T> e : graphRep.get(node)) {
            if (e.node == end) {
                path.put(e.node, node);
                return;
            }
            if (!visited.contains(e.node)){
                path.put(e.node, node);
                recursiveDFS(e.node, end, visited, path);
            }
        }
    }

我相信我可以使用与深度优先搜索基本相同的代码进行广度优先搜索，只是不是按深度遍历节点，而是按广度遍历节点，这就是我陷入困境的地方。我完全不知道如何做到这一点。

    @Override
    public List<T> breadthFirstSearch(T start, T end) {

        Set<T> visited = new HashSet<T>();
        Map<T,T> path = new HashMap<>();
        recursiveBFS(start, end, visited,path);
        List<T> myList = new ArrayList<T>();
        T current = end;
        myList.add(current);
        while (current != start) {
            myList.add(path.get(current));
            current = path.get(current);
        }
        System.out.println(path);
        System.out.println(myList);
        Collections.reverse(myList);
        return myList;
    }

    public void recursiveBFS (T node, T end, Set<T> visited, Map<T, T> path) {

        visited.add(node);
        for (Edge<T> e : graphRep.get(node)) {
            if (e.node == end) {
                path.put(e.node, node);
                return;
            }
            if (!visited.contains(node)) {
              //Here's where I'm stuck. I have no idea how to traverse the graph by breadth
            }
        }
    }

如何完成我的广度优先遍历方法？

Answer 1

BFS 需要一个允许按照访问顺序检索节点的容器。它无法通过Map来实现。 。您需要一个Queue为此目的(take a look carefully at the description of this algorithm)。

注意，虽然 BFS 可以递归实现，但迭代方法更适合此任务。

首先，您需要创建一个队列并在其中添加一个起始节点。然后队列将作为参数传递给 recursiveBFS() .

每次调用 recursiveBFS() 时队列开头的节点将被删除。如果队列为空，则意味着起始节点和结束节点未连接。

这就是递归实现的样子:

public List<T> breadthFirstSearch(T start, T end) {
    Map<T, T> paths = new HashMap<>();
    Queue<T> queue = new ArrayDeque<>();
    queue.add(start);
    recursiveBFS(end, new HashSet<>(), queue, paths);

    return getPath(start, end, paths);
}

public void recursiveBFS(T end, Set<T> visited, Queue<T> queue,  Map<T, T> paths) {
    if (queue.isEmpty()) { // start-node and end-node are not connected
        return;
    }

    T parentNode = queue.remove();
    visited.add(parentNode);
    for (Edge<T> edge : graphRep.get(parentNode)) { // avoid one-letter variables like "e" instead of edge
        if (visited.contains(parentNode)) {
            continue;
        }
        paths.put(edge.node, parentNode);
        // end node was found
        if (edge.node.equals(end)) { // don't compare object with "=="
            return;
        }
        recursiveBFS(end, visited, queue, paths); // this line was missing
    }
}

为了使该解决方案遵守 Single responsibility principle我从 breadthFirstSearch() 中提取了恢复从 start-node 到 end-node 的路径的逻辑。进入单独的方法。

public List<T> getPath(T start, T end,  Map<T, T> paths) {
    List<T> path = new ArrayList<T>();
    T current = end;
    path.add(current);
    while (current != start && current != null) { // if there's no path from start to end current eventually will become null
        path.add(paths.get(current));
        current = paths.get(current);
    }
    System.out.println(path);
    Collections.reverse(path);
    return current != null ? path : Collections.emptyList();
}

建议:

• 我想指出的最重要的是图表的整体设计。。在遍历图表时，您严重依赖 Map<T, List<Edge<T>>> graphRep ，边缘没有它就束手无策。您可能会考虑改进图表，使其元素更加独立。首先，在我看来，图的边必须有两个引用，因为根据定义，它意味着表示两个顶点之间的连接 图表。如果你添加 Vertex类到您的图，然后将包含引用边集合，然后您可以仅使用边和顶点实现图遍历算法em> 无需依赖graphRep .
• 不要将对象与 == 进行比较，使用equals()方法代替。
• 避免单字母变量，如 e .
• 不要命名为 myList ，但尝试想出能够解释该变量用途的名称(例如 path )。

---

更新

下面是BFS的迭代实现:

public List<T> breadthFirstSearch(T start, T end) {
    Map<T, T> paths = new HashMap<>();
    Set<T> visited = new HashSet<>();
    Queue<T> queue = new ArrayDeque<>();
    queue.add(start);
    visited.add(start);
    boolean isFound = false;
    while (!isFound && !queue.isEmpty()) {
        T parentNode = queue.remove();
        for (Edge<T> edge : graphRep.get(parentNode)) {
            if (!visited.add(edge.node)) {
                continue;
            }
            paths.put(edge.node, parentNode);
            // end node was found
            if (edge.node.equals(end)) {
                isFound = true;
                break;
            }
        }
    }
    return getPath(start, end, paths);
}

如果您考虑上面的建议，迭代解决方案会更清晰。由于对于BFS以及DFS，我们不需要任何特定于边的信息(因为顶点 (节点)可以存储有关调整顶点的数据)这些算法只能使用顶点来实现。