【算法随笔】DFS深度优先搜索

由 MisakaStone 发布

深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search。

其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。

1 全排列

给定一个字符数组,对所有元素进行全排列并逐行输出。

DFS函数,详解见注释:

    /**
     * The dfs function to achieve the full permutation of the letters
     * @param letters The given array storing the letters
     * @param level The level of the permutation
     * @param ans The array storing letters arranged
     */
    public static void dfs(char[] letters, int level, char[] ans) {

        // 1. The end condition
        if (level == letters.length) {
            System.out.println(Arrays.toString(ans));
            return;
        }

        // 2. Iterates over the candidate nodes in the given array
        for (int i = 0; i < letters.length; i ++) {
            char c = letters[i];
            if (c != '\0') { // If the letter is used
                ans[level] = c; // Stores it
                letters[i] = '\0'; // The letter is used
                dfs(letters, level+1, ans); // dfs, the level ++
                letters[i] = c; // Recovers the boolean array
            }
        }

    }

测试:

char[] letters = new char[] {'A', 'B', 'C'};
dfs(letters, 0, new char[letters.length]);

输出:

[A, B, C]
[A, C, B]
[B, A, C]
[B, C, A]
[C, A, B]
[C, B, A]

NOTE

对布尔数组的恢复语句写在if语句中dfs函数调用后

2 组合

对深搜函数来言,组合与全排列的不同点有两个:

  • 函数的结束条件不同

    • 需要一个新的参数来终止搜索,而不是全排列中的数组长度
  • 组合不考虑元素顺序

    • 为防止元素重复,循环的起始条件也要作为参数存入深搜函数且每次调用都要进行更新

组合DFS函数:

    public static void dfs(char[] letters, int level, char[] ans, int origin) {

        if (level == ans.length) { // 1. Changes the end condition
            System.out.println(Arrays.toString(ans));
            return;
        }

        for (int i = origin; i < letters.length; i ++) { // 2. Changes the original parameter
            ans[level] = letters[i];
            dfs(letters, level+1, ans, i+1); // 2.1 Updates the 'origin'
        }

    }

测试及输出:

char[] letters = new char[] {'A', 'B', 'C', 'D'};
dfs(letters,0, new char[3], 0);
[A, B, C]
[A, B, D]
[A, C, D]
[B, C, D]

NOTE

两个条件,一个更新

2.1 选数求和

题目来源:P1036 NOIP2002 普及组 选数 - 洛谷

题目描述

已知 $n$ 个整数 $x_1,x_2,\cdots,x_n$,以及 $1$ 个整数 $k$($k<n$)。从 $n$ 个整数中任选 $k$ 个整数相加,可分别得到一系列的和。例如当 $n=4$,$k=3$,$4$ 个整数分别为 $3,7,12,19$ 时,可得全部的组合与它们的和为:

$3+7+12=22$

$3+7+19=29$

$7+12+19=38$

$3+12+19=34$

现在,要求你计算出和为素数共有多少种。

例如上例,只有一种的和为素数:$3+7+19=29$。

输入格式

第一行两个空格隔开的整数 $n,k$($1 \le n \le 20$,$k<n$)。

第二行 $n$ 个整数,分别为 $x_1,x_2,\cdots,x_n$($1 \le x_i \le 5\times 10^6$)。

输出格式

输出一个整数,表示种类数。

样例 #1

样例输入 #1

4 3
3 7 12 19

样例输出 #1

1

题解

import java.util.Scanner;

public class Main {

    static int count = 0;

    public static void main(String[] args) {

        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int k = keyboard.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = keyboard.nextInt();
        }
        keyboard.close();

        dfs(nums, 0, k, 0, 0);
        System.out.println(count);

    }

    public static boolean isPrime(int num) {

        if (num == 1) {
            return false;
        }

        for(int num1 = 2; num1 <= Math.sqrt(num); num1 ++) {
            if (num % num1 == 0) {
                return false;
            }
        }

        return true;

    }

    public static void dfs(int[] nums, int level, int condition, int origin, int sum) {

        if (level == condition) {
            if (isPrime(sum)) {
                count ++;
            }
            return;
        }

        for (int i = origin; i < nums.length; i ++) {
            dfs(nums, level+1, condition, i+1, sum + nums[i]);
        }
    }

}

NOTE

函数调用中进行求和操作


暂无评论

发表评论