背景:想象一下,我有一个小机器人.我把这个机器人放在地图(图形)中的某个节点上.机器人可以调用giveMeMapCopy()方法来获取他所坐的整个地图的副本.我想给我的小机器人一个函数,通过该函数,他可以使用广度优先遍历来查找到Exit节点的最短路径.以下是此类地图的示例:
我在YouTube上观看了关于如何对图表进行广度优先遍历的视频,因此我很清楚需要做些什么.问题是,我发现很难让我的逻辑递归.这是我的代码:
public class Robot
{
// fields required for traversal
private Queue<ArrayList<String>> queue;
private ArrayList<ArrayList<String>> result;
private String workingNode;
private ArrayList<String> routeSoFar;
private Queue<String> knownShortestPath;
public Robot() {
queue = new LinkedList<ArrayList<String>>();
result = new ArrayList<ArrayList<String>>();
routeSoFar = new ArrayList<String>();
knownShortestPath = new LinkedList<String>();
}
// Runs when Robot has reached a node.
public void enterNodeActions() {
knownShortestPath = determineIdealPath();
}
// Runs to determine where to go next
public String chooseNextNode() {
if(!knownShortestPath.isEmpty())
{
// TODO: Need to go through the
}
}
public LinkedList<String> determineIdealPath()
{
try {
// Get the map
Map m = giveMeMapCopy();
// Get all entry nodes of map
Set<String> entryNodes = m.getEntryNodes();
/*
* Loop through all Entry nodes, and find out where we are.
* Set that as current working node.
*/
for (String n : entryNodes) {
if(n == getMyLocation())
{
workingNode = n;
}
}
// All enighbours of working node.
Set<String> neighboursNames = getNeighboursNames(workingNode);
/*
* For each neighbour, construct a path from working node to the neighbour node
* And add path to Queue and Result (if not already present).
*/
for(String node : neighboursNames)
{
if(!node.equals(getMyLocation()))
{
ArrayList<String> route = new ArrayList<String>();
route.add(getMyLocation());
route.add(node);
if(!containsRoute(result, route))
{
if(!containsRoute(queue, route))
{
queue.add(route);
}
result.add(route);
}
}
}
} catch (Exception e) {
e.printStackTrace();
}
}
}
在我想要递归发生的地方是在我经历了Entry节点[A]的所有邻居之后,我想移动到下一个[B]并为此做同样的事情,即通过它的每个邻居(忽略A ,因为它已经存在于Result列表中)并将它们添加到Queue和Result列表中.
我希望问题很清楚,如果不是请让我知道,我会尽力澄清任何不清楚的事情.
解决方法:
广度优先搜索通常在没有递归的情况下完成,因为它基于队列(在您的情况下为部分路径).另一方面,深度优先搜索基于堆栈,可以使用递归函数的调用堆栈非常自然地实现.