Java算法之BFS、DFS、动态规划和贪心算法的实现

本文将详细讲解Java中BFS、DFS、动态规划和贪心算法的实现及使用场景。

BFS

BFS全称Breadth-First Search，即广度优先搜索。BFS算法主要应用于无权重图的最短路径查找，或者非加权的图上的搜索问题。BFS算法使用了队列的数据结构来辅助实现，具体实现步骤如下：

1. 将起始节点加入队列；
2. 从队列头取出一个节点，遍历它的所有未被访问过的邻居并标记为已访问；
3. 将邻居节点加入队列；
4. 如果队列不为空，则重复步骤2~3。

下面是一个BFS示例代码，用于计算在一个无权重图（以邻接矩阵方式存储）中从给定的起始节点到目标节点的最短路径：

public class BFS {
    public static void main(String[] args) {
        int[][] graph = {
                {0, 1, 1, 0, 0},
                {1, 0, 0, 1, 0},
                {1, 0, 0, 1, 1},
                {0, 1, 1, 0, 1},
                {0, 0, 1, 1, 0}
        };
        int start = 0, end = 4;
        System.out.println("The shortest path from " + start + " to " + end + " is " + bfs(graph, start, end));
    }

    public static int bfs(int[][] graph, int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.length];
        queue.add(start);
        visited[start] = true;
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curr = queue.poll();
                if (curr == end) {
                    return level;
                }
                for (int j = 0; j < graph.length; j++) {
                    if (graph[curr][j] == 1 && !visited[j]) {
                        queue.offer(j);
                        visited[j] = true;
                    }
                }
            }
            level++;
        }
        return -1;
    }
}

DFS

DFS全称Depth-First Search，即深度优先搜索。DFS算法主要应用于图的遍历问题，具体实现步骤如下：

1. 从起始节点开始，每次选择一个未被访问的邻居节点进行访问，并将其标记为已访问；
2. 当前节点的所有邻居节点都被访问过后，则回溯到上一个未被访问的节点继续遍历。

下面是一个DFS示例代码，用于在一个无向图（以邻接表方式存储）中查找从起始节点到目标节点的路径：

public class DFS {
    static boolean det = false;
    static LinkedList<Integer>[] adjList;

    public static void main(String[] args) {
        adjList = new LinkedList[4];
        for (int i = 0; i < 4; i++) {
            adjList[i] = new LinkedList<>();
        }
        adjList[0].add(1);
        adjList[0].add(2);
        adjList[1].add(2);
        adjList[2].add(0);
        adjList[2].add(3);
        int start = 2, end = 3;

        visited = new boolean[4];
        visited[start] = true;
        dfs(start, end);
        if(det){
            System.out.println("Path exists");
        }else {
            System.out.println("Path does not exist");
        }
    }

    static boolean[] visited;

    public static void dfs(int node, int end) {
        if (!det) {
            if (node == end) {
                det = true;
            }
            Iterator<Integer> i = adjList[node].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    dfs(n, end);
                }
            }
        }
    }
}

贪心算法

贪心算法（Greedy Algorithm）是一种在每一步取当前状态下最优解的算法，即贪心算法每次寻找当前最优解，并加以选择和保存。简单理解是尽可能地选择当前情况下最优的方案，从而达到全局最优的效果。贪心算法主要应用在需要求最优解的组合问题，具体实现步骤如下：

1. 初始解为空解，即其中不包含任何一个原问题提出的元素；
2. 在满足约束条件的前提下，确定该问题的最大加法递推性质所要求的元素并加入到当前解中；
3. 使用该元素生成一个新问题，再从该新问题出发重复步骤2~3。

这里给出奶酪问题（LeetCode 882）的贪心算法示例代码：

假设有一个二维平面上的无限大的奶酪，上面散布着许多点，每个点表示一个奶酪。你的任务是找到一条线，这条线会将奶酪切成两份，并且两份奶酪大小相等。回答这条线为多长。奶酪的密度是均匀的，并且两者密度相同。

public class CheeseProblem {
    public static void main(String[] args) {
        int[][] cheese = {{1, 0}, {0, 1}, {1, 1}};
        System.out.println(cheeseSlice(cheese));
    }

    public static double cheeseSlice(int[][] cheese) {
        int n = cheese.length;
        double totalX = 0.0, totalY = 0.0;
        for (int[] point : cheese) {
            totalX += point[0];
            totalY += point[1];
        }
        double midX = totalX / n, midY = totalY / n;
        double[] distances = new double[n];
        for (int i = 0; i < n; ++i) {
            distances[i] = Math.sqrt((cheese[i][0] - midX) * (cheese[i][0] - midX) + (cheese[i][1] - midY) * (cheese[i][1] - midY));
        }
        Arrays.sort(distances);
        double sum1 = 0.0, sum2 = 0.0;
        for (int i = 0; i < n / 2; ++i) {
            sum1 += distances[i];
        }
        for (int i = n / 2; i < n; ++i) {
            sum2 += distances[i];
        }
        return Math.abs(sum1 - sum2);
    }
}

动态规划

动态规划（Dynamic Programming）是算法设计中的一种方法，该方法通常用于优化递归算法，例如求斐波那契数列的值。动态规划算法的基本思想是将原问题拆分为多个子问题，完成一个子问题后保存其结果，便于需要时使用已经完成的子问题的结果计算其他子问题。具体实现步骤如下：

1. 将原始问题拆分为多个分解的子问题；
2. 分别解决每个子问题，可以使用记忆化技术从已经计算的子问题中重用计算结果；
3. 组合每个子问题的解来得到原始问题的解，从而实现对原始问题的求解。

以下是一个斐波那契数列的动态规划示例代码：

public class Fibonacci {
    public static void main(String[] args) {
        int num = 10;
        System.out.print(fibonacci(num));
    }

    public static int fibonacci(int num) {
        int[] memo = new int[num + 1];
        return helper(num, memo);
    }

    public static int helper(int num, int[] memo) {
        if (num <= 1) {
            return num;
        }
        if (memo[num] != 0) {
            return memo[num];
        }
        memo[num] = helper(num - 1, memo) + helper(num - 2, memo);
        return memo[num];
    }
}

以上就是BFS、DFS、贪心算法和动态规划算法的完整攻略，希望可以帮助到读者。