数据结构图的prim算法

Prim算法是一种用于解决最小生成树问题的贪心算法。它的基本思想是从图的某个顶点开始，不断选择与当前生成树相邻的、权值最小的边，直到生成一棵包含图中所有顶点的最小生成树。

以下是Prim算法的基本步骤：

1. 选择任意一个顶点作为起始点，将该顶点加入到已经生成的树中。
2. 以已经生成的树中的所有顶点为起点，遍历它们所能到达的所有未加入到已经生成的树中的顶点，找到其中权值最小的边。
3. 将找到的权值最小的边所连接的顶点加入到已经生成的树中。
4. 重复步骤2和步骤3，直到生成一棵包含图中所有顶点的最小生成树。

下面是Prim算法的C++实现代码：

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

const int N = 100010, INF = 0x3f3f3f3f;
int n, m;
int h[N], e[N], ne[N], w[N], idx;
bool st[N];
int dist[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    int res = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
    q.push({0, 1});

    while (q.size())
    {
        auto t = q.top();
        q.pop();

        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = true;
        res += distance;

        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > w[i])
            {
                dist[j] = w[i];
                q.push({dist[j], j});
            }
        }
    }

    return res;
}

int main()
{
    memset(h, -1, sizeof h);

    cin >> n >> m;
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    cout << prim() << endl;

    return 0;
}

其中，h数组用于存放每个顶点的第一条边的编号，e数组和ne数组分别存放边的终点和下一条边的编号，w数组存放边的权值，idx表示边的数量。st数组表示一个顶点是否已经加入到了已经生成的树中，dist数组存放当前顶点到已经生成的树中的最短距离。优先队列q用于存放每个顶点到已经生成的树中的最短距离，每次从q中取出距离最小的顶点加入到已经生成的树中。