深圳市移动端网站建设,网站标题设计ps,小说网站静态页面模板,太原模板建站定制最小生成树算法的实现c
题目链接#xff1a;1584. 连接所有点的最小费用 - 力扣#xff08;LeetCode#xff09;
主要思路#xff1a;使用krusal算法#xff0c;将边的权值进行排序#xff08;从小到大排序#xff09;#xff0c;每次将权值最小且未加入到连通分量中…最小生成树算法的实现c
题目链接1584. 连接所有点的最小费用 - 力扣LeetCode
主要思路使用krusal算法将边的权值进行排序从小到大排序每次将权值最小且未加入到连通分量中的值给加入其中。主要需要使用并查集检查是否在同一个连通分量当中。
class Solution {
public:typedef struct edge{int id; //表示这个点int to; //表示要到达的点int weight;//权重bool operator(edge a) const{return a.weightweight;}}edge;int calcute(vectorint point1,vectorint point2){return abs(point1[0]-point2[0])abs(point1[1]-point2[1]);}int find(int u,vectorint parents){if(parents[u]u){return u;}else{return find(parents[u],parents);}}int find(int u,vectorint parents) //路径压缩后的{while(u!parents[u]){parents[u]parents[parents[u]];uparents[u];}return u;}/*bool is_same_parent(int u,int v){if(find(u)find(v)){return true;}return false;}*/int minCostConnectPoints(vectorvectorint points) {int npoints.size();vectoredge edges;// vectorbool is_valid(n,false);vectorint parents(n,0);for(int i0;in;i){parents[i]i;}for(int i0;in;i){for(int ji1;jn;j){edge temp1;temp1.idi;temp1.toj;temp1.weightcalcute(points[i],points[j]);// edge temp2;// temp2temp1;// temp2.idtemp1.to;// temp2.to temp1.id;edges.push_back(temp1);// edges.push_back(temp2);}}sort(edges.begin(),edges.end());int count0;int ans0;// is_valid[edges[0].id]true;for(int i0;iedges.size();i){int parent1find(edges[i].id,parents);int parent2find(edges[i].to,parents);if(parent1!parent2){parents[parent2]parent1;cout取边edges[i].id-edges[i].to权重为:edges[i].weightendl;ansedges[i].weight;count;}if(countn){break;}}return ans;/*for(int i0;iedges.size();i){cout本点:edges[i].id要到达的点:edges[i].to权重为:edges[i].weightendl;}return 0;*/}
};
使用prime算法做最小生成树
首先要了解什么是链式前向星
前向星是一种特殊的边集数组,我们把边集数组中的每一条边按照起点从小到大排序,如果起点相同就按照终点从小到大排序,
并记录下以某个点为起点的所有边在数组中的起始位置和存储长度,那么前向星就构造好了.
用len[i]来记录所有以i为起点的边在数组中的存储长度.
用head[i]记录以i为边集在数组中的第一个存储位置. 在这里插入图片描述 用链式前向星可以避开排序建立边结构体
struct Edge{int next;int to; //edge[i].to表示第i条边的重点edge[i].next表示与第i条边同起点的下一条边的存储位置int weight;//边的权值
}
另外还有一个数组head[],它是用来表示以i为起点的第一条边存储的位置,实际上你会发现这里的第一条边存储的位置其实在以i为起点的所有边的最后输入的那个编号.
加边函数为void add(int u,int v,int w)
{edge[cnt].w w;edge[cnt].to v;edge[cnt].next head[u];head[u] cnt;
}#include bits/stdc.h
#define INF 0x7f7ff
using namespace std;
int k; //默认初始为0
int head[5010];//由于节点最多为5000个初始化nodes[i]0,node[i]表示以第i个节点为起始点第一次出现的位置
struct node{int to;int weight;int next;
}edges[400010];//由于是无向图要开两倍数组
int n,m;
int ans;
bool vis[5010];//代表该节点是否被访问
int dist[5010];//dis[i]表示已经加入到最小生成树的点到没有加入的点的最短距离
void add(int u,int to,int weight) //实际是逆序的但不影响结果的正确性在此使用的是链式前向星不理解链式前向星的去搜一下前向星相关内容
{edges[k].to to;edges[k].weightweight;edges[k].next head[u];head[u]k;
}
void prime()
{fill(dist1,distn1,INF);dist[1]0;//选择起点为1for(int i1;in;i){int u-1,minnINF;for(int j1;jn;j){if(dist[j]minn!vis[j]) //将距离进行更改且该点要未被访问{uj;minndist[j]; //更新min值}}if(u-1){ans-1;return;}vis[u]true;ansdist[u];for(int jhead[u];j;jedges[j].next){int vedges[j].to;if(!vis[v]dist[v]edges[j].weight) dist[v]edges[j].weight;}}
}
int main()
{cinnm;for(int i0;im;i) //建立{int from,to,weight;cinfromtoweight;add(from,to,weight);add(to,from,weight);}prime();if(ans-1){coutorzendl;}else{coutansendl;}//coutedges[0].from-edges[0].to-edges[0].weightendl;//coutedges[1].from-edges[1].to-edges[1].weightendl;// 请在此输入您的代码return 0;
}
由于每次枚举dist比较花费时间因此可以对其进行优化使用priority_queue来找最短的距离
struct p
{int id,d;bool operator (const p a) const{return a.dd;}
};
void Prime()
{fill(dist1,dist1n,INF);priority_queuep q;p now;now.id1;now.ddist[1]0;q.push(now);while(!q.empty()){p nowq.top();q.pop();int unow.id;if(now.d!dist[u]) continue;vis[u]1;ansdist[u];tot;for(int ihead[u];i;iedge[i].next){int vedge[i].to;if(!vis[v]dist[v]edge[i].w){dist[v]edge[i].w;p nxt;nxt.ddist[v];nxt.idv;q.push(nxt);}}}if(totn) ans-1;
}if(!vis[v]dist[v]edge[i].w){dist[v]edge[i].w;p nxt;nxt.ddist[v];nxt.idv;q.push(nxt);}}
}
if(totn) ans-1;}
