是什么使广度优先搜索算法比深度优先搜索慢（均在下面显示）？

Question

我正在使用DFS和BFS解决迷宫问题中的鼠标，在该问题中，允许鼠标向右或向上移动。由于分支因子只有两个，迷宫是5x5矩阵，我希望BFS比DFS更快，但事实却恰恰相反。DFS需要6793300纳秒BFS需要26359600纳秒

什么可能解释这种差异？ BFS中使用的其他数据结构会导致这种开销吗？

DFS：

 int performMazeSearchDFS(int i, int j, int[][] maze, int destI, int destJ, int size, int moveCount) 
 {
    int result = moveCount;
    if (i == destI && j == destJ) {
      return moveCount;
    }

    if(j+1 < size && maze[i][j+1] != 1) {
        result = performMazeSearchDFS(i, j + 1, maze, destI, destJ, size, moveCount+1);
     if(result > moveCount) {
            return result;
        }
    }

    if (i-1 >= 0 && maze[i-1][j] != 1) { // no improvement from previous moves
        result = performMazeSearchDFS(i - 1, j, maze, destI, destJ, size, moveCount+1);
        if(result > moveCount) {
            return result;
         }
    }
   moveCount = moveCount -1;
   return moveCount;
}

BFS：

 private class Coordinates{
    private int i;
    private int j;
    public Coordinates(int iCord, int jCord){
        i= iCord;
        j=jCord;
    }
    public int getI(){return i;}
    public int getJ(){return j;}
    public boolean equals(Object toCompare){
        if(toCompare instanceof  Coordinates ){
            Coordinates coOrdX  = (Coordinates)toCompare;
            if(this.i == coOrdX.getI() && this.j == coOrdX.getJ()){
                return true;
            }
        }
        return false;
    }
}

private class History{
    private Coordinates parent;
    private Coordinates current;
    public History(Coordinates par, Coordinates curr){
        parent = par;
        current = curr;
    }
    public Coordinates getParent(){return parent;}
    public Coordinates getCurrent(){return current;}
}

public boolean performMazeSearchBFS(int i, int j, int[][] maze, int destI, int destJ, int size) {
    LinkedList<History>  nodeQ = new LinkedList<>();
    HashMap<Coordinates,Boolean> visitedNode = new HashMap<>();
    boolean found = false;
    nodeQ.add(new History(new Coordinates(-1,-1),(new Coordinates(i,j))));
    while(!nodeQ.isEmpty()) {
      History currNode = nodeQ.poll();
      visitedNode.put(new Coordinates(currNode.getCurrent().getI(), 
      currNode.getCurrent().getJ()),true);
      int m = currNode.current.getI();
      int n = currNode.current.getJ();
      if(currNode.current.getI() == destI && currNode.current.getJ() == destJ) {
        found = true;
        break;
      }
      if (m - 1 >= 0 && maze[m - 1][n] == 0 
          && !visitedNode.containsKey(new Coordinates(m - 1, n))) {
      if (m - 1 >= 0 && maze[m - 1][n] == 0 ) {
          nodeQ.add(new History(new Coordinates(m, n), new Coordinates(m - 1, n)));
      }
      if (n + 1 < size && maze[m][n] == 0 
         && !visitedNode.containsKey(new Coordinates(m, n + 1))) {
         nodeQ.add(new History(new Coordinates(m, n), new Coordinates(m, n + 1)));
      }
 }
      return found;
 }

Answer 1

速度实际上取决于您要搜索的内容和图形的严格程度。如果搜索图形中的所有路径，则速度应相似。如果搜索靠近根的节点，或者需要最短路径，则BFS可能会更快。如果搜索图中深处，远离根的节点且不需要最短路径，则DFS可能会更快。