当前位置:   article > 正文

最小生成树——Prim算法_prim算法构造最小生成树

prim算法构造最小生成树

目录

基本思想

实现

伪代码

实际问题求解


最小生成树:带权连通图的生成树中 边的权值之和最小的那个生成树。

  • 最小生成树不是唯一的。当图中的各边权值互不相等时,最小生成树是唯一的;
  • 若无向连通图本身是一棵树时(边数比顶点数少1 ),则最小生成树就是它本身。
  • 最小生成树的边数为顶点数减1

基本思想

(找距离最近的结点)

  1. 任选一个结点v1,然后选择离【当前选中结点集合】最近的一个结点v2;
  2. 再选择离【当前选中结点集合{v1,v2}】结点最近的一个结点;依次重复,直到点全部被选中。

  • Prim算法的时间复杂度为O(|V|^2)不依赖于|E|,因此它适用于求解边稠密图的最小生成树。

实现

伪代码

  1. void Prim (G , T ) {
  2. T = 空集 ; //初始化空树
  3. U={w}; //添加任一顶点w
  4. while( (V-U) != 空集 ) { //若树中不含全部顶点
  5. 设 ( u , v ) 是使u∈U 与 v∈(V-U),且权值最小的边;
  6. T=TU{ (u,v) }; //边归入树
  7. U=U U{v); //顶点归入树
  8. }
  9. }

实际问题求解

 [USACO3.1]最短网络 Agri-Net

题目背景:Farmer John 被选为他们镇的镇长!他其中一个竞选承诺就是在镇上建立起互联网,并连接到所有的农场。当然,他需要你的帮助。

题目描述:FJ 已经给他的农场安排了一条高速的网络线路,他想把这条线路共享给其他农场。为了用最小的消费,他想铺设最短的光纤去连接所有的农场。

你将得到一份各农场之间连接费用的列表,你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过10^5

(采用基本Prim算法求解:Kruskal算法求解见专栏)

  1. public class MST {
  2. public int prim(int[][] w){
  3. int n=w.length;
  4. //最小生成树总权值
  5. int result=0;
  6. //加入的顶点集
  7. boolean[] Vex=new boolean[n];
  8. //当前已确定的顶点集到i的最短距离
  9. int[] dis=new int[n];
  10. //初始化
  11. //任选v点开始点
  12. int v=0;
  13. Vex[0]=true;
  14. for (int i = 0; i < n; i++) {
  15. dis[i]=w[v][i];
  16. }
  17. //遍历n次,选n个顶点
  18. for (int l = 0; l < n; l++) {
  19. //选取当前顶点集到其它顶点的最短路径
  20. int temp=-1;
  21. for (int i = 0; i < n; i++) {
  22. if ((!Vex[i])&&(temp==-1||(dis[i]>0&&dis[i]<dis[temp]))){
  23. temp=i;
  24. }
  25. }
  26. if (temp==-1) {
  27. return -1;
  28. }
  29. //将找到的距离最近的顶点加入顶点集
  30. Vex[temp] = true;
  31. v = temp;
  32. result += dis[temp];
  33. //由于顶点集新加入一个顶点,要更新当前已确定的顶点集到i的最短距离
  34. for (int i = 0; i < w.length; i++) {
  35. if ((!Vex[i])&&w[v][i]>0&&w[v][i]<dis[i]){
  36. dis[i]=w[v][i];
  37. }
  38. }
  39. }
  40. return result;
  41. }
  42. public static void main(String[] args) {
  43. Scanner scan=new Scanner(System.in);
  44. int n=scan.nextInt();
  45. int[][] w=new int[n][n];
  46. for (int i = 0; i < w.length; i++) {
  47. for (int j = 0; j < w.length; j++) {
  48. w[i][j]=scan.nextInt();
  49. }
  50. }
  51. System.out.println(new MST().prim(w));
  52. }
  53. }
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小惠珠哦/article/detail/820721
推荐阅读
相关标签
  

闽ICP备14008679号