使用递归在二维数组中查找路径

Question

我正在为我的 A level 做一个项目。它涉及找到网络的最大流量，我正在使用 javascript。

我有一个二维数组，数组中的值表示两点之间的距离。数组的一个例子：

0 2 2 0
0 0 1 2
0 0 0 2
0 0 0 0

我想我需要使用递归技术来查找路径；下面是一些伪代码，假设数组是 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)

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

Answer 1

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

Answer 2

寻路可以通过使用洪水填充算法轻松实现，该算法可以以递归形式编写为

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, []);  

然而，这是非常低效的，并且一旦到达较大的网格就会导致堆栈溢出......更好的方法是是做一个软件栈...

而且，它只找到一条可行的路径，而不是最有效的路径。您必须在算法中添加计数[希望这不会花费太多精力]