2020-2021:teams:namespace:最小生成树
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:namespace:最小生成树 [2020/07/10 17:23] great_designer [Prim算法（反圈法）] |
2020-2021:teams:namespace:最小生成树 [2020/07/10 17:37] (当前版本) great_designer [Prim算法（反圈法）] |
||
|---|---|---|---|
| 行 61: | 行 61: | ||
| 第三步：若在某一步，反圈为空集，则图中没有支撑树。若在某一步，已经选择了图的所有顶点，则所有被选择的边构成最小树，算法终止。 | 第三步：若在某一步，反圈为空集，则图中没有支撑树。若在某一步，已经选择了图的所有顶点，则所有被选择的边构成最小树，算法终止。 | ||
| - | 可以看一个程序示例： | + | 因此可以用优先队列的STL来维护割集（反圈），方法是每次选元素后判断，新堆顶不在割集中就pop掉这个元素。 |
| + | |||
| + | 注意，我们要实现最小堆。默认优先队列是最大堆。因此要想办法颠倒过来。 | ||
| <code C++> | <code C++> | ||
| - | //weights为权重数组、n为顶点个数、src为最小树的第一个顶点、edge为最小生成树边 | + | #include<algorithm> |
| - | + | #include<iostream> | |
| - | void Prim(int weights[][512], int n, int src, int edges[]) | + | #include<cstring> |
| - | { | + | #include<stdio.h> |
| - | int minweight[512],min; | + | #include<math.h> |
| - | int i,j,k; | + | #include<string> |
| - | for(i=0;i<n;i++)//初始化相关数组 | + | #include<stdio.h> |
| + | #include<queue> | ||
| + | #include<stack> | ||
| + | #include<map> | ||
| + | #include<deque> | ||
| + | using namespace std; | ||
| + | struct edge//保存边的情况，to为通往的边，不需要保存from | ||
| + | { | ||
| + | int to; | ||
| + | int v; | ||
| + | friend bool operator<(const edge& x,const edge& y)//优先队列即最小堆 | ||
| { | { | ||
| - | minweight[i]=weights[src][i]; //将src顶点与之有边的权值存入数组 | + | return x.v>y.v; |
| - | edges[i]=src; //初始化第一个顶点为src | + | |
| } | } | ||
| - | minweight[src]=0; //将第一个顶点src顶点加入生成树 | + | }; |
| - | for(i=1;i<n;i++) | + | priority_queue<edge>q; |
| + | int vis[105];//判断是否标记数组 | ||
| + | int p[105][105];//存图 | ||
| + | int n; | ||
| + | int main() | ||
| + | { | ||
| + | int i,j,x,y,d2,d1,s,key; | ||
| + | edge now; | ||
| + | while(scanf("%d",&n)!=EOF) | ||
| { | { | ||
| - | min=32767; | + | for(i=0;i<n;i++) |
| - | for(j=0,k=0;j<n;j++) | + | |
| { | { | ||
| - | if(minweight[j]!=0&&minweight[j]<min)//在数组中找最小值，其下标为k | + | vis[i]=0;//初始化一下 |
| + | for(j=0;j<n;j++) | ||
| { | { | ||
| - | min=minweigth[j]; | + | scanf("%d",&p[i][j]); |
| - | k=j; | + | |
| } | } | ||
| } | } | ||
| - | minweight[k]=0; //找到最小树的一个顶点 | + | s=0; |
| - | for(j=0;j<n;j++) | + | vis[0]=1;//标记起始点 |
| + | key=0;//随便找起始点 | ||
| + | while(!q.empty())q.pop(); | ||
| + | for(i=0;i<n-1;i++)//n-1次 | ||
| { | { | ||
| - | if(minweight[j]!=0;&&weights[k][j]<minweight[j] ) | + | for(j=0;j<n;j++)//记入新加入点的情况 |
| - | { | + | { |
| - | minweight[j]=weights[k][j]; //将小于当前权值的边(k,j)权值加入数组中 | + | if(!vis[j])//没标记过的点就加入全家桶套餐 |
| - | edges[j]=k; //将边(j,k)信息存入边数组中 | + | { |
| - | } | + | now.to=j; |
| - | } | + | now.v=p[key][j]; |
| + | q.push(now); | ||
| + | } | ||
| + | } | ||
| + | while(!q.empty()&&vis[q.top().to])//最小边但是标记过就放弃 | ||
| + | { | ||
| + | q.pop(); | ||
| + | } | ||
| + | if(q.empty()) | ||
| + | break; | ||
| + | now=q.top(); | ||
| + | key=now.to; | ||
| + | s+=now.v;//累加最小边的和 | ||
| + | vis[key]=1; | ||
| + | q.pop(); | ||
| + | } | ||
| + | printf("%d\n",s); | ||
| } | } | ||
| + | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| + | |||
| + | <code C++> | ||
| + | |||
| + | |||
| + | #include <iostream> | ||
| + | #include <queue> | ||
| + | #include <map> | ||
| + | #include <cstring> | ||
| + | using namespace std; | ||
| + | #define maxint 0x3f3f3f3f | ||
| + | #define maxnum 1051 | ||
| + | |||
| + | int link[maxnum][maxnum]; | ||
| + | int c[maxnum][maxnum]; | ||
| + | int sum,n;//sum为最小权之和，n为顶点个数 | ||
| + | |||
| + | struct node | ||
| + | { | ||
| + | int s;//起点 | ||
| + | int e;//终点 | ||
| + | int w;//权 | ||
| + | }; | ||
| + | |||
| + | bool operator < (const node &a,const node &b) | ||
| + | { | ||
| + | return a.w > b.w; | ||
| + | } | ||
| + | |||
| + | void prim(int s) | ||
| + | { | ||
| + | int i,j,k,m,t,u,total; | ||
| + | int vis[maxnum];//标记访问 | ||
| + | memset(vis,0,sizeof(vis));//初始化vis均为0，即未被访问 | ||
| + | priority_queue <node> qq;//声明一个存储node结构体的优先队列 | ||
| + | |||
| + | struct node nn; | ||
| + | |||
| + | total = 1; | ||
| + | vis[s] = 1; | ||
| + | sum = 0; | ||
| + | while(total < n)//遍历所有的顶点 | ||
| + | { | ||
| + | for(i=1;i<link[s][0];i++)//遍历所有和s点相连的边,s点为源点 | ||
| + | { | ||
| + | if(!vis[link[s][i]])//若这个边没被访问，就将其加入优先队列 | ||
| + | { | ||
| + | nn.s = s; | ||
| + | nn.e = link[s][i]; | ||
| + | nn.w = c[s][nn.e]; | ||
| + | qq.push(nn); | ||
| + | } | ||
| + | } | ||
| + | | ||
| + | //这里就是简单处理一下特殊情况 | ||
| + | while(!qq.empty() && vis[qq.top().e])//遇到顶点和集合外的顶点没有相连的 | ||
| + | qq.pop();//刚巧这个点作为终点是最短的，因为这个顶点没背标记过，所以会错误的计入在内 | ||
| + | |||
| + | //将优先队列的队顶元素输出 | ||
| + | nn = qq.top(); | ||
| + | s = nn.e; | ||
| + | sum += nn.w;//队顶的边就是最适合的边，因为优先队列的作用就是对权值进行排序，队顶总是 | ||
| + | //最大或最小的权值的边，又因为没被访问过，所有一定是最适合的 | ||
| + | //cout<<nn.s<<" "<<nn.e<<" "<<nn.w<<endl; | ||
| + | vis[s] = 1;//标记为集合内的元素 | ||
| + | qq.pop(); | ||
| + | total++;//访问的点数加一 | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | int i,j,k; | ||
| + | int line,len; | ||
| + | int t,s,d,p,q; | ||
| + | |||
| + | cin>>n>>line; | ||
| + | |||
| + | for(i=1;i<=n;i++) | ||
| + | { | ||
| + | link[i][0] = 1; | ||
| + | } | ||
| + | |||
| + | for(i=1;i<=line;i++) | ||
| + | { | ||
| + | cin>>p>>q>>len; | ||
| + | c[p][q] = c[q][p] = len; | ||
| + | link[p][link[p][0]++] = q; | ||
| + | link[q][link[q][0]++] = p; | ||
| + | } | ||
| + | |||
| + | cin>>s;//输入起始点 | ||
| + | prim(s); | ||
| + | |||
| + | cout<<sum<<endl; | ||
| + | |||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
2020-2021/teams/namespace/最小生成树.1594373007.txt.gz · 最后更改: 2020/07/10 17:23 由 great_designer
