从一个节点到另一个节点的广度优先搜索

Question

我正在实现我自己的图表 class，我目前正在制作我自己的 BFS 搜索方法。现在它从一个根顶点遍历所有顶点。

public List<T> breadthFirstSearch(T start, T end) {
    List<T> visited = new ArrayList<T>();
    Queue<T> path = new LinkedList<T>();
    visited.add(start);
    path.add(start);
    while (!path.isEmpty()){
        T currentNode = path.poll();
        for (Edge<T> edge: graphRep.get(currentNode)) {
            if (!visited.contains(edge.node)) {
                visited.add(edge.node);
                path.add(edge.node);
            }
        }
    }
    System.out.println(visited);
    return visited;
}

我想做的是找到从顶点开始到顶点结束的路径，但现在它找到了开始到所有节点之间的路径。如何更改我的代码，使其只查找从开始到结束之间的路径？

Answer 1

你的解决方案有几个错误：

你没有检查是否找到目标节点；
从起始节点无法到达终点的情况不在您的解决方案中；
列表visited将包含所有访问过的节点序列，但不包含从起始节点到结束节点的路径；
方法 contains() 成本 O(n) 对于列表，您肯定必须为此目的使用 HashSet；
ArrayDeque 将比 LinkedList 表现更好（从技术上讲这不是错误而是强烈推荐）。

因此，要修复您的代码，您需要添加一个检查 node 是否指向 current edge 是等于到结束节点和一个布尔标志到break循环（无需进行更多迭代）。

在下面的代码中 HashMap paths 用于两个目的：

跟踪每个访问过的节点的父节点，以恢复从头到尾的路径；
检查是否已经访问了一个新节点。

方法 getPath() 将 return 列出表示从头到尾的直接路径的节点，如果该路径不存在则为空列表。

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

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();
}

从一个节点到另一个节点的广度优先搜索

Breadth-first search from one node to another

java

graph

breadth-first-search

depth-first-search