-
最小生成树-两种算法复杂度比较 poj-1258,2485
2016-08-20 11:37:471.Prim算法 时间是复杂度O(n2),适合稠密图。 例:Poj–1258 题目大意:n个城市建造光缆,要使这些城市直接通信,并且光缆费用最小。 #include #include #define n 10010 #define inf 100010 int a[n][n],ans...1.Prim算法
时间是复杂度O(n2),适合稠密图。
例:Poj–1258
题目大意:n个城市建造光缆,要使这些城市直接通信,并且光缆费用最小。#include <cstdio> #include <string.h> #define n 10010 #define inf 100010 int a[n][n],ans; bool vis[n],t; int dis[n]; bool prim() { memset(vis,0,sizeof(vis)); for(int i=1; i<=t; i++) dis[i]=inf; ans=0; dis[1]=0; for(int i=1; i<=t; i++) { int temp=inf,k=0; for(int j=1; j<=t; j++) { if((vis[j]==0)&&(dis[j]<temp)) { temp =dis[j]; k=j; } } if(temp==n) return false; vis[k]=true; ans+=temp; for(int j=1; j<=t; j++) { if(vis[j]==0&&dis[j]>a[k][j]) dis[j]=a[k][j]; } } return true; } int main() { while(~scanf("%d",&t)) { ans=0; for(int i=1; i<=t; i++) for(int j=1; j<=t; j++) scanf("%d",&a[i][j]); prim(); printf("%d\n",ans); } return 0; }
2.Kruskal算法
时间复杂度O(elog2e),适合简单图。
例如:Poj–2485
题目大意:给定一些地点和连通它们的可以修的公路,每条路有不同长度,求修建一些路使它们连通,并且所有路长度最小。#include <cstdio> #include <string.h> #include <algorithm> using namespace std; #define N 1001 #define inf 1000000001 #define M N*N int t; int e,n,m; int f[N]; struct note { int u,v; int c; note() {} note(int u,int v,int c):u(u),v(v),c(c) {} } p[M]; void add(int u,int v,int c) { p[e++]=note (u,v,c); } int cmp(const void * a,const void * b) { note *aa=(note *)a; note *bb=(note *)b; return aa->c-bb->c; } void made() { int i; for(i=0; i<=n; i++) f[i]=i; } int find(int x) { if(x!=f[x]) f[x]=find(f[x]); return f[x]; } int kru(int n) { qsort(p,e,sizeof(p[0]),cmp); made(); int m=0,ans=0; int i,j; for(i=0; i<e; i++) { int xx=find(p[i].u); int yy=find(p[i].v); if(xx==yy) continue; m++; ans =p[i].c; f[yy]=xx; if(m==n-1) break; } if(m<n-1) return -1; else return ans; } int main() { int i,j,l,c;; scanf("%d",&t); while(t--) { scanf("%d",&n); e=0; for(i=1; i<=n; i++) for(j=1; j<=n; j++) { scanf("%d",&c); add(i,j,c); } printf("%d\n",kru(n)); } return 0; }
-
最小生成树算法总结
2018-10-24 21:07:00最小生成树算法总结 Kruskal算法 Kruskal算法是典型的最小生成树算法,用于计算将所有顶点连通的最小权值。 最常见的问题就是:已知N座城市中任意两座城市之间建造道路所需要的费用,求最少花费多少就可以使得...最小生成树算法总结
Kruskal算法
Kruskal算法是典型的最小生成树算法,用于计算将所有顶点连通的最小权值。
最常见的问题就是:已知N座城市中任意两座城市之间建造道路所需要的费用,求最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达。
算法核心:首先选择最短的边,然后选择次短的边……直到选择n-1条边为止。算法的时间复杂度为O(MlogM),空间复杂度为O(M)。
基本步骤如下:
- 对所有的边按照权值进行从小到大排序。
- 然后每次选取最小的权值,如果和已有点集构成环则跳过,否则加到该点集中,直到选择了n-1条边让整个图连通为止。最终由所有的点集构成的树就是最佳的。
Kruskal算法核心代码:
for (i = 1; i <= m; i++) {//开始从小到大枚举每一条边 //判断一条边的两个顶点是否连通,即判断是否已在同一个集合中 if (merge(e[i].u, e[i].v)) {//如果目前尚未不连通,则选用这条边 counts++; sum += e[i].w; } if (counts == n - 1) //直到选用了n-1条边之后退出循环 break; }
Prim算法
Prim算法是主要解决与边数无关和顶点树有关的算法,适合求解稠密网的最小生成树。
最常见的问题就是:已知N座城市中任意两座城市之间建造道路所需要的费用,求最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达。
算法核心:每在最小生成树集合中加入一个点就需要把这个点与集合外的点比较,不断的寻找两个集合之间最小的边。
算法的时间复杂度为O(N2),空间复杂度为O(N2)。
基本步骤如下:
- 从任意个顶点开始构造生成树,假设就从1号顶点吧。首先将顶点1加入生成树中,用一个一维数组book来标记哪些顶点已经加入了生成树。
- 用数组dis记录生成树到各个顶点的距离。最初生成树中只有1号顶点,有直连边时,数组dis中存储的就是1号顶点到该顶点的边的权值,没有直连边的时候就是无穷大,即初始化dis数组。
- 从数组dis中选出离生成树最近的顶点(假设这个顶点为j)加入到生成树中(即在数组dis中找最小值)。再以j为中间点,更新生成树到每一个非树顶点的距离(就是松弛啦),即如果dis[k]>e[j][k]则更新dis[k]=e[j][k]。
- 重复第3步,直到生成树中有n个顶点为止。
Prim算法核心代码:
//将1号顶点加入生成树 book[1] = 1; //这里用book来标记一个顶点是否已经加入生成树 count++; while (count < n) { min = inf; for (i = 1; i <= n; i++) { if (!book[i] && dis[i] < min) { min = dis[i]; j = i; } } book[j] = 1; count++; sum += dis[j]; //扫描当前顶点j的所有的边,再以j为中间点,更新生成树到每一个非树顶点的距离 for (k = 1; k <= n; k++) { if (!book[k] && dis[k] > e[j][k]) dis[k] = e[j][k]; } }
-
最小生成树算法
2018-10-12 09:34:29利用prim算法实现的最小生成树算法 将集合U划分为A和B两个子集,不断的将连接A,B集合的最小权值的点不断的从B中加入到A中,直到遍历整个集合U。 算法过程: 先选取一个初始点作为集合A,集合B为ADev补集 选取连接...利用prim算法实现的最小生成树算法
将集合U划分为A和B两个子集,不断的将连接A,B集合的最小权值的点不断的从B中加入到A中,直到遍历整个集合U。
算法过程:- 先选取一个初始点作为集合A,集合B为ADev补集
- 选取连接集合A,B的权值最小边,将在集合B中的点添加到集合A中
- 不断的重复上面的过程
算法复杂度O(n*n)
import java.util.Arrays; class Graph{ char[] vexs; int[][] edges; public static final int INF=Integer.MAX_VALUE; public Graph(char[] vexs,int[][] edges) { this.edges=edges; this.vexs=vexs; } public void prim(int start) { if(start<0) return; int len=vexs.length; int[] weights=new int[len]; char[] prims=new char[len]; int index=0; prims[index++]=vexs[start]; for(int i=0;i<len;i++) weights[i]=edges[start][i]; for(int i=0;i<len;i++){ if(i==start) continue; int min=Integer.MAX_VALUE; int minINdex = 0; for(int j=0;j<len;j++){ if(weights[j]!=0&&min>weights[j]){ min=weights[j]; minINdex=j; } } prims[index++]=vexs[minINdex]; weights[minINdex]=0; for(int j=0;j<len;j++){ if(weights[j]!=0&&weights[j]>edges[minINdex][j]) weights[j]=edges[minINdex][j]; } } int sum=0; for(int i=0;i<len-1;i++){ int iIndexA=getPosition(prims[i]); int iIndexB=getPosition(prims[i+1]); sum+=edges[iIndexA][iIndexB]; } //System.out.println(sum); System.out.println(Arrays.toString(prims)); } private int getPosition(char c) { for(int i=0;i<vexs.length;i++) if(vexs[i]==c) return i; return -1; } } public class PrimMethod { private static final int INF = Integer.MAX_VALUE; public static void main(String[] args) { char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; int edges[][] = { /*A*//*B*//*C*//*D*//*E*//*F*//*G*/ /*A*/ { 0, 12, INF, INF, INF, 16, 14}, /*B*/ { 12, 0, 10, INF, INF, 7, INF}, /*C*/ { INF, 10, 0, 3, 5, 6, INF}, /*D*/ { INF, INF, 3, 0, 4, INF, INF}, /*E*/ { INF, INF, 5, 4, 0, 2, 8}, /*F*/ { 16, 7, 6, INF, 2, 0, 9}, /*G*/ { 14, INF, INF, INF, 8, 9, 0}}; Graph graph=new Graph(vexs, edges); graph.prim(0); } }
kruskal算法
算法描述:先将边的权值进行排序,然后将边权从小到大依次操作,判断即将加入的边是否会在树中生成环,将不能生成环的加入到最小生成树中,否则舍弃这条边。
算法复杂度O(elge)e为边的个数class Edge{ int start; int end; int value; public Edge(int start,int end,int value) { this.end=end; this.start=start; this.value=value; } } class Graph1{ char[] vexs; int[][] edges; public Graph1(char[] vexs, int[][] edges) { super(); this.vexs = vexs; this.edges = edges; } int edgeNum; private static final int INF=Integer.MAX_VALUE; public void kruskal() { //System.out.println(Arrays.toString(vexs)); for(int i=0;i<vexs.length;i++) for(int j=i+1;j<vexs.length;j++) if(this.edges[i][j]!=INF) edgeNum++; Edge[] edges=buildEdge(this.edges,edgeNum); //System.out.println(Arrays.toString(this.edges)); sortEdge(edges,0,edges.length-1); //System.out.println(Arrays.toString(edges)); Edge[] resEdge=new Edge[edgeNum]; int index=0; int[] edgeRelation=new int[edgeNum]; for(int i=0;i<edges.length;i++){ int end1=getEnd(edges[i].start,edgeRelation); int end2=getEnd(edges[i].end,edgeRelation); if(end1!=end2){ resEdge[index++]=edges[i]; edgeRelation[end1]=end2; } } for(int i=0;i<resEdge.length;i++) if(resEdge[i]!=null) System.out.println(vexs[resEdge[i].start]+" end="+vexs[resEdge[i].end]); } private void sortEdge(Edge[] edges2,int start,int end) { if(start>=end) return; int mid=(end-start)/2; sortEdge(edges2, start,start+mid ); sortEdge(edges2, start+mid+1, end); merge(edges2,start,start+mid+1,end); } private void merge(Edge[] edges2, int start,int mid,int end) { int tmp=mid,index=0,s=start; Edge[] data=new Edge[end-start+1]; while(start<mid&&tmp<=end){ if(edges2[start].value<=edges2[tmp].value){ data[index++]=edges2[start]; start++; }else{ data[index++]=edges2[tmp]; tmp++; } } while(start<mid){ data[index++]=edges2[start]; start++; } while(tmp<=end){ data[index++]=edges2[tmp]; tmp++; } for(int i=0;i<data.length;i++) edges2[s+i]=data[i]; } private int getEnd(int end, int[] edgeRelation) { while(edgeRelation[end]!=0) end=edgeRelation[end]; return end; } private Edge[] buildEdge(int[][] edges2, int length) { Edge[] edges=new Edge[length]; int index=0,len=edges2.length; for(int i=0;i<len;i++) for(int j=i+1;j<len;j++) if(edges2[i][j]!=Integer.MAX_VALUE) edges[index++]=new Edge(i,j , edges2[i][j]); return edges; } } public class KruskalMethod { private static final int INF=Integer.MAX_VALUE; public static void main(String[] args) { char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; int edges[][] = { /*A*//*B*//*C*//*D*//*E*//*F*//*G*/ /*A*/ { 0, 12, INF, INF, INF, 16, 14}, /*B*/ { 12, 0, 10, INF, INF, 7, INF}, /*C*/ { INF, 10, 0, 3, 5, 6, INF}, /*D*/ { INF, INF, 3, 0, 4, INF, INF}, /*E*/ { INF, INF, 5, 4, 0, 2, 8}, /*F*/ { 16, 7, 6, INF, 2, 0, 9}, /*G*/ { 14, INF, INF, INF, 8, 9, 0}}; Graph1 graph=new Graph1(vexs, edges); graph.kruskal(); } }
-
图论最小生成树算法模板
2020-08-16 16:16:50目录最小生成树算法primkruskal 最小生成树算法 prim 时间复杂度: O(Elog2V) 适用范围: 稠密图 基本思路: 将任一点作为起点,将其所连接的最近的点加入,再从两点所连的点中找到最近的一个加入,依次类推。 模板...最小生成树算法
prim
时间复杂度: O(Elog2V)
适用范围: 稠密图
基本思路: 将任一点作为起点,将其所连接的最近的点加入,再从两点所连的点中找到最近的一个加入,依次类推。
模板:
#include <iostream> #include <vector> #include <queue> using namespace std; #define inf 0x3f3f3f3f #define maxn 110 struct edge { int to; int dis; edge(int to, int dis) : to(to), dis(dis) {} bool operator < (const edge& b)const { return dis > b.dis; } }; vector<edge> G[maxn]; bool vis[maxn]; void prim(int n) { int sum = 0; priority_queue<edge> pq; pq.push(edge(1, 0)); while (!pq.empty()) { edge e = pq.top(); pq.pop(); if (vis[e.to]) { continue; } vis[e.to] = true; for (int i = 0; i < G[e.to].size(); ++i) { if(!vis[G[e.to][i].to]){ pq.push(G[e.to][i]); } } sum += e.dis; } printf("%d\n", sum); } int main() { int n, m; scanf("%d%d", &n, &m); int u, v, w; for (int i = 1; i <= m; ++i) { scanf("%d%d%d", &u, &v, &w); G[u].push_back(edge(v, w)); G[v].push_back(edge(u, w)); } prim(n); return 0; }
kruskal
时间复杂度: O(Elog2E + E)
适用范围: 稀疏图
基本思路: 将边从小到大排好序,若边的两端点不再同一集中(连接不成圈),则将该边加入生成树中。
模板:
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; #define inf 0x3f3f3f3f #define maxm 10010 #define maxn 2010 struct node { int from, to; int dis; node() {} node(int from, int to, int dis) : from(from), to(to), dis(dis) {} bool operator < (const node& b)const { return dis < b.dis; } }edge[maxm]; int s[maxn]; int find(int u) { return s[u] == u ? u : find(s[u]); } void kruskal(int n, int m) { for (int i = 1; i <= n; ++i) { s[i] = i; } sort(edge, edge + m); int sum = 0; for (int i = 0; i < m; ++i) { int a = find(edge[i].from); int b = find(edge[i].to); if (a == b) { continue; } s[a] = b; sum += edge[i].dis; } printf("%d\n", sum); } int main() { int n, m; scanf("%d%d", &n, &m); int u, v, w; for (int i = 0; i < m; ++i) { scanf("%d%d%d", &u, &v, &w); edge[i] = node(u, v, w); } kruskal(n, m); return 0; }
-
prim最小生成树算法原理
2016-05-03 16:51:26prim 最小生成树算法原理 主要需要了解算法的原理、算法复杂度、优缺点 、刻画和度量指标 评价等 可以查阅相关的文献,这部分内容主要整合了两篇博客的内容 分别是:... -
最小生成树 kruskal算法+时间复杂度
2016-10-08 17:34:46Kruskal算法与Prime算法的区别就在于一个是以边为目标进行考虑,一个以点为目标进行考虑。 由于Kruskal算法以边进行考虑,就涉及到边可能属于两个连通块,这时候就涉及到连通块的判断查找合并。 这个知识点属于 ... -
MST最小生成树算法
2017-06-27 16:06:00Kruskal算法: 相对于prim算法,适合于求边稀疏的网的最小生成树 Prim算法: 适合于求边稠密的网的最小生成树 Prim算法: 时间复杂度O(n2) ,与网中的边数无关 假设N=(V,{E})是连通图,TE是N上最小生成... -
Kruskal最小生成树算法
2019-04-11 16:05:53Kruskal最小生成树算法 适用情况 以边为主线贪心搜索,判断连通图时需要用到并查集 时间复杂度为 (n 为边的数量) 思想 ①【边按升序排序】将所有的边从小到大排序,然后依次取边判断是否成环(相连) ②... -
最小生成树算法 Kruskal算法
2019-05-05 16:42:25Prim算法时间复杂度:Elog(V) Kruskal算法时间复杂度:Elog(E) -
b+树时间复杂度_数据结构与算法——最小生成树
2020-11-24 03:13:49而在实际生活中的许多问题都是通过转化为图的这类数据结构来求解的,这就涉及到了许多图的算法研究。例如:在n个城市之间铺设光缆,以保证这n个城市中的任意两个城市之间都可以通信。由于铺设光缆的价格很高,且各个... -
最小生成树 Prime算法 + 时间复杂度
2016-10-08 17:13:03主要就是以点作为目标来考虑, 而不是以边进行考虑。 由于思想一样,所以时间复杂度分析的结果与Dijkstra算法的一模一样。 -
prime算法-最小生成树算法
2015-11-13 20:43:36Prime算法 分类: 算法总结2011-...普利姆算法求最小生成树时候,和边数无关,只和定点的数量相关,所以适合求稠密网的最小生成树,时间复杂度为O(n*n)。 算法过程: 1.将一个图的顶点分为两部分,一部 -
Prim最小生成树算法
2019-04-11 16:59:45Prim最小生成树算法 适用情况 以点为主线贪心搜索,适合与稠密图。 时间复杂度为 O() 思想 ①【初始化(最短距离)】将所有的点分成两个集合,一个是已经被选上的点集(默认有一个起始点);另一个是待选... -
最小生成树算法 1.Prim算法
2018-05-25 19:24:00Prim算法的时间复杂度时O(n^2)的,因此适用于稠密图的最小生成树,如果是稀疏图的情况下采用Kruskal算法更好。 Prim算法蕴含了贪心的思想,其原理是把图中所有的点分成两个集合,一个集合(V)是已经在生成树中的点,... -
最小生成树算法——Kruskal算法
2016-09-05 21:25:23Kruskal算法是求加权连通图中最小生成树的算法。该算法将一个连通图中的边权从小到大排列,然后每次选取边权最小的点,用并查集将几个点合并成一个集合,直到找到第n-1条边为止。 该算法的时间复杂度主要取决于排列... -
数据结构与算法C++之最小生成树问题 Prim
2018-11-29 23:13:48上篇博客中使用Lazy Prim实现的最小生成树算法复杂度为 O(ElogE)O(ElogE)O(ElogE) 下面使用Prim实现最小生成树,算法复杂度为 O(ElogV)O(ElogV)O(ElogV) 使用最小索引堆实现Prim (1)将与节点0相连接的节点的... -
最小生成树算法-prim和kruskal
2021-02-25 11:55:52最小生成树Prim算法适用场景思路模版Kruskal算法适用场景思路模版 Prim算法 适用场景 时间复杂度为O(n2)O(n^2)O(n2),适用于稠密图,按照邻接矩阵存储。 思路 总体思路于dijkstra算法类似,dijkstra算法每次找离原点... -
【图论】最小生成树算法:prim算法和kruskal算法
2020-05-04 23:45:36目录prim算法AC代码堆优化kruskal算法比较 prim算法 复杂度:o(n2)o(n^2)o(n2),n为节点数 prim算法是一种基于贪心的算法,主要流程是:首先,将任意一点...洛谷P3366 模板:最小生成树 先贴下板子: ll prim(){/... -
最小生成树算法:Prim算法和Kruskal算法
2020-06-21 18:23:11最小生成树处理的是无向图 常用算法: Prim算法 O(n²)适合稠密图 Kruskal(克鲁斯卡尔)算法O(mlogm)适合稀疏图 Prim算法 伪代码 dist[i] <- 正无穷 for (i=0; i < n; i++) // 迭代n次,加入n个点 t &... -
最小生成树算法总结【洛谷P3366】
2021-01-02 14:53:43Prim算法是一种以点集为出发点的最小生成树算法,它将无向图G中所有顶点V分成两个子集A、B。初始时,A中只包含一个随机选取的顶点u,其余顶点属于集合B。每次从集合B中选取一个顶点加入顶点A,该顶点是集合B到集合A...
-
动态多目标优化的基于动态环境演化模型的种群多样性维持策略
-
084_可直接用于项目的qt窗口(桑原创).rar
-
物联网基础篇:快速玩转MQTT
-
白话:java从入门到实战
-
C++代码规范和Doxygen根据注释自动生成手册
-
二极管抽运全固态1.319 μm连续锁模激光器
-
sourceTree添加用户
-
在Ubuntu 18.04系统上安装Systemback的方法【在优麒麟系统上亲测可用】
-
MySQL 高可用(DRBD + heartbeat)
-
Keil.STM32F2xx_DFP.2.9.0.1.rar
-
基于单片机的交通灯系统设计--By Kingzd.rar
-
Java获取系统时间的四种方法
-
vue3从0到1-超详细
-
随机电磁光束阵列的光束传输变换特性
-
2021 年该学的 CSS 框架 Tailwind CSS 实战视频
-
vue解决控制http的referer有无
-
2021-02-25
-
Galera 高可用 MySQL 集群(PXC v5.7+Hapro)
-
信号与系统(Python) 学习笔记摘录 (1) 信号简介.pdf
-
PPT大神之路高清教程