快速学习Java中的广度优先和深度优先算法、动态规划和贪心技巧

旧城等待， 2024-03-24 15:32 36阅读 0赞

## 前言 ##

广度优先搜索（BFS）和深度优先搜索（DFS）是图遍历算法中最常见的两种算法，主要用于解决搜索和遍历问题。动态规划和贪心算法则用来解决优化问题。

### 广度优先搜索 ###

广度优先搜索算法是一种遍历或搜索树或图的算法，它从根节点开始搜索并逐层向下扩展，直到找到目标状态或所有节点都被遍历。BFS通常使用队列来实现，它每次将下一个节点放入队列中，直到所有的节点都被访问。

下面是一个Java实现：

public void bfs(Node start) {
        
        Queue<Node> queue = new LinkedList<>();
        Set<Node> visited = new HashSet<>();
    
        queue.offer(start);
        visited.add(start);
    
        while (!queue.isEmpty()) {
        
            Node node = queue.poll();
            System.out.print(node.val + " ");
    
            for (Node neighbor : node.neighbors) {
        
                if (!visited.contains(neighbor)) {
        
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }

### 深度优先搜索 ###

深度优先搜索算法是一种遍历或搜索树或图的算法，它从根节点开始递归地遍历所有子树，直到找到目标状态或所有节点都被遍历。DFS通常使用栈来实现，它每次将下一个节点压入栈中，直到所有的节点都被访问。

下面是一个Java实现：

public void dfs(Node node, Set<Node> visited) {
        
        System.out.print(node.val + " ");
        visited.add(node);
    
        for (Node neighbor : node.neighbors) {
        
            if (!visited.contains(neighbor)) {
        
                dfs(neighbor, visited);
            }
        }
    }

### 动态规划 ###

动态规划算法（DP）是一种解决问题的方法，它用来解决重叠子问题和最优子结构问题。DP通常用来解决优化问题，例如最短路径问题、背包问题等。

下面是一个Java实现：

public int knapsack(int[] weights, int[] values, int capacity) {
        
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
    
        for (int i = 1; i <= n; i++) {
        
            for (int j = 1; j <= capacity; j++) {
        
                if (weights[i - 1] <= j) {
        
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                } else {
        
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
    
        return dp[n][capacity];
    }

### 贪心 ###

贪心算法是一种解决优化问题的方法，它总是选择当前最优解。与动态规划不同，贪心算法并没有考虑所有的子问题，而是只看当前的最优解。

下面是一个Java实现：

public int knapsack(int[] weights, int[] values, int capacity) {
        
        int n = weights.length;
        Item[] items = new Item[n];
    
        for (int i = 0; i < n; i++) {
        
            items[i] = new Item(weights[i], values[i]);
        }
    
        Arrays.sort(items, (a, b) -> b.valuePerWeight - a.valuePerWeight);
    
        int totalValue = 0;
        int remainingCapacity = capacity;
    
        for (Item item : items) {
        
            if (remainingCapacity >= item.weight) {
        
                totalValue += item.value;
                remainingCapacity -= item.weight;
            } else {
        
                totalValue += item.valuePerWeight * remainingCapacity;
                break;
            }
        }
    
        return totalValue;
    }
    
    class Item {
        
        int weight;
        int value;
        int valuePerWeight;
    
        public Item(int weight, int value) {
        
            this.weight = weight;
            this.value = value;
            this.valuePerWeight = value / weight;
        }
    }

## 总结 ##

在实际编程中，我们需要根据具体问题来选择不同的算法，例如搜索问题可以使用BFS或DFS，优化问题可以使用动态规划或贪心算法。需要注意的是，贪心算法往往只适用于一些特定的情况，有时会得到次优解或者错误解。因此，在使用贪心算法时需要仔细考虑问题和分析可能的情况。