Java算法之BFS,DFS,动态规划和贪心算法如何实现
更新时间：2023-12-05前言
在计算机科学中，算法是解决问题的一系列步骤或指令。在 Java 中，有很多经典的算法，比如广度优先搜索（Breadth-First Search，BFS）、深度优先搜索（Depth-First Search，DFS）、动态规划（Dynamic Programming）和贪心算法（Greedy Algorithm）。这些算法在不同的场景中有着不同的应用，可以帮助我们解决各种问题。在本文中，我们将讨论如何实现这些算法，并提供相应的 Java 代码示例。BFS（广度优先搜索）
广度优先搜索是一种基于“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的顶点，然后是离起始顶点距离为2的顶点，依此类推。BFS 需要借助队列数据结构来实现。以下是一个 BFS 算法的示例代码：
import java.util.LinkedList;
import java.util.Queue;
class BFS {
static class Node {
int data;
Node left, right;
public Node(int data) {
this.data = data;
left = right = null;
}
}
static void bfs(Node root) {
if (root == null)
return;
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
System.out.print(node.data + " ");
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
bfs(root);
}
}
以上示例中，我们使用一个队列来保存待访问的节点，并在遍历每个节点时将其左右子节点放入队列中。通过这样的方式，可以实现按层级遍历二叉树，打印出节点的值。
DFS（深度优先搜索）
深度优先搜索是一种递归地钻入图或树的深处，尽可能深地搜索。DFS 通常使用递归或栈数据结构来实现。以下是一个 DFS 算法的示例代码：
import java.util.LinkedList;
class DFS {
static class Graph {
int vertices;
LinkedList[] adjacencyList;
Graph(int vertices) {
this.vertices = vertices;
adjacencyList = new LinkedList[vertices];
for (int i = 0; i < vertices; i++)
adjacencyList[i] = new LinkedList<>();
}
void addEdge(int source, int destination) {
adjacencyList[source].add(destination);
}
void dfs(int vertex, boolean[] visited) {
visited[vertex] = true;
System.out.print(vertex + " ");
for (int adjVertex : adjacencyList[vertex]) {
if (!visited[adjVertex]) {
dfs(adjVertex, visited);
}
}
}
void dfsTraversal(int startVertex) {
boolean[] visited = new boolean[vertices];
dfs(startVertex, visited);
}
}
public static void main(String[] args) {
int vertices = 5;
Graph graph = new Graph(vertices);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.dfsTraversal(0);
}
}
以上示例中，我们使用邻接表来表示图的关系。通过递归地深入访问节点的邻接节点，可以实现 DFS。在 DFS 过程中，我们还使用一个 boolean 数组来跟踪已访问的节点，以避免重复访问。
动态规划
动态规划是一种将问题划分为子问题，并存储子问题解决方案的算法思想。通过解决子问题，我们可以得到原问题的解。动态规划常用于解决最优化问题。以下是一个动态规划算法的示例代码，用于计算斐波那契数列的第 n 项：
class DynamicProgramming {
static int fibonacci(int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
public static void main(String[] args) {
int n = 6;
System.out.println("斐波那契数列第 " + n + " 项为：" + fibonacci(n));
}
}
以上示例中，我们使用一个动态规划数组 dp 来存储计算过的斐波那契数列项。通过迭代填充 dp 数组，我们可以计算出第 n 个斐波那契数。
贪心算法
贪心算法是一种优化问题的算法思想，它每次都选择当前最优解，而不考虑全局最优解。该算法通常适用于一些特定类别的问题，例如图的最小生成树、单源最短路径等。以下是一个贪心算法的示例代码，用于找零钱问题：
class GreedyAlgorithm {
static void makeChange(int[] coins, int amount) {
int totalCoins = 0;
for (int i = coins.length - 1; i >= 0; i--) {
int currentCoins = amount / coins[i];
totalCoins += currentCoins;
amount %= coins[i];
if (currentCoins > 0) {
System.out.println(coins[i] + " 元硬币数量：" + currentCoins);
}
}
System.out.println("总硬币数量：" + totalCoins);
}
public static void main(String[] args) {
int[] coins = {10, 5, 2, 1};
int amount = 28;
makeChange(coins, amount);
}
}
以上示例中，我们使用贪心算法来找零钱。从最大面额的硬币开始，尽可能多地找零，直到剩余的金额为 0。通过这种方式，我们可以使用较少量的硬币完成找零。
