C++示例详解Prim算法与优先队列

什么是Prim算法？

Prim算法是一种经典的最小生成树算法，它可以用于求无向连通图的最小生成树。该算法以一个顶点开始，通过不断地向外扩张生成最小生成树，最终遍历图中所有节点，并且每次扩张的时候选择权值最小的边。

Prim算法的实现流程

1. 选取一个起始节点开始。

2. 初始化辅助数组，该数组用来记录图中每个节点是否已经被访问，以及每个节点与已经访问的节点的最短距离，初始时所有节点都未被访问，距离为正无穷。

3. 将起始节点标记为已经访问，并设置其与其他节点的距离为0。

4. 从起始节点开始，遍历与其相连的所有节点，更新其到已访问节点的距离。

5. 在所有未访问的节点中，选取与已访问节点距离最短的那个节点，标记为已经访问。

6. 不断重复步骤4和5，直到遍历完图中所有节点。

7. 最终生成的最小生成树是一个有n-1条边的连通子图，其中n为节点的数量。

用优先队列实现Prim算法

优先队列可以帮助我们快速找到未访问的节点中距离最短的那个节点。具体实现流程如下：

1. 创建一个优先队列，用来存储还未访问的节点，队列按节点到已访问节点的距离从小到大排序，距离越小越先出队。

2. 初始化辅助数组，该数组用来记录图中每个节点是否已经被访问，以及每个节点与已经访问的节点的最短距离，初始时所有节点都未被访问，距离为正无穷。

3. 将起始节点标记为已经访问，并设置其与其他节点的距离为0。

4. 将起始节点加入优先队列。

5. 不断执行以下步骤，直到遍历完图中所有节点：

6. 从优先队列中取出距离最近的节点，并将其标记为已访问。

7. 遍历该节点的所有邻居节点，更新其与已访问节点的距离。

8. 如果该邻居节点还没有被访问，将其加入优先队列中。

9. 最终生成的最小生成树是一个有n-1条边的连通子图，其中n为节点的数量。

示例1

下面是C++示例代码实现，该示例用优先队列实现了Prim算法。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    int n = 6, m = 9;
    vector<vector<int> > edges = {{0, 1, 3}, {0, 2, 1}, {1, 2, 5}, {1, 3, 4}, {2, 3, 2}, {2, 4, 7}, {3, 4, 6}, {3, 5, 5}, {4, 5, 8}};

    vector<int> dist(n, INF), visited(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;

    int start = 0;
    dist[start] = 0;
    q.push(make_pair(0, start));

    int ans = 0;
    while (!q.empty()) {
        auto cur = q.top();
        q.pop();
        int d = cur.first, u = cur.second;
        if (visited[u]) {
            continue;
        }
        visited[u] = true;
        ans += d;

        for (auto edge : edges) {
            if (edge[0] == u) {
                int v = edge[1], w = edge[2];
                if (!visited[v] && w < dist[v]) {
                    dist[v] = w;
                    q.push(make_pair(dist[v], v));
                }
            }
            if (edge[1] == u) {
                int v = edge[0], w = edge[2];
                if (!visited[v] && w < dist[v]) {
                    dist[v] = w;
                    q.push(make_pair(dist[v], v));
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}

以上代码部分类和变量的含义说明如下：

• n: 节点的数量。
• m: 边的数量。
• edges: 存储图的邻接矩阵。
• dist: 存储每个节点与已经访问节点的最短距离。
• visited: 存储每个节点是否已经被访问。
• q: 优先队列，用来存储还未访问的节点。
• start: 起始节点。
• ans: 最小生成树的权值和。

以上代码使用了STL的优先队列实现。时间复杂度为O(E*logE)，其中E为图中边的数量。

示例2

下面是C++示例代码实现，该示例用数组实现了Prim算法。

#include <iostream>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;

int main() {
    int n = 6, m = 9;
    vector<vector<int> > edges = {{0, 1, 3}, {0, 2, 1}, {1, 2, 5}, {1, 3, 4}, {2, 3, 2}, {2, 4, 7}, {3, 4, 6}, {3, 5, 5}, {4, 5, 8}};

    vector<int> dist(n, INF), visited(n, false);

    int start = 0;
    dist[start] = 0;

    int ans = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, min_dist = INF;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                u = j;
                min_dist = dist[j];
            }
        }
        if (u == -1) {
            break;
        }
        visited[u] = true;
        ans += min_dist;

        for (auto edge : edges) {
            if (edge[0] == u) {
                int v = edge[1], w = edge[2];
                if (!visited[v] && w < dist[v]) {
                    dist[v] = w;
                }
            }
            if (edge[1] == u) {
                int v = edge[0], w = edge[2];
                if (!visited[v] && w < dist[v]) {
                    dist[v] = w;
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}

以上代码部分类和变量的含义说明如下：

• n: 节点的数量。
• m: 边的数量。
• edges: 存储图的邻接矩阵。
• dist: 存储每个节点与已经访问节点的最短距离。
• visited: 存储每个节点是否已经被访问。
• start: 起始节点。
• ans: 最小生成树的权值和。

以上代码使用了数组实现，时间复杂度为O(V^2)，其中V为节点的数量。

总结

本篇文章详细讲解了Prim算法和用优先队列实现Prim算法的流程。希望读者通过阅读本文，可以对Prim算法有一个全面的认识，并且能够掌握用优先队列实现Prim算法的技能。