全球做的比较好的网站,平台营销型网站建设,秦皇岛网络编辑网站,wordpress主题chuxia算法之最小生成树
最小生成树
概念#xff1a;
最小生成树是一颗连接图G所有顶点的边构成的一颗权最小的树#xff0c;最小生成树一般是在无向图中寻找。最小生成树共有N-1条边(N为顶点数)。
算法#xff1a;
Prim算法
概念#xff1a;
Prim(普里姆)算法是生成最小生…算法之最小生成树
最小生成树
概念
最小生成树是一颗连接图G所有顶点的边构成的一颗权最小的树最小生成树一般是在无向图中寻找。最小生成树共有N-1条边(N为顶点数)。
算法
Prim算法
概念
Prim(普里姆)算法是生成最小生成树的一种算法该算法基本上和求最短路径的Dijkstra算法一样具体操作选取一个顶点作为树的根节点v1然后从这个顶点发散找到其邻接顶点(加入队列中)然后选取根节点到邻接顶点中权最小的路径(也就是连接该路径的另一个顶点)进行添加到树中(也将连接的顶点除去v1的顶点的邻接顶点加入队列中)然后初步形成一个图为u然后再按顺序的查找图u与队列中的顶点的最小路径并加入树中重复操作。最小生成树信息打印打印树中边的顶点对组。
实现代码
使用优先队列
void Prim(int v){an[v].dist0;//使用优先队列,定义参数数据类型容器类型比较方法priority_queuepairint,int,vectorpairint,int,greaterpairint,intq;//pairint,int对组的第一个为权第二个为顶点。q.push(make_pair(0,v));while (!q.empty()){int wq.top().second;q.pop();listnode* pan[w].next;if(an[w].flag) continue;while (p! nullptr){//选取最小权的边而不是顶点到顶点的最短距离if(p-weightan[p-data].dist!an[p-data].flag){an[p-data].distp-weight;an[p-data].pathw;q.push(make_pair(p-weight,p-data));}pp-next;}an[w].flag true;}int w0; //记录最小生成树的总权for(int i1;ivnum;i){if(an[i].path!0){if(ian[i].path)cout(an[i].path,i) 权:an[i].distendl;elsecout(i,an[i].path) 权:an[i].distendl;wan[i].dist;}}cout总权:w;coutendl;}使用vector容器模拟优先队列
struct edge{int v; //顶点int weight; //权
};
static bool cmp(const edge a,const edge b){return b.weighta.weight;}void Prim(int v){an[v].dist0;vectoredgeq;q.push_back({v,0});while (!q.empty()){sort(q.begin(),q.end(),cmp);int wq.back().v;q.pop_back();listnode* pan[w].next;if(an[w].flag) continue;while (p! nullptr){//选取最小权的边而不是顶点到顶点的最短距离if(p-weightan[p-data].dist!an[p-data].flag){an[p-data].distp-weight;an[p-data].pathw;q.push_back({p-data,p-weight});}pp-next;}an[w].flag true;}int w0; //记录最小生成树的总权for(int i1;ivnum;i){if(an[i].path!0){if(ian[i].path)cout(an[i].path,i) 权:an[i].distendl;elsecout(i,an[i].path) 权:an[i].distendl;wan[i].dist;}}cout总权:w;coutendl;}Kruskal算法
概念
Kruskal(克鲁斯卡尔)算法是连续地按照最小的权选择边并且当所选的边不产生圈时就把它作为最小生成树中的边。该算法是在处理一个森林–树的集合。开始的时候存在|V|棵单节点树而添加一边则将两棵树合并成一颗树。当算法终止时就只有一棵树就是最小生成树。
并查集 并合并查查询连通关系集形成集合用于处理连通性问题。 并查集集合中的元素组织成树的形式 查找两个元素是否属于同一集合所在树的根结点是否相同 合并两个集合——将一个集合的根结点作为另一个集合根结点的孩子
具体操作
该算法是根据选取边来进行生成最小生成树那么我们就将图的信息用一个边集结构表示我们需要进行一个循环循环条件就是当最小生成树的边达到N-1条时就退出(N为元素个数)每次循环我们都需要选取最小权重的边并且判断在树中加入这条边会不会形成圈如果形成圈就不进行加入直到树的边条数达到N-1就形成了最小生成树。该算法的关键是判断在树中加入边会不会形成圈–也就是判断两个顶点是否位于两个连通分量这就需要并查集的操作在图中我们将每个顶点都当作一个集合我们插入边的时候直接判断这两个顶点是否处于一个集合中如何是一个集合就不进行加入如果不是一个集合就需要将两个集合进行合并那么这就需要一个存储每个节点的根(父亲)节点的数组parent。我们将parent每个连通分量(集合)进行初始化为-1表示没有父亲。
实现代码
struct edge{int u,v,w; //uv为顶点的w为权重,u为起始点v为终点
};static bool cmp(const edge a,const edge b){return a.wb.w;}int findroot(int v,int parent[]){int tv;while (parent[t]-1){ //查找该集合的根节点。tparent[t];}return t;}void Kruskal(int v){vectoredgeq;//存储每个连通变量的父亲节点的数组int parent[vnum1];int w0; //记录最小生成树的总权memset(parent,-1, sizeof(int)*(vnum1));//生成边集数组。for(int i1;ivnum;i) {listnode *p an[i].next;while (p ! nullptr) {if(ip-data)q.push_back({i, p-data, p-weight});p p-next;}}//进行排序将最小权边放入第一位。sort(q.begin(),q.end(), cmp);for(int i0,num0;numvnum-1;i){int v1findroot(q[i].u,parent);int v2 findroot(q[i].v,parent);//判断祖先节点是否相等--判断是否在一个集合.if(v1!v2){cout(q[i].u,q[i].v) 权:q[i].wendl;wq[i].w;parent[v2]v1; //合并集合。num;}}cout总权:w;coutendl;}尾言
完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看或者在github库中自取(包含源代码) 博客1 codebooks.xyz博客2moonfordream.github.iogithub项目地址Data-Structure-and-Algorithms
