typescript - 什么应该被视为 2D 或 3D 阵列的正确 DFS（深度优先搜索）算法输出？

Question

我正在尝试理解/学习DFS（使用TypeScript）2D array。我可以看到它可以有多个输出，我不确定应该将什么视为有效输出。

问题：

• 这是一种有效的方法吗？如果是，所有这些输出都有效吗？

方法：

• 初始化堆栈。
• 初始化二维布尔数组，大小与原始数组相同。为了避免遍历，进入循环。
• 将第一个元素位置（元素在 (0,0)，row=0，column=0）推入堆栈
• 现在直到堆栈不为空
  • 从堆栈中弹出位置。用“,”分割得到行索引和列索引。并检查索引是否在给定矩阵的范围内并在visited []数组中标记为false，如果不是则忽略它并从堆栈中弹出下一个位置。如果索引有效且未访问，则打印该元素。
  • 标记访问数组中的元素。
  • 将当前元素从左、右、下、上的元素位置添加到堆栈中。

示例：此代码将产生第一个输出。如果你改变左，右，下和上，那么可以产生不同的输出。

    var grid = [
        [-1, 2, 3],
        [0, 9, 8],
        [1, 0, 1]
    ];

function DFSMatrix(grid){
    var h = grid.length;
    if (h == 0)
        return;
    var l = grid[0].length;

    var visited = Array.from(Array(h), () => Array(l).fill(false));

    var stack = [];
    stack.push(0 + "," + 0);

    while (stack.length != 0) {

        var x = stack.pop();
        var row = Number.parseInt(x.split(",")[0])
        var col = Number.parseInt(x.split(",")[1]);

        if (row < 0 || col < 0 || row >= h || col >= l || visited[row][col])
            continue;

        visited[row][col] = true;
        var element = grid[row][col] + " ";
        console.log(element);
        // console.log(grid[row][col] + " ");
        // result.push(element);
        stack.push(row + "," + (col - 1)); //go left
        stack.push(row + "," + (col + 1)); //go right
        stack.push((row - 1) + "," + col); //go up
        stack.push((row + 1) + "," + col); //go down
    }
}

输出：

• 第一个输出：-1、0、1、0、9、2、3、8、1

• 第二个输出：-1、2、3、8、9、0、1、0、1

• 第三个输出：-1、0、1、0、1、8、9、2、3

标签： typescriptdepth-first-search

Answer 1

如果 BFS 的目的是横穿整个图（数组），则输出是正确的。
一个有效的答案是勾勒出最短路径的答案。在给出的示例中有多个等效的最短路径，因此有多个有效答案。
事实上，通过随机选择元素的方向（左、右、下、上），您将获得更有效的输出。

另一方面，如果目的是找到从源 (x1,y,1) 到目标 (x2,y2) 的最短路径，则需要更改算法：一旦到达目标，搜索就会停止。

旁注：在将元素添加到堆栈之前，“检查索引是否在给定矩阵的范围内”会更有效。