[算法]深度优先搜索DSF

LeetCode 算法 DFS algorithm 数据结构与算法
376

DFS(深度优先搜索 Depth-First-Search)[1]

DFS基本介绍

是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。这种算法不会根据图的结构等信息调整执行策略。
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的拓扑排序表1，利用拓扑排序表可以方便的解决很多相关的图论问题，如无权最长路径问题等等。
因发明“深度优先搜索算法”，约翰·霍普克洛夫特与罗伯特·塔扬在1986年共同获得计算机领域的最高奖：图灵奖。

DFS实现方法

  1. 首先将根节点放入stack中。
  2. 从stack中取出第一个节点，并检验它是否为目标。
    如果找到目标，则结束搜寻并回传结果。
    否则将它某一个尚未检验过的直接子节点加入stack中。
  3. 重复步骤2。
  4. 如果不存在未检测过的直接子节点。
    将上一级节点加入stack中。
    重复步骤2。
  5. 重复步骤4。
  6. 若stack为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

算法题

矩阵最长递增路径[2]

给定一个矩阵，矩阵内所有数均为非负整数。
求一条路径，该路径上所有数是递增的。
这个路径必须满足以下条件：
1、对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外。
2、你不能走重复的单元格。即每个格子最多只能走一次。
输入: [[1,2,3],[4,5,6],[7,8,9]] 输出:5 原因:1->2->3->6->9即可(当然这种递增路径不是唯一的)

解法如下：

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    public int solve (int[][] matrix) {
        int maxLength = 0;
	//存储已经遍历过的路径长度,这个是点睛之笔，避免了了重复计算
        int[][] checked = new int[matrix.length][matrix[0].length];
	//每个节点有四个方向可以行进
        int[][] paths = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
	//遍历每个节点，获取最大长度
        for (int row = 0;row < matrix.length;row++) {
            for (int col = 0;col < matrix[0].length;col++) {
                int length = getMaxLength(matrix, row, col, checked, paths);
                if (maxLength < length) {
                    maxLength = length;
                }
            }
        }
        return maxLength;
    }
    //递归查找节点的四个方向找出符合方向的节点并返回长度+1
    private int getMaxLength(int[][] m, int row, int col, int[][] checked, int[][] paths) {
        int length = 0;
        int maxLength = 0;
	//已经计算过就不再重复计算
        if(checked[row][col] > 0) {
            return checked[row][col];
        }
	//递归查找节点的四个方向找出符合方向的节点并返回长度 +1
        for (int[] path : paths) {
            int movedRow = row + path[0];
            int movedCol = col +  path[1];
            if (0 <= movedRow && movedRow < m.length &&
                    0 <= movedCol && movedCol < m[0].length &&
                    m[row][col] < m[movedRow][movedCol]) {
                length = getMaxLength(m, movedRow, movedCol, checked, paths);
            }
            if (length > maxLength){
                maxLength = length;
            }
        }
	//记录已经计算过的节点，其作为起点的最长长度
        checked[row][col] = maxLength + 1;
        return checked[row][col];
    }
    
}

本质上就是上述提到的DFS算法。对于数组的查询，以一个元素作为根节点root，接下来的过程就是利用DFS，以root节点开始对四个节点进行搜索。

参考

1.深度优先搜索， https://zh.wikipedia.org/wiki/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2
2. 矩阵最长递增路径，https://www.nowcoder.com/practice/7a71a88cdf294ce6bdf54c899be967a2?tpId=196&tqId=37184&rp=1&ru=%2Fta%2Fjob-code-total&qru=%2Fta%2Fjob-code-total%2Fquestion-ranking&tab=answerKey