使用递归在2D数组中查找路径

我正在为A级别的项目工作。它涉及到查找网络的最大流量，并使用javascript。使用递归在2D数组中查找路径

我有一个2D数组，数组中的值表示两点之间的距离。阵列的一个例子：

我想我需要使用递归技术来查找路径;下面是一些伪代码，假设数组是4x4。 a是（0,0），b是（3,3）。

function search(a,b) 
    from a to b 
    if element(i,j) != 0 then 
     store value of element 
     search(j,3)

我想知道这是否是深度优先搜索的正确结构。谢谢你的帮助。

来源

2010-04-13 rikkit

对不起，数组中的值代表两点之间的距离？二维数组中的单个位置仅指定一个点，对吗？ – tloflin 2010-04-13 17:27:11

想象一下行和列标题（ABCD），所以三点和一点是C和A之间的距离。 – rikkit 2010-04-19 10:43:22

认真考虑使用BFS。 Edmonds-Karp是Ford-Fulkerson，但路径寻找方法是固定的 - BFS，它保证最坏情况O（V * E^2），这与DFS不同。 V是顶点数和E - 边数。如果你仍然坚持DFS，那么至少你应该检查你在循环中下一个访问的节点还没有被访问以防止永久递归。你可以为它使用一个布尔数组。

来源

2010-04-13 17:21:02

寻路可以利用此时，floodFill算法，它可以在一个递归形式写成

function floodFill(x, y, prevPoints) 
{ 
var prevPoints = prevPoints.concat([]); //make a copy of the points list since JS uses ref 

if(grid[x][y].isExit) return prevPoints; 
grid[x][y].accessed = true; 
prevPoints.push([x, y]); 

var result; 
var cfr; //cellfillresult 
if(grid[x+1][y].isPath && !grid[x+1][y].accessed) cfr = floodFill(x+1, y, prevPoints); 
if(cfr != null) result = cfr; 

if(grid[x-1][y].isPath && !grid[x-1][y].accessed) cfr = floodFill(x-1, y, prevPoints); 
if(cfr != null) result = cfr; 

if(grid[x][y+1].isPath && !grid[x][y+1].accessed) cfr = floodFill(x, y+1, prevPoints); 
if(cfr != null) result = cfr; 

if(grid[x][y-1].isPath && !grid[x][y-1].accessed) cfr = floodFill(x, y-1, prevPoints); 
if(cfr != null) result = cfr; 

return result; 
} 

var pathToExit = floodFill(entranceX, entranceY, []);

但是可以轻松实现，这是非常低效的，并会导致堆栈溢出一旦你到大十岁上下网格...一个更好的方法来做到这一点将是一个软件堆栈...

而且，它只发现一个工作的路径，但不是最有效的路径。你必须添加计算算法[这不应该花费太多的努力，希望]

来源

2010-04-13 17:51:04 Warty

使用递归在2D数组中查找路径

回答

相关问题