跳转至

12、贪心详解

​ 贪心算法（Greedy Algorithm）是一种解决问题的策略，它在每个决策点都选择局部最优解，希望通过一系列局部最优解得到全局最优解。贪心算法的核心思想是每一步都做出当前看来最好的选择，但并不保证这样的选择能够达到全局最优。

贪心算法的特点：

  1. 简单易懂：贪心算法的实现通常比较简单，容易理解。
  2. 高效：由于每一步都做出局部最优解，贪心算法通常具有较高的执行效率。
  3. 不一定得到全局最优解：贪心算法并不能保证在所有情况下得到全局最优解，但在某些特定问题中，贪心算法能够找到全局最优解。

贪心算法的设计步骤：

  1. 确定问题的最优子结构：分析问题，找到局部最优解和全局最优解之间的关系，以及如何通过局部最优解得到全局最优解。
  2. 选择贪心策略：设计一个策略，在每个决策点都选择局部最优解。
  3. 构造贪心算法：根据贪心策略，实现具体的算法过程。
  4. 证明算法正确性：验证贪心算法的正确性，确保算法可以找到全局最优解。

贪心算法的应用案例：

  1. 换零钱问题（Coin Change）：给定一组硬币面值和一个目标金额，求最少需要多少枚硬币能达到目标金额。
  2. Kruskal算法、Prim算法和Sollin算法：用于求解最小生成树问题。
  3. Dijkstra算法：用于求解单源最短路径问题。
  4. Huffman编码：用于数据压缩，构建最优前缀码。
  5. 部分背包问题：在给定容量限制的情况下，从物品中选择部分物品以获得最大价值。
  6. 区间调度问题：在一系列时间段中选择尽可能多的不重叠区间。
  7. 拓扑排序：主要应用于有向无环图（DAG，Directed Acyclic Graph）的顶点排序。
  8. 二分覆盖：给定一个有序数组，以及一个目标区间，求用数组中的最少元素数量来覆盖目标区间。

​ 需要注意的是，贪心算法并不适用于所有问题。在使用贪心算法时，要先分析问题是否具有贪心选择性质和最优子结构性质，然后设计贪心策略，最后验证算法的正确性。在某些问题中，贪心算法可以找到全局最优解，而在其他问题中，贪心算法可能只能找到局部最优解。

​

应用案例的详细介绍：

1、换零钱问题（Coin Change）：

​ 换零钱问题（Coin Change）的贪心解法在特定条件下才能得到最优解，例如美元和欧元等货币系统，但请注意它可能无法在所有情况下得到最优解。

​ 贪心策略：从最大面值的硬币开始，尽可能多地使用当前面值的硬币，直到无法使用更多硬币。然后继续使用次大面值硬币。重复此过程直到达到目标金额或无法满足条件。

​ 以下是换零钱问题的贪心解法及C++代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int coinChangeGreedy(int target, vector<int>& coins) {
    sort(coins.rbegin(), coins.rend());

    int numCoins = 0;

    for (int coin : coins) {
        while (target >= coin) {
            target -= coin;
            numCoins++;
        }
        if (target == 0) {
            break;
        }
    }

    if (target > 0) {
        cout << "No solution with the given coins!" << endl;
        return -1;
    }

    return numCoins;
}

int main() {
    vector<int> coins = {1, 5, 10, 25};
    int target = 63;

    int minCoins = coinChangeGreedy(target, coins);
    if (minCoins != -1) {
        cout << "Minimum number of coins: " << minCoins << endl;
    }

    return 0;
}

​ 在这个实现中，首先对硬币面值按降序排序。然后，遍历面值列表，每次尽可能多地使用当前面值的硬币，直到无法使用更多硬币。最后，返回所需硬币的最小数量。如果无法达到目标金额，则输出错误信息并返回-1。

​ 请注意，贪心解法可能无法处理所有情况，例如当硬币面值为[1, 4, 5]，目标金额为8时，贪心解法会给出结果4个硬币（5, 1, 1, 1），而实际最优解是2个硬币（4, 4）。在这种情况下，你需要使用动态规划或其他方法来获得全局最优解。

2、最小生成树问题

​ Kruskal算法、Prim算法和Sollin算法都是用于解决最小生成树问题的贪心算法。最小生成树是一个连通无向图的子图，包含所有顶点，且形成一棵树，使得所有边的权值之和最小。

2.1、Kruskal算法
  1. 将所有的边按权值从小到大排序。
  2. 初始化一个空的最小生成树。
  3. 按顺序遍历所有边，如果当前边的两个顶点不在同一个连通分量中，则将这条边加入最小生成树，并合并这两个顶点所在的连通分量。
  4. 重复步骤3，直到最小生成树中包含n-1条边（n为顶点个数）或遍历完所有边。

Kruskal算法的C++实现：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int u, v, weight;

    Edge(int u, int v, int weight) : u(u), v(v), weight(weight) {}
};

bool compareEdges(Edge a, Edge b) {
    return a.weight < b.weight;
}

int find(vector<int>& parent, int x) {
    if (parent[x] != x)
        parent[x] = find(parent, parent[x]);
    return parent[x];
}

void union_set(vector<int>& parent, int x, int y) {
    parent[find(parent, x)] = find(parent, y);
}

vector<Edge> kruskal(vector<Edge>& edges, int n) {
    sort(edges.begin(), edges.end(), compareEdges);

    vector<int> parent(n);
    for (int i = 0; i < n; ++i) {
        parent[i] = i;
    }

    vector<Edge> mst;
    for (Edge& edge : edges) {
        if (find(parent, edge.u) != find(parent, edge.v)) {
            mst.push_back(edge);
            union_set(parent, edge.u, edge.v);
        }
    }

    return mst;
}
2.2 Prim算法
  1. 初始化一个空的最小生成树和一个未访问顶点集合。
  2. 从任意一个顶点开始，将其加入最小生成树。
  3. 在未访问顶点集合中，找到一个与最小生成树中顶点相连的权值最小的边。
  4. 将找到的边加入最小生成树，将对应的顶点从未访问顶点集合中移除。
  5. 重复步骤3和4，直到最小生成树包含所有顶点。

Prim算法的C++实现：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <vector>
#include <climits>
#include <queue>

using namespace std;

struct Edge {
    int v, weight;
    Edge(int v, int weight) : v(v), weight(weight) {}
};

vector<Edge> prim(vector<vector<Edge>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    vector<Edge> mst;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, 0)); // 将第一个顶点加入优先队列，权值为0
    while (!pq.empty()) {
        int u = pq.top().second;
        int minWeight = pq.top().first;
        pq.pop();

        if (!visited[u]) {
            visited[u] = true;
            mst.push_back(Edge(u, minWeight));

            for (Edge& edge : graph[u]) {
                if (!visited[edge.v]) {
                    pq.push(make_pair(edge.weight, edge.v));
                }
            }
        }
    }

    return mst;
}

int main() {
    int n = 5; // 顶点个数
    vector<vector<Edge>> graph(n);
// 添加边（无向图）
    graph[0].push_back(Edge(1, 1));
    graph[0].push_back(Edge(2, 2));
    graph[1].push_back(Edge(0, 1));
    graph[1].push_back(Edge(2, 3));
    graph[1].push_back(Edge(3, 4));
    graph[1].push_back(Edge(4, 5));
    graph[2].push_back(Edge(0, 2));
    graph[2].push_back(Edge(1, 3));
    graph[2].push_back(Edge(4, 6));
    graph[3].push_back(Edge(1, 4));
    graph[3].push_back(Edge(4, 7));
    graph[4].push_back(Edge(1, 5));
    graph[4].push_back(Edge(2, 6));
    graph[4].push_back(Edge(3, 7));

    vector<Edge> mst = prim(graph);

    int totalWeight = 0;
    for (Edge& edge : mst) {
        cout << "Vertex: " << edge.v << ", Weight: " << edge.weight << endl;
        totalWeight += edge.weight;
    }
    cout << "Total weight: " << totalWeight << endl;

    return 0;
}

​ 以上代码实现了Prim算法。注意，这里使用优先队列（最小堆）来存储待访问的顶点及其权值，优先队列会自动根据权值对顶点进行排序，这样可以很容易地找到与当前最小生成树相连的权值最小的边。

2.3 Sollin算法

​ Sollin算法（又称Boruvka算法）是一种用于解决最小生成树（Minimum Spanning Tree，MST）问题的贪心算法。最小生成树问题要求找到一个给定加权无向图中权重和最小的生成树。Sollin算法的基本思路如下：

  1. 初始化一个空的最小生成树和一个森林，森林最初包含图中的所有顶点作为单独的分量。
  2. 在每个分量中找到连接到其他分量的具有最小权重的边。
  3. 将这些边添加到最小生成树，并合并相应的分量。
  4. 重复步骤2-3，直到森林中只有一个分量（即最小生成树）。

以下是使用Sollin算法解决最小生成树问题的C++代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <vector>
#include <utility>
#include <climits>

using namespace std;

struct Edge {
    int u, v, weight;
};

int find(vector<int>& parent, int i) {
    if (parent[i] == i) {
        return i;
    }
    return parent[i] = find(parent, parent[i]);
}

void union_set(vector<int>& parent, int u, int v) {
    parent[find(parent, u)] = find(parent, v);
}

int sollin(const vector<vector<pair<int, int>>>& adjList) {
    int n = adjList.size();
    int mst_weight = 0;
    vector<int> parent(n);

    for (int i = 0; i < n; ++i) {
        parent[i] = i;
    }

    int num_components = n;

    while (num_components > 1) {
        vector<Edge> min_edge(n, {-1, -1, INT_MAX});

        for (int u = 0; u < n; ++u) {
            for (const auto& edge : adjList[u]) {
                int v = edge.first;
                int weight = edge.second;

                int u_component = find(parent, u);
                int v_component = find(parent, v);

                if (u_component != v_component) {
                    if (weight < min_edge[u_component].weight) {
                        min_edge[u_component] = {u_component, v_component, weight};
                    }
                }
            }
        }

        for (const auto& edge : min_edge) {
            if (edge.weight != INT_MAX) {
                int u_component = find(parent, edge.u);
                int v_component = find(parent, edge.v);

                if (u_component != v_component) {
                    mst_weight += edge.weight;
                    union_set(parent, u_component, v_component);
                    --num_components;
                }
            }
        }
    }

    return mst_weight;
}

int main() {
    vector<vector<pair<int, int>>> adjList = {
        {{1, 10}, {2, 6}, {3, 5}},
        {{0, 10}, {3, 15}},
        {{0, 6}, {3, 4}},
        {{0, 5}, {1, 15}, {2, 4}}
    };

    int mst_weight = sollin(adjList);
    cout << "Weight of the minimum spanning tree: " << mst_weight << endl;

    return 0;
}

3、Dijkstra算法

​ Dijkstra算法是一种解决单源最短路径问题的贪心算法。它适用于有向图和无向图，但要求图中的权值非负。Dijkstra算法的基本思想是从源点开始，逐步扩展已找到最短路径的顶点集合，直到所有顶点都被包含在集合中。

Dijkstra算法的步骤如下：

  1. 初始化一个集合，用于存储已找到最短路径的顶点；初始化一个距离数组，用于存储源点到各顶点的最短距离。
  2. 将源点加入已找到最短路径的顶点集合，设置源点到自身的距离为0。
  3. 从尚未找到最短路径的顶点中，选取一个距离源点最近的顶点u。
  4. 将顶点u加入已找到最短路径的顶点集合，更新与u相邻的尚未找到最短路径的顶点的距离。
  5. 重复步骤3和4，直到所有顶点都被加入到已找到最短路径的顶点集合中。

以下是Dijkstra算法的C++实现：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <vector>
#include <limits>
#include <queue>

using namespace std;

const int INF = numeric_limits<int>::max(); // 定义一个无穷大的常量，表示不可达

vector<int> dijkstra(const vector<vector<pair<int, int>>>& graph, int source) {
    int n = graph.size();
    vector<int> dist(n, INF); // 初始化距离数组
    dist[source] = 0; // 源点到自身的距离为0

    // 使用优先队列存储待处理顶点，按距离从小到大排序
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, source));

    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();

        if (d > dist[u]) {
            continue;
        }

        // 遍历与顶点u相邻的顶点，更新距离
        for (const auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;

            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    return dist;
}

int main() {
    int n = 5; // 顶点个数
    vector<vector<pair<int, int>>> graph(n);

    // 添加边（有向图）
    graph[0].emplace_back(1, 1);
    graph[0].emplace_back(2, 2);
    graph[1].emplace_back(3, 4);
    graph[1].emplace_back(4, 5);
    graph[2].emplace_back(4, 6);
    graph[3].emplace_back(4, 7);
    int source = 0;
    vector<int> dist = dijkstra(graph, source);

    for (int i = 0; i < n; ++i) {
        cout << "Distance from vertex " << source << " to vertex " << i << ": ";
        if (dist[i] == INF) {
            cout << "unreachable" << endl;
        } else {
            cout << dist[i] << endl;
        }
    }

    return 0;
}

​ 以上代码实现了Dijkstra算法。注意，这里使用优先队列（最小堆）来存储待处理的顶点及其距离，优先队列会自动根据距离对顶点进行排序，这样可以很容易地找到距离源点最近的顶点。此外，使用pair表示边，其中first表示相邻顶点，second表示边的权值。

4、Huffman编码

​ Huffman编码是一种无损数据压缩算法，通过构建特定的前缀码（Prefix Code）实现字符的高效编码。在Huffman编码中，频率较高的字符使用较短的编码，而频率较低的字符使用较长的编码，从而实现整体的数据压缩。Huffman编码具有唯一解码性，即给定一串编码后的数据，可以唯一地还原成原始数据。

Huffman编码的构建过程：

  1. 统计字符频率：对输入数据进行字符频率统计。
  2. 构建Huffman树：利用贪心算法，以字符频率为权值构建Huffman树。
  3. 生成编码表：根据Huffman树，为每个字符生成相应的编码。

以下是Huffman编码的C++实现：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
#include <string>

using namespace std;

struct Node {
    char character;
    int frequency;
    Node* left;
    Node* right;

    Node(char character, int frequency, Node* left = nullptr, Node* right = nullptr)
        : character(character), frequency(frequency), left(left), right(right) {}
};

struct CompareNode {
    bool operator()(const Node* a, const Node* b) {
        return a->frequency > b->frequency;
    }
};

void generateHuffmanCodes(Node* root, string code, unordered_map<char, string>& huffmanCodes) {
    if (root == nullptr) {
        return;
    }

    if (root->left == nullptr && root->right == nullptr) {
        huffmanCodes[root->character] = code;
    }

    generateHuffmanCodes(root->left, code + "0", huffmanCodes);
    generateHuffmanCodes(root->right, code + "1", huffmanCodes);
}

unordered_map<char, string> buildHuffmanCodes(const string& input) {
    unordered_map<char, int> frequencyMap;
    for (char c : input) {
        ++frequencyMap[c];
    }

    priority_queue<Node*, vector<Node*>, CompareNode> pq;
    for (const auto& entry : frequencyMap) {
        pq.push(new Node(entry.first, entry.second));
    }

    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();

        Node* newNode = new Node('\0', left->frequency + right->frequency, left, right);
        pq.push(newNode);
    }

    Node* root = pq.top();

    unordered_map<char, string> huffmanCodes;
    generateHuffmanCodes(root, "", huffmanCodes);

    return huffmanCodes;
}

int main() {
    string input = "this is an example for huffman encoding";
    unordered_map<char, string> huffmanCodes = buildHuffmanCodes(input);

    cout << "Huffman codes:" << endl;
    for (const auto& entry : huffmanCodes) {
        cout << entry.first << ": " << entry.second << endl;
    }

    return 0;
}

​ 以上代码实现了Huffman编码。首先，统计输入数据中每个字符的频率。然后，利用优先队列（最小堆）构建Huffman树。在构建过程中，每次从优先队列中取出两个频率最小的节点，合并为一个新的节点，并将新节点的频率设置为这两个节点频率之和，然后将新节点放回优先队列。当优先队列中只剩下一个节点时，这个节点就是Huffman树的根节点。

​ 接着，根据Huffman树为每个字符生成对应的编码。为了生成编码，我们从根节点开始遍历Huffman树，每向左子树走一步，就在当前编码后面添加一个0，每向右子树走一步，就在当前编码后面添加一个1。当我们遇到一个叶子节点时，就找到了对应字符的编码。

​ 最后，输出生成的Huffman编码表。注意，这个实现仅生成了Huffman编码表，并没有实际对输入数据进行编码和解码。实际应用中，你可以使用这个编码表对输入数据进行编码，然后将编码后的数据和编码表一起传输或存储。接收方可以根据编码表对编码后的数据进行解码，从而实现数据压缩和传输。

5、部分背包问题

​ 部分背包问题（Fractional Knapsack Problem）是一种典型的贪心问题。与0-1背包问题不同，部分背包问题允许将物品拆分，即可以取物品的一部分。问题的目标是在给定背包容量的限制下，最大化背包中物品的总价值。

​ 贪心策略：每次选择单位重量价值最高的物品，将尽可能多的该物品放入背包，直到背包装满或该物品用完。然后继续选择下一个单位重量价值最高的物品，重复此过程。

