快捷導(dǎo)航

Java算法之BFS,DFS,動(dòng)態(tài)規(guī)劃和貪心算法的實(shí)現(xiàn)

更新時(shí)間：2023年04月07日 08:29:05 作者：亮點(diǎn)菌

廣度優(yōu)先搜索（BFS）和深度優(yōu)先搜索（DFS）是圖遍歷算法中最常見(jiàn)的兩種算法，主要用于解決搜索和遍歷問(wèn)題。動(dòng)態(tài)規(guī)劃和貪心算法則用來(lái)解決優(yōu)化問(wèn)題。本文就來(lái)看看這些算法的具體實(shí)現(xiàn)吧

前言

廣度優(yōu)先搜索（BFS）和深度優(yōu)先搜索（DFS）是圖遍歷算法中最常見(jiàn)的兩種算法，主要用于解決搜索和遍歷問(wèn)題。動(dòng)態(tài)規(guī)劃和貪心算法則用來(lái)解決優(yōu)化問(wèn)題。

廣度優(yōu)先搜索

廣度優(yōu)先搜索算法是一種遍歷或搜索樹(shù)或圖的算法，它從根節(jié)點(diǎn)開(kāi)始搜索并逐層向下擴(kuò)展，直到找到目標(biāo)狀態(tài)或所有節(jié)點(diǎn)都被遍歷。BFS通常使用隊(duì)列來(lái)實(shí)現(xiàn)，它每次將下一個(gè)節(jié)點(diǎn)放入隊(duì)列中，直到所有的節(jié)點(diǎn)都被訪問(wèn)。

下面是一個(gè)Java實(shí)現(xiàn)：

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

深度優(yōu)先搜索

深度優(yōu)先搜索算法是一種遍歷或搜索樹(shù)或圖的算法，它從根節(jié)點(diǎn)開(kāi)始遞歸地遍歷所有子樹(shù)，直到找到目標(biāo)狀態(tài)或所有節(jié)點(diǎn)都被遍歷。DFS通常使用棧來(lái)實(shí)現(xiàn)，它每次將下一個(gè)節(jié)點(diǎn)壓入棧中，直到所有的節(jié)點(diǎn)都被訪問(wèn)。

下面是一個(gè)Java實(shí)現(xiàn)：

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

動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃算法（DP）是一種解決問(wèn)題的方法，它用來(lái)解決重疊子問(wèn)題和最優(yōu)子結(jié)構(gòu)問(wèn)題。DP通常用來(lái)解決優(yōu)化問(wèn)題，例如最短路徑問(wèn)題、背包問(wèn)題等。

下面是一個(gè)Java實(shí)現(xiàn)：

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

貪心

貪心算法是一種解決優(yōu)化問(wèn)題的方法，它總是選擇當(dāng)前最優(yōu)解。與動(dòng)態(tài)規(guī)劃不同，貪心算法并沒(méi)有考慮所有的子問(wèn)題，而是只看當(dāng)前的最優(yōu)解。

下面是一個(gè)Java實(shí)現(xiàn)：

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

總結(jié)

在實(shí)際編程中，我們需要根據(jù)具體問(wèn)題來(lái)選擇不同的算法，例如搜索問(wèn)題可以使用BFS或DFS，優(yōu)化問(wèn)題可以使用動(dòng)態(tài)規(guī)劃或貪心算法。需要注意的是，貪心算法往往只適用于一些特定的情況，有時(shí)會(huì)得到次優(yōu)解或者錯(cuò)誤解。因此，在使用貪心算法時(shí)需要仔細(xì)考慮問(wèn)題和分析可能的情況。

到此這篇關(guān)于Java算法之BFS,DFS,動(dòng)態(tài)規(guī)劃和貪心算法的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: