【图论】最小生成树与Prim、Kruskal算法

求图的最小生成树的Prim、Kruscal算法，其实都是由最小生成树的性质推来的，掌握了该性质，便能较容易地推导出这两种算法。

最小生成树的性质

无向图G的顶点集为 V V V，设 U U U为 V V V的真子集， u ∈ U u\in U u∈U， v ∈ ( V − U ) v\in (V- U) v∈(V−U)，边u-v是连通 U U U、的所有边中权重最小的一条，则边u-v一定在G的最小生成树（MST）中。
反证法证明：假设T是一个MST，边u-v不在该MST中，先把它加入到T，则出现包含该边的环；T中必存在另一条边 u ′ − v ′ u^\prime-v^\prime u′−v′，连接题中两个集合，删除它后，环消失，出现新的MST，并且比原MST的权重更小，矛盾。

Prim算法

思路就是任取一个顶点作为初始U，不断寻找连接两个子集的所有边中权重最小的一条，把此边在 V − U V-U V−U上的顶点移到 U U U，重复这个操作，直至U包含全部顶点。

Kruscal算法

直接将所有边按权重排序，从小到大，每次尝试添加一条到MST，如果加入后没有产生环就加入该边，否则跳过。

松弛操作

两种算法都用了求最值问题的松弛操作思路，相似的例子，求K个已排序数组的最短公共区间，该区间包含每个数组至少一个元素，初始化选择各个数组首个元素组成集合的最小最大值，然后松弛，选择最小值所在数组向右取元素，更新区间。

#include <vector>
#include <utility>
#include <numeric>
#include <iostream>
#include <limits>
#include <tuple>
using namespace std;
class Solution {
public:
    vector<int> smallestRange(vector<vector<int> > &nums)
    {
        bool stop = false;
        int length = 2e5;
        int left = -1e5;
        int right = 1e5;
        vector<size_t> v_pos;
        vector<size_t> v_size;
        vector<int> holder;
        std::vector<int> lrlen{left, right, length};
        Init(nums, v_pos, v_size, holder);
        UpdateLeftRight(nums, v_pos, v_size, holder, lrlen, stop);
        while (!stop) {
            UpdateLeftRight(nums, v_pos, v_size, holder, lrlen, stop);
        }
        return {lrlen[0], lrlen[1]};
    }

    tuple<size_t, int, int> GetMinMax(const vector<int> &holder_)
    {
        int min = numeric_limits<int>::max();
        int max = numeric_limits<int>::min();
        size_t pos = 0;
        for (size_t i = 0; i < holder_.size(); i++) {
            if (min > holder_[i]) {
                min = holder_[i];
                pos = i;
            }
            if (max < holder_[i]) {
                max = holder_[i];
            }
        }
        return {pos, min, max};
    }
    void UpdateLeftRight(const vector<vector<int> > &nums, vector<size_t> &v_pos, vector<size_t> &v_size,
                         vector<int> &holder, std::vector<int> &lrlen, bool &stop)
    {
        auto res = GetMinMax(holder);
        int tmp_left = get<1>(res);
        int tmp_right = get<2>(res);
        size_t pos = get<0>(res);
        if (v_pos[pos] == (nums[pos].size() - 1)) {
            stop = true;
        }
        v_pos[pos]++;
        int tmp_length = tmp_right - tmp_left;
        if (tmp_length < lrlen[2] || (tmp_length == lrlen[2] && tmp_left < lrlen[0])) {
            lrlen[0] = tmp_left;
            lrlen[1] = tmp_right;
            lrlen[2] = tmp_length;
        }
        holder.clear();
        for (size_t i = 0; i < v_pos.size(); i++) {
            holder.push_back(nums[i][v_pos[i]]);
        }
    }
    void Init(const vector<vector<int> > &nums, vector<size_t> &v_pos, vector<size_t> &v_size, vector<int> &holder)
    {
        v_pos.clear();
        v_size.clear();
        holder.clear();
        for (size_t i = 0; i < nums.size(); i++) {
            v_pos.push_back(0);
            v_size.push_back(nums[i].size());
            holder.push_back(nums[i][0]);
        }
    }
};
int main()
{
    Solution A;
    vector<int> a{4, 10, 15, 24, 26};
    vector<int> b{0, 9, 12, 20};
    vector<int> c{5, 18, 22, 30};
    vector<vector<int> > q{a, b, c};
    auto res = A.smallestRange(q);
    for (auto i : res) {
        cout << i << " ";
    }
    cout << endl;
    a.clear();
    b.clear();
    c.clear();
    for (int i = 1; i < 4; i++) {
        a.push_back(i);
        b.push_back(i);
        c.push_back(i);
    }
    vector<vector<int> > qb{a, b, c};
    res = A.smallestRange(qb);
    for (auto i : res) {
        cout << i << " ";
    }
    return 0;
}