​ 以下是部分背包问题的贪心解法及C++代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Item {
    int weight;
    int value;
    double valuePerWeight;

    Item(int weight, int value) : weight(weight), value(value), valuePerWeight((double)value / weight) {}
};

bool compareItems(const Item& a, const Item& b) {
    return a.valuePerWeight > b.valuePerWeight;
}

double fractionalKnapsack(int capacity, vector<Item>& items) {
    sort(items.begin(), items.end(), compareItems);

    double maxValue = 0.0;

    for (Item& item : items) {
        if (capacity >= item.weight) {
            maxValue += item.value;
            capacity -= item.weight;
        } else {
            maxValue += item.valuePerWeight * capacity;
            break;
        }
    }

    return maxValue;
}

int main() {
    int capacity = 50;
    vector<Item> items = {
        Item(10, 60),
        Item(20, 100),
        Item(30, 120),
    };

    double maxValue = fractionalKnapsack(capacity, items);
    cout << "Maximum value in knapsack: " << maxValue << endl;

    return 0;
}

​ 在这个实现中，首先定义一个结构体表示物品，包含物品的重量、价值以及单位重量价值。然后，对物品按照单位重量价值降序排列。接着，遍历排序后的物品列表，每次尽可能多地将当前物品放入背包，直到背包装满或当前物品用完。最后，返回背包中物品的总价值。

6、区间调度问题

​ 区间调度问题（Interval Scheduling）是一种典型的贪心问题。给定一组时间区间，要求选择尽可能多的互不相交的区间。互不相交是指任意两个区间的时间不重叠。

​ 贪心策略：按照结束时间对区间进行排序，每次选择结束时间最早的区间，然后从剩下的区间中删除与已选区间相交的区间。重复此过程直到没有剩余区间。

​ 以下是区间调度问题的贪心解法及C++代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Interval {
    int start;
    int end;

    Interval(int start, int end) : start(start), end(end) {}
};

bool compareIntervals(const Interval& a, const Interval& b) {
    return a.end < b.end;
}

int intervalScheduling(vector<Interval>& intervals) {
    sort(intervals.begin(), intervals.end(), compareIntervals);

    int count = 0;
    int lastEnd = -1;

    for (const Interval& interval : intervals) {
        if (interval.start >= lastEnd) {
            lastEnd = interval.end;
            ++count;
        }
    }

    return count;
}

int main() {
    vector<Interval> intervals = {
        Interval(1, 4),
        Interval(3, 5),
        Interval(0, 6),
        Interval(4, 7),
        Interval(3, 8),
        Interval(5, 9),
        Interval(6, 10),
        Interval(8, 11)
    };

    int maxNonOverlappingIntervals = intervalScheduling(intervals);
    cout << "Maximum number of non-overlapping intervals: " << maxNonOverlappingIntervals << endl;

    return 0;
}

​ 在这个实现中，首先定义一个结构体表示区间，包含区间的开始时间和结束时间。然后，对区间按照结束时间进行升序排序。接着，遍历排序后的区间列表，每次选择结束时间最早的区间，同时更新最后一个选择区间的结束时间。最后，返回选择的不相交区间的个数。

7、拓扑排序

​ 贪心算法在拓扑排序中并不是直接应用的解决方法，但是可以通过贪心策略实现拓扑排序。拓扑排序主要应用于有向无环图（DAG，Directed Acyclic Graph）的顶点排序。在拓扑排序中，对于所有的有向边 (u, v)，顶点 u 必须在顶点 v 之前。换句话说，拓扑排序中的顶点顺序要满足图中所有有向边的顺序要求。拓扑排序在诸如任务调度、编译器中的符号依赖处理等领域有广泛应用。

使用贪心策略实现拓扑排序的算法被称为Kahn算法。Kahn算法的基本思路如下：

  1. 首先找到所有入度为0的顶点，并将它们加入一个队列。
  2. 每次从队列中取出一个顶点，将其添加到结果序列中，然后移除所有从该顶点出发的有向边。
  3. 如果移除边后，某个邻接顶点的入度变为0，则将其加入队列。
  4. 重复步骤2-3，直到队列为空。
  5. 如果结果序列包含所有顶点，则返回拓扑排序结果；否则，图中存在环，拓扑排序无法完成。

需要注意的是，拓扑排序不是唯一的，因为有向无环图可能存在多种拓扑排序。此外，Kahn算法的时间复杂度是O(V+E)，其中V表示顶点数，E表示边数。这是因为每个顶点和每条边都会被访问一次。

