每日一算法:深度优先算法

2023-12-14 09:27:57

深度优先搜索(Depth-First Search,简称DFS)是一种用于遍历或搜索树或图的算法。如其名,该算法深入到可能的分支上,直到目标节点被找到或者已经没有其他节点可以继续深入,此时算法回溯到上一节点,以探索未被遍历的路径。深度优先搜索是一个递归算法,它利用了后进先出的栈结构,在图的遍历中特别有效。

深度优先搜索的步骤:

  1. 选择起点:从图中的某个顶点开始遍历。
  2. 访问节点:访问当前节点。如果该节点是目标节点,则搜索成功,返回结果。
  3. 递归遍历:对当前节点的所有未访问的相邻节点,采用深度优先搜索的方式递归遍历。
  4. 回溯:当当前节点的所有相邻节点都被访问过,或者在相邻节点中没有找到目标节点,算法回溯到上一节点继续执行步骤3。
  5. 结束条件:当所有节点都被访问过,或者找到目标节点,算法结束。

深度优先搜索的特点:

  • 内存消耗较小:由于只需存储一条从根节点到当前节点的路径,因此相较于宽度优先搜索,其内存消耗通常较小。
  • 找到解后停止:在搜索到解后,可以立即停止,不需要遍历整个图。
  • 可能陷入死循环:在遍历图时,如果不记录已经访问过的节点,可能会陷入无限循环的情况。
  • 不保证最短路径:深度优先搜索不保证找到的路径是最短的,它只是尽可能深地搜索图。

深度优先搜索的应用:

  • 解决迷宫问题:可以用来寻找从起点到终点的路径。
  • 排列组合问题:可以用来生成所有可能的排列组合。
  • 拓扑排序:在有向无环图中,深度优先搜索可以用来进行拓扑排序。
  • 解决连通性问题:可以用来判断两个节点是否连通,或者整个图的连通分量。

深度优先搜索的伪代码:

DFS(node):
  if node is visited:
    return

  mark node as visited
  for each node_neighbor in node.adjacent_nodes:
    if node_neighbor is not visited:
      DFS(node_neighbor)

在实际编程中,深度优先搜索可以通过递归实现,也可以通过显式地使用栈来实现非递归版本。递归版本的实现较为简洁,但在遇到深度非常大的图时可能会导致栈溢出。非递归版本虽然代码复杂一些,但可以避免栈溢出的问题。

案例

1.全排列
问题描述:

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

代码实现:
public static List<List<Integer>> res = new LinkedList<>();

    /**
     * 输入一组不重复的数字,返回它们的全排列
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> permute(int[] nums) {
        // 记录「路径」
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums, track);
        return res;
    }

    public static void backtrack(int[] nums, LinkedList<Integer> track) {
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (track.contains(num)) {
                continue;
            }
            track.add(num);
            backtrack(nums, track);
            track.removeLast();
        }
    }
2.N皇后问题
问题描述:

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

代码实现:
public static List<String[][]> result = new LinkedList<>();

    /**
     * N皇后问题
     * 如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
     * 给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
     *
     * @param n 皇后个数
     * @return 满足条件的所有方式
     */
    public static List<String[][]> solveNQueens(int n) {


        String[][] strings = new String[n][n];

        Arrays.fill(strings, ".");

        backtrack(strings, 0);

        return result;
    }

    public static void backtrack(String[][] strings, int i) {

        if (i >= strings.length) {
            result.add(strings);
            return;
        }

        for (int j = 0; j < strings.length; j++) {
            if (!isValid(strings, i, j)) {
                continue;
            }
            strings[i][j] = "Q";
            backtrack(strings, i + 1);
            strings[i][j] = ".";
        }

    }

    /**
     * i行j列放置皇后是否满足要求
     * @param strings 棋盘布局
     * @param i 行
     * @param j 列
     * @return 是否满足要求
     */
    public static boolean isValid(String[][] strings, int i, int j) {
        //判断同一行是否已经有
        for (int k = 0; k < i; k++) {
            if ("Q".equals(strings[i][k])) {
                return false;
            }
        }
        //判断左上方是否有
        for (int m = i - 1, n = j - 1; m >= 0 && n >= 0; m--, n--) {
            if ("Q".equals(strings[m][n])) {
                return false;
            }
        }
        //判断右上方是否有
        for (int m = i - 1, n = j + 1; m >= 0 && n <= j; m--, n++) {
            if ("Q".equals(strings[m][n])) {
                return false;
            }
        }
        return true;
    }
3.子集问题
问题描述:

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

代码实现:
public static List<List<Integer>> res2 = new LinkedList<>();

    /**
     * 子集问题
     * 给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
     * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
     *
     * @param nums 数组
     * @return 所有可能的子集
     */
    public static List<List<Integer>> subsets(int[] nums) {
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums, 0, track);
        return res2;
    }

    public static void backtrack(int[] nums, int start, LinkedList<Integer> track) {

        res2.add(new LinkedList<>(track));

        for (int i = start; i < nums.length; i++) {
            track.add(nums[i]);
            backtrack(nums, i + 1, track);
            track.removeLast();
        }

    }
4.组合问题
问题描述:

给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合

代码实现:
public static List<List<Integer>> res3 = new LinkedList<>();

    /**
     * 组合问题
     * 给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
     * @param n
     * @param k
     * @return 所有可能的组合
     */
    public static List<List<Integer>> combine(int n, int k) {
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(n, 1, k, track);
        return res3;
    }

    public static void backtrack(int n, int start, int k, LinkedList<Integer> track) {

        if (track.size() == k) {
            res3.add(new LinkedList<>(track));
            return;
        }
        for (int i = start; i <= n; i++) {
            track.add(i);
            backtrack(n, i + 1, k, track);
            track.removeLast();
        }

    }

文章来源:https://blog.csdn.net/fudaihb/article/details/134956434
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。