How to implement Java algorithm BFS, DFS, dynamic programming and greedy algorithm

Breadth-first search

The breadth-first search algorithm is an algorithm that traverses or searches a tree or graph. It searches from the root node and expands downward layer by layer until the target state is found or all nodes are Traverse. BFS is usually implemented using a queue, which puts the next node into the queue each time until all nodes have been visited.

The following is a Java implementation:

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);
            }
        }
    }
}

Depth-first search

The depth-first search algorithm is an algorithm that traverses or searches a tree or graph, starting recursively from the root node Traverse all subtrees until the target state is found or all nodes are traversed. DFS is usually implemented using a stack, which pushes the next node onto the stack each time until all nodes have been visited.

The following is a Java implementation:

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);
        }
    }
}

Dynamic Programming

Dynamic programming algorithm (DP) is a problem-solving method that is used to solve overlapping sub-problems and the most Eusubstructure problem. DP is usually used to solve optimization problems, such as the shortest path problem, knapsack problem, etc.

The following is a Java implementation:

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];
}

Greedy

The greedy algorithm is a method of solving optimization problems. It always chooses the current optimal solution. Unlike dynamic programming, the greedy algorithm does not consider all sub-problems, but only looks at the current optimal solution.

The following is a Java implementation:

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;
    }
}

The above is the detailed content of How to implement Java algorithm BFS, DFS, dynamic programming and greedy algorithm. For more information, please follow other related articles on the PHP Chinese website!