以下是使用Kahn算法实现拓扑排序的C++代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> topologicalSort(const vector<vector<int>>& adjList) {
    int n = adjList.size();
    vector<int> inDegree(n, 0);
    vector<int> result;

    // 计算所有顶点的入度
    for (const auto& neighbors : adjList) {
        for (int neighbor : neighbors) {
            inDegree[neighbor]++;
        }
    }

    // 将入度为0的顶点加入队列
    queue<int> q;
    for (int i = 0; i < n; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    // 进行拓扑排序
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        result.push_back(current);

        for (int neighbor : adjList[current]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    // 如果结果包含所有顶点，返回拓扑排序结果；否则，返回空序列
    if (result.size() == n) {
        return result;
    } else {
        return {};
    }
}

int main() {
    vector<vector<int>> adjList = {
        {1, 2},
        {3},
        {3},
        {}
    };

    vector<int> result = topologicalSort(adjList);
    if (result.empty()) {
        cout << "The graph contains a cycle." << endl;
    } else {
        cout << "Topological order: ";
        for (int vertex : result) {
            cout << vertex << " ";
        }
        cout << endl;
    }

    return 0;
}

​ 此代码首先计算所有顶点的入度，然后使用一个队列存储所有入度为0的顶点。接下来，从队列中取出顶点，将其添加到结果序列中，并更新其邻接顶点的入度。如果某个邻接顶点的入度变为0，将其加入队列。最后，如果结果序列包含所有顶点，则返回拓扑排序结果；否则，返回空序列，表示图中存在环。

8、二分覆盖

​ 二分覆盖问题是这样的：给定一个有序数组，以及一个目标区间，求用数组中的最少元素数量来覆盖目标区间。

问题示例：给定一个有序数组 arr = [1, 3, 5, 7, 9] 和一个目标区间 [2, 16]，求用数组中的最少元素数量来覆盖目标区间。

​ 解决此问题的贪心策略是：在每一步中，选择可以覆盖当前未覆盖区域起始位置的最大元素。然后更新未覆盖区域的起始位置，直至整个区间被覆盖。

对于上述示例，解决步骤如下：

  1. 选择元素 1，覆盖区间 [1, 2]，未覆盖区域变为 [3, 16]。
  2. 选择元素 3，覆盖区间 [1, 4]，未覆盖区域变为 [5, 16]。
  3. 选择元素 5，覆盖区间 [1, 6]，未覆盖区域变为 [7, 16]。
  4. 选择元素 7，覆盖区间 [1, 8]，未覆盖区域变为 [9, 16]。
  5. 选择元素 9，覆盖区间 [1, 10]，未覆盖区域变为 [11, 16]。

​ 这样我们就用最少的元素（5个）覆盖了整个目标区间 [2, 16]。虽然这个问题是在一维情况下的，但实际上在很多实际问题中，我们需要处理更高维度的二分覆盖问题。贪心算法在这类问题中非常有效。

​ 以下是解决二分覆盖问题的C++代码：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <vector>

using namespace std;

int minElementsToCoverInterval(vector<int>& arr, int target_start, int target_end) {
    int n = arr.size();
    int start = target_start;
    int count = 0;
    int i = 0;

    while (start <= target_end && i < n) {
        int max_cover = start;
        while (i < n && arr[i] <= start) {
            max_cover = max(max_cover, arr[i] + 1);
            i++;
        }
        if (max_cover == start) {
            // 无法覆盖更多区域
            return -1;
        }
        start = max_cover;
        count++;
    }

    if (start <= target_end) {
        // 无法覆盖整个目标区间
        return -1;
    }

    return count;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9};
    int target_start = 2;
    int target_end = 16;

    int count = minElementsToCoverInterval(arr, target_start, target_end);
    if (count == -1) {
        cout << "Cannot cover the whole interval." << endl;
    } else {
        cout << "Minimum elements to cover the interval: " << count << endl;
    }

    return 0;
}

​ 此代码首先初始化未覆盖区域的起始位置和计数器。然后，遍历数组，寻找可以覆盖当前未覆盖区域起始位置的最大元素。每次找到这样的元素后，更新未覆盖区域的起始位置，并增加计数器。最后，如果整个区间被覆盖，返回计数器的值；否则，返回-1表示无法覆盖整个目标区间。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用