Prim最小生成树

Prim最小生成树

Prim算法是用于寻找加权无向图的最小生成树的贪心算法

最小生成树是一个包含图中所有顶点的树，并且边的总权重最小的树

Prim算法的核心思想逐渐构建最小生成树，从一个顶点开始，每次选择与当前树相连的最小边，直到所有顶点都被包含在树中

Prim算法的基本原理

1. 初始化

   从图中的任意一个顶点开始，将其加入到最小生成树中，创建一个集合来存储最小生成树的顶点，初始化一个优先队列（或最小堆）来选择边权重最小的边

2. 选择边

   在每一步中，从优先队列中取出权重最小的边，该边连接了已加入最小生成树的顶点和未加入的顶点，将未加入的顶点添加到最小生成树中，并将该边加入到树中

3. 更新边

   将新加入的顶点与图中其他未加入的顶点之间的边加入到优先队列中，以便在后续步骤中考虑

4. 重复

   重复选择边和更新边的过程，直到所有顶点都被包含在最小生成树中

算法步骤

1. 选择起始顶点:
   • 选择一个任意的起始顶点，将其标记为已访问。
2. 维护一个优先队列:
   • 使用优先队列（最小堆）来存储所有已访问顶点与未访问顶点之间的边，并按边的权重进行排序。
3. 构建最小生成树:
   • 从优先队列中取出权重最小的边，检查该边的终点是否已被访问。
   • 如果未被访问，则将其加入最小生成树，更新已访问的顶点集合，并将新顶点与其他未访问顶点的边加入优先队列。
   • 重复此过程，直到所有顶点都被访问。

代码示例

int main() {
    int V , E;
    cin >> V >> E;
    vector<vector<pair<int,int>>> graph(V+1);
    // 读取所有边
    for (int i = 0; i < E; i++) {
        int v1, v2, val;
        cin >> v1 >> v2 >> val; // 读取边的起点、终点和权值
        graph[v1].emplace_back(val, v2); // 添加边到邻接表
        graph[v2].emplace_back(val, v1); // 因为是无向图，添加反向边
    }
    auto cmp = [](pair<int,int> v1 , pair<int,int> v2){
        return v1.first > v2.first;
    };
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    vector<bool> inMST(V+1,false);
    pq.push({0,1});
    int isUsed = 0 ;
    int res = 0;
    while(!pq.empty() && isUsed < V)
    {
        auto val = pq.top();
        pq.pop();
        int weight = val.first;
        int dot = val.second;
        if(inMST[dot]) continue;
        res += weight;
        isUsed ++;
        inMST[dot] = true;
        for(const auto& [w,v] : graph[dot])
        {
            if(!inMST[v]) pq.push({w,v});
        }
    }
    cout <<res << endl;
    return 0;
}