最小生成树问题

给出一个带权重的无向图，请找出能够维持它连通性的权重之和的最小的一组边。
这个问题被称为“最小生成树”问题，也成为“最小连通子图”问题。
为什么称他为“树”？是因为我们可以很直观地得出“在上述问题的结果中一定不存在环”的结论。无环的图，退化为树。
一个很直观的想法是，既然是最小生成树，那么我们就让它生成一下看看。

Prim算法

我们首先随机选择一个节点作为基础的“树”，然后每次选择距离我们已经有的树最近的且可以直接相连的节点，将它加入树中。
当所有的节点都被加入树中之后，算法结束。 这个算法被称为Prim算法，非常直观。
但是我们仍然有几个细节要讨论：

1. 如何确定距离目前的树最近的节点？
   我们认为一个节点与树的距离是“节点到树上任意一个节点的最小距离”。找到这个最小节点是非常容易的：以类似于Dijkstra算法的方式即可快速确定。而这一距离的更新只需要在每次新插入节点时更新。
2. 这个问题针对的对象是无向图
   因此我们需要非常小心地调整邻接表和表示节点访问情况的向量。
3. 如果存在着若干个距离相同且都是最小值的节点，该如何处理？
   随机选择其一，然后继续遍历

代码

int Prim(const vector<vector<int>> &Graph) {
    vector<int> distance(Graph.size(), int(INT_MAX));
    unordered_map<int, bool> visited;
    int nowPoint = 0;
    int res = 0;

    while (visited.size() != Graph.size()) {
        visited[nowPoint] = 1;
        for (int i = 0; i < Graph[nowPoint].size(); i++) {
            if (visited.find(i) == visited.end() && Graph[nowPoint][i] != 0) {
                distance[i] = std::min(distance[i], Graph[nowPoint][i]);
            }
        }
        int minPoint, minValue = INT_MAX;
        for (int i = 0; i < distance.size(); i++) {
            if (visited.find(i) == visited.end() && distance[i] < minValue) {
                minValue = distance[i];
                minPoint = i;
            }
        }
        if (visited.size() == Graph.size()) minValue = 0;
        res += minValue;
        nowPoint = minPoint;
    }
    return res;
}

适用情况

Prim算法很明显适用于边稠密的情况，因为它不需要遍历一遍边，只需要遍历一遍节点。