最小生成树之Prime算法（临接表+优先队列实现）

文章目录

（一）Prime算法（临接表+优先队列实现）1.1 邻接表1.2 优先队列1.3 Prime算法

（一）Prime算法（临接表+优先队列实现）

1.1 邻接表

邻接表，一种存图的方式，用到了c++里面的STL标准模板库里面的vector，vector是一种不定长数组。

#include<vector>头文件 vector<int> v;定义一个int型的动态数组；

但邻接表用到的vector的数据类型是node类型的结构体；

struct node { int to;//他要到达的那个点； int v; node(int x, int y)//对结构体赋值； { to = x; v = y; } };//邻接表 vector<node> v[N];//定义V个链表；

【邻接表的存图思想】：对每个顶点，使用不定长的链表（用vector来实现）来存储从该点出发的所有边的情况，第 i 个链表的第 j 个值就是顶点 i 到顶点 j 的权值。

1.2 优先队列

Prime算法用来解决最小生成树的问题，我们可以想到，它的边的权值是必须从小到大排序的，而优先队列的默认从大到小排序。所以，我们得写一个自定义排序，并且这里的优先队列的数据类型不是int型，而是node结构体类型。

struct node { int to;//他要到达的那个点； int v; node(int x, int y)//对结构体赋值； { to = x; v = y; } };//邻接表 struct cmp { bool operator()(node a, node b) { return a.v > b.v;//a.v的优先级高于b.v，即：从小到大； } }; priority_queue<node, vector<node>, cmp> pq;//升序的优先队列；

1.3 Prime算法

和普通的Prime算法一样，这个算法也需要用到两个数组，一个用来记录到最小生成树的距离。一个用了记录已访问的结点； 先对这两个数组进行初始化：将标记数组全部初始化为0，表示全部为访问；将距离数组初始化为无穷大，表示任意两个结点不联通；

int dis[N];//记录到生成树的最小距离 int vis[N];//标记数组 memset(dis, INf, sizeof(dis));//初始化； memset(vis, 0, sizeof(vis));

以下是用邻接表+优先队列实现Prime算法的难点，我也是刚搞懂，下面只是我的理解，可能有不对的地方； （1）

dis[x] = 0;

[x]表示以任意一个结点开始，即：最小生成树的根节点选取是任意的，我这里选的是0，即：dis[0] = 0;，从0号结点开始构建最小生成树；

（2）

pq.push(node(x, 0));

这里的x和上面的x一样，表示将到达x的结点压入队列。因为刚开始没有结点，它是第一个结点，所以到它的权值是0；

（3）

dis[0] = 0; pq.push(node(0, 0)); while(pq.empty() != 1) { node t = pq.top();//弹出当前优先队列的首元素； pq.pop(); int p = t.to;//它要到达的结点； if (vis[p] == 1) { continue; } vis[p] = 1;//将它到达的结点标记； for (i = 0; i < n; i++) { node x = v[p][i];//定义一个临时结构体变量，代替v进行操作；即p结点到i结点； if (vis[x.to] != 1 && dis[x.to] > x.v) { dis[x.to] = x.v; pq.push(node(x.to, dis[x.to]));//压入队列； } } }

弹出此时的队列中的队首元素(它是一个结点）并删除，如果这个队首元素要达到的结点已经被访问过，终止此次循环，进入下一次循环。如果这个队首元素要达到的结点没有被访问过，则进行以下操作： 标记它要达到的结点，然后定义一个临时的结构体变量代替操作，如果它要达到的结点没有被访问过且它要到达的结点到最小生成树的距离大于它自己到最小生成树的距离，就对dis距离数组进行更新；dis[x.to] = x.v;，并且将这个结点压入队列；pq.push(node(x.to, dis[x.to])); 注意：v[p][i]表示p点指向i点。。。。（好像可以认为它是一个结点） 注意：这里的每个结点包括两个信息：1是它要指向的点；2是它到指向的点的权值； 最后，对dis数组求和，就是最小生成树的值；

完整代码如下：

#include<iostream> #include<cstring> #include<vector> #include<queue> using namespace std; #define INf 0x3f3f3f3f #define N 1000 int dis[N];//记录到生成树的最小距离 int vis[N];//标记数组 struct node { int to;//他要到达的那个点； int v; node(int x, int y)//对结构体赋值； { to = x; v = y; } };//邻接表 struct cmp { bool operator()(node a, node b) { return a.v > b.v;//a.v的优先级高于b.v，即：从小到大； } }; vector<node> v[N];//定义V个链表； int prime(int n) { int i; priority_queue<node, vector<node>, cmp> pq;//升序的优先队列； memset(dis, INf, sizeof(dis));//初始化； memset(vis, 0, sizeof(vis)); dis[0] = 0; pq.push(node(0, 0)); while(pq.empty() != 1) { node t = pq.top();//弹出当前优先队列的首元素； pq.pop(); int p = t.to;//它要到达的结点； if (vis[p] == 1) { continue; } vis[p] = 1;//将它到达的结点标记； for (i = 0; i < n; i++) { node x = v[p][i];//定义一个临时结构体变量，代替v进行操作；即p结点到i结点； if (vis[x.to] != 1 && dis[x.to] > x.v) { dis[x.to] = x.v; pq.push(node(x.to, dis[x.to]));//压入队列； } } } int sum = 0; for (i = 0; i < n; i++) { sum = sum + dis[i]; } return sum; } int main() { int i,j, n, x; cin >> n; for (i = 0; i < n; i++)//对链表进行清空操作； { v[i].clear(); } for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { cin >> x; v[i].push_back(node(j, x));//即:i结点到j结点的权值为x； } } int k = prime(n); cout << k << endl; return 0; }

注意：要对不定长数组v进行清空操作：

for (i = 0; i < n; i++)//对链表进行清空操作； { v[i].clear(); }

例如，这样一幅图：它四个结点，分别是：

0，1，2，3，4

为了便于理解，我们看下面的代码：

#include <iostream> #include <cstdio> #include <vector> #include <queue> using namespace std; const int maxn = 1000; const int inf = 0x3f3f3f3f; int d[maxn];//距离向量 int vis[maxn];//标记数组 int sum; struct node { int to; int cost; node(int t, int c) { to = t; cost = c; } }; struct cmp { bool operator()(node a, node b) { return a.cost > b.cost; } }; vector<node> v[maxn]; void prim(int n) { int i; priority_queue<node, vector<node>, cmp> q;//升序的优先队列； memset(vis, 0, sizeof(vis)); memset(d, inf, sizeof(d)); d[0] = 0; q.push(node(0, 0)); while (q.empty() != 1) { cout << "队列大小："; cout << q.size() << endl; node t = q.top(); q.pop(); cout << "执行删除操作之后的队列大小："; cout << q.size() << endl; int pos = t.to; if (vis[pos] == 1) { continue; } vis[pos] = 1; for (i = 0; i < n;i++) { node x = v[pos][i]; cout <<"起点："<< pos << " " <<"终点："<< i << ":"; cout <<" " << "权值："<<x.cost << endl; if (vis[x.to]!=1 && d[x.to] > x.cost) { d[x.to] = x.cost; q.push(node(x.to, d[x.to])); } } cout << "距离数组d的值："; for (i = 0; i < n; i++) { cout << d[i] << " "; } cout << endl; } sum = 0; for (i = 0; i < n; i++) { sum = sum + d[i]; } } int main() { int i, j, x; int n; cin >> n; for (i = 0; i <= n; i++) { v[i].clear(); } for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { cin >> x; v[i].push_back(node(j, x)); } } prim(n); cout << "最小生成树的值："; cout << sum << endl; return 0; }

输入：

4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0

输出：

4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0 队列大小：1 执行删除操作之后的队列大小：0 起点：0 终点：0: 权值：0 起点：0 终点：1: 权值：4 起点：0 终点：2: 权值：9 起点：0 终点：3: 权值：21 距离数组d的值：0 4 9 21 队列大小：3 执行删除操作之后的队列大小：2 起点：1 终点：0: 权值：4 起点：1 终点：1: 权值：0 起点：1 终点：2: 权值：8 起点：1 终点：3: 权值：17 距离数组d的值：0 4 8 17 队列大小：4 执行删除操作之后的队列大小：3 起点：2 终点：0: 权值：9 起点：2 终点：1: 权值：8 起点：2 终点：2: 权值：0 起点：2 终点：3: 权值：16 距离数组d的值：0 4 8 16 队列大小：4 执行删除操作之后的队列大小：3 队列大小：3 执行删除操作之后的队列大小：2 起点：3 终点：0: 权值：21 起点：3 终点：1: 权值：17 起点：3 终点：2: 权值：16 起点：3 终点：3: 权值：0 距离数组d的值：0 4 8 16 队列大小：2 执行删除操作之后的队列大小：1 队列大小：1 执行删除操作之后的队列大小：0 最小生成树的值：28