将广度优先搜索转换为深度优先使用Java搜索

自从我与Java打交道以来，这已经很长时间了，所以这可能看起来像一个奇怪的问题。目前，我在StackOverflow上找到了这个广度优先搜索代码，我在最后修改了它，但是我会在这里发布原始代码。将广度优先搜索转换为深度优先使用Java搜索

public List<Node> getDirections(Node start, Node finish){ 
    List<Node> directions = new LinkedList<Node>(); 
    Queue<Node> q = new LinkedList<Node>(); 
    Node current = start; 
    q.add(current); 
    while(!q.isEmpty()){ 
     current = q.remove(); 
     directions.add(current); 
     if (current.equals(finish)){ 
      break; 
     }else{ 
      for(Node node : current.getOutNodes()){ 
       if(!q.contains(node)){ 
         q.add(node); 
       } 
      } 
     } 
    } 
    if (!current.equals(finish)){ 
     System.out.println("can't reach destination"); 
} 
return directions; 
}

我所知道的其他深度优先搜索算法在那里，但我还被告知其可能转换广度优先搜索，深度优先搜索很容易，我会更好地理解它，如果它做这个代码而不是2个完全不同的代码。

我该如何改变这是深度优先搜索？

来源

2011-10-13 Thu 01 Jan 1970 000000 GMT

你有没有试过把它自己转换成DFS？如果是这样，什么不起作用？ – MAK

只是一个提示：我记得从前一段时间，如果你以这种方式编写算法，只需在LIFO和FIFO数据结构（如堆栈或队列）之间切换，就可以在DFS和BFS之间切换。 –

我得到它沿着左侧旅行，但那是一些凌乱的hacky代码，（通过编辑for循环中的代码）它有很多nullpointerexceptions和headbanging过去的年龄 –

你必须用q.add(0, node)（在开始处添加）替换q.add(node)（它在列表的末尾加上）。基本上，使用stack而不是queue。

很明显，您必须使用List接口而不是Queue接口来访问LinkedList。

来源

2011-10-13 19:38:54 millimoose

Deque会比List更好。 – Daniel

我使用'List'作为'removeAll（）'和'addAll（）'，并且在深入代码块嵌套的情况下移除了for循环。 – millimoose

Deque<Node> q = new LinkedList<Node>();

并使用pop和push代替remove和add

从同一侧基本上除去所添加（正常remove和add是LIFO队列基OPS）深度首先使用FIFO堆栈

和其他搜索算法基本相同，但使用不同类型的队列（例如，热切搜索使用最简单的下一步）

来源

2011-10-13 19:40:31

更换Queue和LinkedList与Stack，add与push，并remove与pop

来源

2011-10-13 19:44:24 Jagat

深度优先和广度拳头之间的主要区别是在你探索你的“前沿”的节点（节点你”的列表中的顺序还没有探索）。

如果您将当前节点的传出节点添加到该列表的末尾，您将在“级别”（为了简化目的，将其想象为树）中测试每种可能性，然后再转到下一个级别，所以你有一个广度优先搜索。

另一方面，如果您在先前添加的节点（属于树的“上部”级别）之前探究新添加的节点（来自当前位置的传出节点），则您将首先探索树的深度。

就数据结构而言，你需要一个Stack而不是Queue，但我认为这个解释可能会派上用场。

来源

2011-10-13 19:47:05 pcalcao

将广度优先搜索转换为深度优先使用Java搜索

回答

相关问题