一、问题
最小生成树解决的问题如下所示:
假设要在 n 个城市之间建立通讯联络网,则连通 n 个城市只需要修建 n-1条线路,如何在最节省经费的前提下建立这个通讯网?
使用Prime算法构造最小生成树,将生成树上的边的权值累加即可得到最小值。
二、Prime算法核心思想
取图中任意一个顶点 v 作为生成树的根,之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边,并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点,直至生成树上含有 n-1 个顶点为止。
动态图演示:
三、算法实现(Java)
import java.util.Scanner; public class Prime { private final static int maxNodeValue=(1<<31)-1; public static void main(String[] args){ Scanner scanner=new Scanner(System.in); int[][] map=new int[101][101]; while(scanner.hasNext()){ init(map); int nodeCount=scanner.nextInt(); int edgeCount=scanner.nextInt(); for(int i=0;i<edgeCount;i++){ int node1=scanner.nextInt(); int node2=scanner.nextInt(); int edgeValue=scanner.nextInt(); map[node1][node2]=edgeValue; map[node2][node1]=edgeValue; } int cost=prime(nodeCount,map); System.out.println(cost); } } public static int prime(int nodeCount,int[][] map){ int[] lowcost=new int[101]; int cost=0; lowcost[1]=-1; for(int i=2;i<=nodeCount;i++){ lowcost[i]=map[1][i]; } for(int i=1;i<=nodeCount-1;i++){ int min=maxNodeValue; int k=0; for(int j=1;j<=nodeCount;j++){ if(min>lowcost[j]&&lowcost[j]!=-1){ min=lowcost[j]; k=j; } } cost+=min; lowcost[k]=-1; for(int j=1;j<=nodeCount;j++){ if(lowcost[j]!=-1&&lowcost[j]>map[k][j]){ lowcost[j]=map[k][j]; } } } return cost; } public static void init(int[][] map){ for(int i=0;i<map.length;i++){ for(int j=0;j<map[i].length;j++){ map[i][j]=maxNodeValue; } } } }
这里使用lowcost数组保存非生成树上的节点到生成树的最小值,每次添加一个节点到生成树,都需要刷新lowcost数组。
四、测试数据
输入
6 10
1 2 6
2 5 3
5 6 6
6 4 2
4 1 5
3 1 1
3 2 5
3 5 6
3 6 4
3 4 5
输出
15
6 10
1 2 6
2 5 3
5 6 6
6 4 2
4 1 5
3 1 1
3 2 5
3 5 6
3 6 4
3 4 5
输出
15
五、ACM
题目链接:http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2144
AC代码:
import java.util.Scanner; import java.util.Map; import java.util.HashMap; public class Main { private final static int maxNodeValue=(1<<31)-1; public static void main(String[] args){ Scanner scanner=new Scanner(System.in); int[][] map=new int[101][101]; while(scanner.hasNext()){ init(map); int nodeCount=scanner.nextInt(); int edgeCount=scanner.nextInt(); for(int i=0;i<edgeCount;i++){ int node1=scanner.nextInt(); int node2=scanner.nextInt(); int edgeValue=scanner.nextInt(); if(map[node1][node2]>edgeValue){ map[node1][node2]=edgeValue; map[node2][node1]=edgeValue; } } int cost=prime(nodeCount,map); System.out.println(cost); } } public static int prime(int nodeCount,int[][] map){ int[] lowcost=new int[101]; int cost=0; lowcost[1]=-1; for(int i=2;i<=nodeCount;i++){ lowcost[i]=map[1][i]; } for(int i=1;i<=nodeCount-1;i++){ int min=maxNodeValue; int k=0; for(int j=1;j<=nodeCount;j++){ if(min>lowcost[j]&&lowcost[j]!=-1){ min=lowcost[j]; k=j; } } cost+=min; lowcost[k]=-1; for(int j=1;j<=nodeCount;j++){ if(lowcost[j]!=-1&&lowcost[j]>map[k][j]){ lowcost[j]=map[k][j]; } } } return cost; } public static void init(int[][] map){ for(int i=0;i<map.length;i++){ for(int j=0;j<map[i].length;j++){ map[i][j]=maxNodeValue; } } } }
这道题目出的实际上并不好,有默认的规则:
- 顶点的个数=最大值,顶点值一定从0开始,依次递增到最大值(顶点的个数)
- 默认从0开始加入生成树
- 默认有可能出现输入相同边两次的情况,这时候取最小值
相关推荐
图论算法:最小生成树——Prim算法和Kruskal算法C 实现
用Kruskal避圈算法求最小生成树的源代码
图论模板 最小生成树,Kruscal算法,采用了并查集技术,外加注释,很通俗易懂的,可以用来解决acm 畅通工程方面的问题
最小生成树是图论中的经典问题,也是一个重要部分,一般书上往往只介绍求最小生成树的算法,而忽略了更精彩的算法应用部分。本文将对最小生成树算法及其应用作全面的分析说明,使大家对此有更加深刻的认识。本文分三...
利用Kruskal避圈算法求解图论中的最小生成树问题
图论中最小生成树算法,使用ruskal进行处理
这是用prim算法实现的最小生成树算法,实质上是一个贪心算法的应用,看一下,会对你有帮助
在分析现有并行Prim算法的基础上,提出了适于GPU架构的压缩邻接表图表示形式,开发了基于GPU的min-reduction数据并行原语,在NVIDIA GPU上设计并实现了基于Prim算法思想的并行最小生成树算法。该算法通过使用原语...
图论 图与网络 最小生成树的两种常用算法 最大流问题 单源和单汇运输网络
本程序是使用c++编写的prim最小生成树算法,需要输入的是graph的阶数以及边赋权图矩阵
图论- 生成树- 最小生成树- Prim.rar
图论- 生成树- 最小生成树- Kruskal.rar
该程序用C实现了最小生成树的prim和kruscal算法,并且也实现了,图的广度遍历和深度遍历,采用了临界矩阵或者是临界表的存储结构。
图论- 生成树- 曼哈顿距离最小生成树.rar
最小生成树:minimum spanning tree 在连通网的所有生成树中,所有边的代价和最小的生成树,称为最小生成树。 Kruskal不是最小生成树的最有效算法,但却是学习图论必不可少的一步。 本代码旨在帮助初学图论的编程...
matlab算法,可以解决最小生成树算法以及类似问题关于最小生成树,学过图论的都懂,这里就不做介绍。 下面是一个例题,附有Kruskal算法和Prim算法。
Prim算法是最小生成树一般算法的特例, Prim算法的特点是集合A的边总是只形成单棵树.
数学建模 图论 课件 最小生成树 广度和深度搜索 matlab 程序 数学建模 图论 课件 最小生成树 广度和深度搜索 matlab 程序 数学建模 图论 课件 最小生成树 广度和深度搜索 matlab 程序 数学建模 图论 课件 最小生成树...
图论- 生成树- 最小瓶颈生成树.rar