实现图的 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（仔细查看说明这个算法的）。

注意，虽然 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责任原则我从breadthFirstSearch() 到单独的方法中。

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>> 等元素。 graphRep、edges 没有它就束手无策。您可能会考虑改进图表，使其元素更加独立。首先，在我看来，图的边必须有两个引用，因为根据定义，它意味着表示两个顶点之间的连接 图表。如果您将 Vertex 类添加到您的图，那么将包含引用边的集合，那么您可以仅使用实现图遍历算法>边和顶点，无需依赖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，我们不需要任何特定于边的信息（因为顶点 （节点）可以存储有关调整顶点的数据）这些算法只能使用顶点来实现。