为图实现 BFS 搜索方法

Question

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

    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 可以递归实现，但迭代方法更适合此任务。

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

在每次调用 recursiveBFS() 时，queue 开头的 node 将被删除。如果队列为空，则意味着 start-node 和 end-node 未连接。

这就是递归实现的样子：

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 我提取了用于从 start-node 到 恢复路径的逻辑end-node从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();
}

建议：

我想指出的最重要的是你的 graph 的整体设计。在遍历图表时，您严重依赖 Map<T, List<Edge<T>>> graphRep，edges 没有它就无能为力。您可能会考虑优化图表，使其元素更多 self-contained。首先，在我看来，图的 edge 必须有 two 引用，因为根据定义它意味着表示连接 在图的两个顶点之间。如果你添加一个 Vertex class 到你的 graph 然后将包含引用一个 边集合 然后你可以实现图遍历算法仅使用 edges 和 vertexes 而无需依赖 graphRep.
不要将对象与 == 进行比较，而是使用 equals() 方法。
避免 one-letter 变量，例如 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 我们不需要任何特定于 edges 的信息（因为 vertex（节点）可以存储关于 adjusent vertexes 的数据）这些算法只能使用 vertecies 来实现.

为图实现 BFS 搜索方法

Implementing a BFS-search method for a graph

java

graph

depth-first-search

breadth-first-search