个人随笔
目录
Java实现图连通网的最小生成树算法之Prim算法
2020-05-08 23:21:50

摘要:图,连通网,最小生成树,Prim算法,Java实现Prim

一、相关概念

首先,我们得理解啥是最小生成树以及图的相关定义

  • 连通图:在无向图中,若任意两个顶点vi与vj都有路径相通,则称该无向图为连通图。
  • 强连通图:在有向图中,若任意两个顶点vi与vj都有路径相通,则称该有向图为强连通图。
  • 连通网:在连通图中,若图的边具有一定的意义,每一条边都对应着一个数,称为权;权代表着连接连个顶点的代价,称这种连通图叫做连通网。
  • 生成树:一个连通图的生成树是指一个连通子图,它含有图中全部n个顶点,但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边,如果生成树中再添加一条边,则必定成环。
  • 最小生成树:在连通网的所有生成树中,所有边的代价和最小的生成树,称为最小生成树。

由上可知,最小生成树是对于连通网的,举个例子,如下所示:

我们知道,最小生成树的算法通常有两种:Kruskal算法Prim算法。这两种算法都是属于贪心算法。这篇博文研究的是Prim算法。

二、最小生成树的形成

怎么找到最小生成树呢,其实不管是Kruskal算法还是Prim算法都是一个原理:找到一条轻量级边,举个简单例子,我们一个联通图的节点集合Q,和他的最小生成树A,那么树A中的节点与集合Q中的权重最小的边就为轻量级边,该轻量级边横跨了集合Q和树A,一定是属于最小生成树的,所以可以把该轻量级边在Q中的节点加入到最小生成树A中。具体原理以及证明请查看:算法导论第三版第六部分图算法最小生成树(625~628页)。因为篇幅原因,这里不做过多说明,总之Kruskal和Prim都是基于这个原理的。

三、Prim算法

Prim算法可以称为是“加点法”,不过本质上还是选择一条轻量级边,它具有的一个性质是集合A中的边总是构成一颗树。这棵树从一个任意的根节点r开始,一直长大到覆盖V中的所有节点位置。算法每一步在连接集合A和A之外的节点的所有边中,选择一条轻量级边加入到A中。本策略属于贪心策略,因为每一步所加入的边都必须是使树的总权重增加量最小的边。

算法伪代码如下:

  1. MST-PRIM(G,w,r)
  2. for each u <- G.V
  3. u.key=∞
  4. u =NIL
  5. r:key=0
  6. Q=G.V
  7. while QO
  8. u=EXTRACT-MIN(Q)
  9. for each v <- G.Adj[u]
  10. if v<-Q and w(u,v)<v.key
  11. v.π=u
  12. v.key=w(u,v)
  13. DECREASE-KEY(Q,v)
  14. A=A∪{u}

在上面的伪代码中,所有不在树A中的节点全部都存放在一个基于key属性的最小优先队列Q中,对于每个节点v,属性v.key保存的是连接v和树中节点所有边中最小权重的边,我们约定若不存在这样子的边,则u.key=∞。属性v.π给出的是节点v在树中的父节点。

举个例子

有如下连通网

根据上面的伪代码来运行

第一步:初始化A和优先队列Q
  1. A={},Q={A,B,C,D,E,F}
  2. A.Key=0;A.π=Nil
  3. B.Key=∞;B.π=Nil
  4. C.Key=∞;C.π=Nil
  5. D.Key=∞;D.π=Nil
  6. E.Key=∞;E.π=Nil
  7. F.Key=∞;F.π=Nil
第二步:从Q中取出A来,更新各个节点到树A的距离,以及保证Q还是优先队列
  1. A={A},Q={C,B,D,E,F}
  2. A.key=0;A.π=NIL
  3. B.key=6;B.π=A
  4. C.key=1;C.π=A
  5. D.key=5;D.π=A
  6. E.key=∞;E.π=NIL
  7. F.key=∞;F.π=NIL
第三步:从Q中取出C来,更新各个节点到树A的距离,以及保证Q还是优先队列
  1. A={A,C},Q={F,B,D,E}
  2. A.key=0;A.π=NIL
  3. C.key=1;C.π=A
  4. B.key=5;B.π=C
  5. D.key=5;D.π=A
  6. E.key=6;E.π=C
  7. F.key=4;F.π=C
第四步:从Q中取出F来,更新各个节点到树A的距离,以及保证Q还是优先队列
  1. A={A,C,F},Q={D,B,E}
  2. A.key=0;A.π=NIL
  3. C.key=1;C.π=A
  4. F.key=4;F.π=C
  5. B.key=5;B.π=C
  6. D.key=2;D.π=F
  7. E.key=6;E.π=C
第五步:从Q中取出D来,更新各个节点到树A的距离,以及保证Q还是优先队列
  1. A={A,C,F,D},Q={B,E}
  2. A.key=0;A.π=NIL
  3. C.key=1;C.π=A
  4. F.key=4;F.π=C
  5. D.key=2;D.π=F
  6. B.key=5;B.π=C
  7. E.key=6;E.π=C
第七步:从Q中取出B来,更新各个节点到树A的距离,以及保证Q还是优先队列
  1. A={A,C,F,DB},Q={E}
  2. A.key=0;A.π=NIL
  3. C.key=1;C.π=A
  4. F.key=4;F.π=C
  5. D.key=2;D.π=F
  6. B.key=5;B.π=C
  7. E.key=3;E.π=B
第八步:从Q中取出E来,更新各个节点到树A的距离,以及保证Q还是优先队列
  1. A={A,C,F,D,B,E},Q={}
  2. A.key=0;A.π=NIL
  3. C.key=1;C.π=A
  4. F.key=4;F.π=C
  5. D.key=2;D.π=F
  6. B.key=5;B.π=C
  7. E.key=3;E.π=B
第九步:Q为空,结束。

由上面可以知道,根据伪代码中的逻辑,成功生产了图的最小生成树,我们现在聊分析下算法的复杂度!

四、Prim算法时间复杂度分析

我们现在来重新砍一下Prim算法,把上面的伪代码拷贝下来

  1. MST-PRIM(G,w,r)
  2. for each u <- G.V
  3. u.key=∞
  4. u =NIL
  5. r:key=0
  6. Q=G.V
  7. while QO
  8. u=EXTRACT-MIN(Q)
  9. for each v <- G.Adj[u]
  10. if v<-Q and w(u,v)<v.key
  11. v.π=u
  12. v.key=w(u,v)
  13. DECREASE-KEY(Q,v)
  14. A=A∪{u}

算法的2~6行是建堆,我们知道最小优先队列的初始化时间成本为O(V)。因为有V个节点,所以while循环要执行V次,从最小优先队列中取出堆顶元素时间成本为O(lgV),所以第8行的总时间成本为O(VlgV)。因为邻接矩阵的边为2E,所以9~13行总执行次数为O(E),在for循环里,我们可以在常数时间里完成对一个节点是否属于Q,方法就是对每个节点维护一个标志位来指明该节点是否属于Q,并在将节点从Q中删除的时候对该标志位进行更新。在算法12行因为改变了节点的key值,所以需要重新建堆,该操作在二叉最小堆上执行的时间成本为O(lgV)。因此第9~13行的总执行时间成本为O(ElgV)。所以Prim算法的总时间代价为O(V+VlgV+ElgV)=O(ElgV)。如果用斐波那契堆来实现最小优先队列Q,Prim算法的渐进运行时间可以进一步得到改善。

五、Java实现

我们这里用Java来实现Prim算法,根据上面的伪代码我们知道,我们需要实现一个最小优先队列,这里用最小堆来实现,代码如下:

  1. /**
  2. *最小堆实现的一个优先队列
  3. * @author suibibk@qq.com
  4. */
  5. class PriorityQueue<E extends Comparable<E>> {
  6. //这里使用数组来实现
  7. private ArrayList<E> data;
  8. public PriorityQueue(int capacity) {
  9. data = new ArrayList<>(capacity);
  10. }
  11. public PriorityQueue() {
  12. data = new ArrayList<>();
  13. }
  14. //返回堆中元素的个数
  15. public int getSize() {
  16. return data.size();
  17. }
  18. //返回二叉树中索引为index的节点的父节点索引
  19. public int parent(int index) {
  20. if(index == 0) {
  21. throw new IllegalArgumentException("index-0 dosen't have parent");
  22. }
  23. return (index-1)/2;
  24. }
  25. //返回完全二叉树中索引为index的节点的左孩子的索引
  26. private int leftChild(int index) {
  27. return index*2+1;
  28. }
  29. //返回完全二叉树中索引为index的节点的右孩子的索引
  30. private int rightChild(int index) {
  31. return index * 2 + 2;
  32. }
  33. //交换索引为i、j的值
  34. private void swap(int i, int j) {
  35. E t = data.get(i);
  36. data.set(i, data.get(j));
  37. data.set(j, t);
  38. }
  39. //向堆中添加元素
  40. public void add(E e) {
  41. data.add(e);
  42. siftUp(data.size() - 1);
  43. }
  44. //上浮
  45. private void siftUp(int k) {
  46. //k不能是根节点,并且k的值要比父节点的值小
  47. while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) > 0) {
  48. swap(k, parent(k));
  49. k = parent(k);
  50. }
  51. }
  52. //看堆中最小的元素
  53. public E findMin() {
  54. if (data.size() == 0)
  55. throw new IllegalArgumentException("Can not findMax when heap is empty");
  56. return data.get(0);
  57. }
  58. //取出堆中最小的元素
  59. public E extractMin() {
  60. E ret = findMin();
  61. swap(0, data.size() - 1);
  62. data.remove(data.size() - 1);
  63. siftDown(0);
  64. return ret;
  65. }
  66. /**
  67. * 当修改了堆中一些元素后,要执行先向下浮再向上浮的操作,这里需要重新建堆
  68. */
  69. public void rebuildHead(E e) {
  70. // 这里优化为在建优先队列的时候,就指定节点在优先队列中的坐标,那么就不需要使用循环
  71. for (int j = 0; j < data.size(); j++) {
  72. if(e==data.get(j)) {
  73. siftDown(j);
  74. siftUp(j);
  75. break;
  76. }
  77. }
  78. }
  79. //下浮
  80. private void siftDown(int k) {
  81. //leftChild存在
  82. while (leftChild(k) < data.size()) {
  83. int j = leftChild(k);
  84. //rightChild存在,且值小于leftChild的值
  85. if (j + 1 < data.size() &&
  86. data.get(j).compareTo(data.get(j + 1)) > 0)
  87. j = rightChild(k);
  88. //data[j]是leftChild和rightChild中最小的
  89. if (data.get(k).compareTo(data.get(j)) <0)
  90. break;
  91. swap(k, j);
  92. k = j;
  93. }
  94. }
  95. //取出堆中最大的元素,替换为元素e
  96. public E replace(E e){
  97. E ret = findMin();
  98. data.set(0, e);
  99. siftDown(0);
  100. return ret;
  101. }
  102. //heapify操作:将数组转化为堆
  103. public PriorityQueue(E[] arrs) {
  104. data = new ArrayList<>(Arrays.asList(arrs));
  105. for (int i = parent(data.size() - 1); i >= 0; i--) {
  106. siftDown(i);
  107. }
  108. }
  109. public void print() {
  110. for (E e : data) {
  111. System.out.print(" "+e);
  112. }
  113. }
  114. public List<E> getDate() {
  115. return data;
  116. }
  117. }

该队列初始化的复杂度为O(V),取出队头的复杂度为O(lgV),重新建堆的复杂度为O(lgV),满足伪代码中的要求。


然后我们需要有一个节点对象,该对象不仅仅是当做图的节点,还要当做树A中的节点以及最小优先队列Q中的节点,所以不仅仅需要节点名称,还需要父节点,以及key属性,以及一个标志位表明是否存在Q中(这是为了让这个判定复杂度变为O(1))。

  1. //图的节点,当然也是最小优先队列Q的节点,也是最小生成树A的节点:因此多了属性key,parent,inQ
  2. class Node implements Comparable<Node>{
  3. private int index;//坐标
  4. private int key;//每个节点的key属性
  5. private String value;//节点名称
  6. private Node parent;//父节点
  7. private int inQ=1;//是否属于Q,默认是属于的,等离开才不属于
  8. @Override
  9. public int compareTo(Node o) {
  10. return this.key-o.key;
  11. }
  12. public Node(String value) {
  13. super();
  14. this.value = value;
  15. }
  16. public int getIndex() {
  17. return index;
  18. }
  19. public void setIndex(int index) {
  20. this.index = index;
  21. }
  22. public int getKey() {
  23. return key;
  24. }
  25. public void setKey(int key) {
  26. this.key = key;
  27. }
  28. public String getValue() {
  29. return value;
  30. }
  31. public void setValue(String value) {
  32. this.value = value;
  33. }
  34. public Node getParent() {
  35. return parent;
  36. }
  37. public void setParent(Node parent) {
  38. this.parent = parent;
  39. }
  40. public int getInQ() {
  41. return inQ;
  42. }
  43. public void setInQ(int inQ) {
  44. this.inQ = inQ;
  45. }
  46. }

然后我们需要一个图对象,可以方便的通过某一个节点找到相邻的节点,这里用的是邻接矩阵来存储图:

  1. //定义图:无向图
  2. class Graph{
  3. //顶点数目
  4. int size;
  5. int index=0;
  6. //顶点
  7. private List<Node> vertexs;
  8. //边
  9. int[][] edges;
  10. //初始化
  11. public Graph(int size) {
  12. this.size=size;
  13. this.vertexs=new ArrayList<Node>(size);
  14. this.edges=new int[size][size];
  15. }
  16. //添加顶点
  17. public void addVertex(Node node) {
  18. node.setIndex(index);
  19. vertexs.add(node);
  20. index++;
  21. }
  22. //添加边:有权重有方向
  23. public void addEdge(Node vertex1,Node vertex2,int weight) {
  24. //因为是无向图,所以这里直接把两条边都加上
  25. edges[vertex1.getIndex()][vertex2.getIndex()]=weight;
  26. edges[vertex2.getIndex()][vertex1.getIndex()]=weight;
  27. }
  28. public List<Node> getVertexs() {
  29. return vertexs;
  30. }
  31. /***************上面已经做好了图,现在做遍历********************/
  32. /**
  33. * 打印图
  34. * @param index
  35. */
  36. public void printGraph() {
  37. System.out.print("图\t ");
  38. for (Node vertex: vertexs) {
  39. System.out.print(vertex.getValue()+"\t");
  40. }
  41. System.out.println("\n");
  42. for (int i = 0; i <size; i++) {
  43. Node vertex = vertexs.get(i);
  44. System.out.print(vertex.getValue()+"\t");
  45. for (int j = 0; j < size; j++) {
  46. System.out.print(edges[i][j]+"\t");
  47. }
  48. System.out.println("\n");
  49. }
  50. System.out.println();
  51. }
  52. /**
  53. * 获取节点index相邻的节点
  54. * @param index
  55. * @return
  56. */
  57. public List<Node> getAdjacentVertexIndex(Node node) {
  58. List<Node> lists = new ArrayList<Node>();
  59. for (int j = 0; j < size; j++) {
  60. if(edges[node.getIndex()][j]!=0) {
  61. lists.add(vertexs.get(j));
  62. }
  63. }
  64. return lists;
  65. }
  66. }

上面都准备好了后,我们就可以根据伪代码中的逻辑来实现最小生成树啦!

  1. public static List<Node> prim(Graph graph){
  2. //1、初始化一个最小优先队列
  3. PriorityQueue<Node> Q = new PriorityQueue<Node>();
  4. //这里第一个顶点的key是0,其他都是Integer.MAX_VALUE 代表无穷
  5. List<Node> nodes = graph.getVertexs();
  6. for (int i = 0; i < nodes.size(); i++) {
  7. Node node = nodes.get(i);
  8. node.setParent(null);
  9. if(i==0) {
  10. node.setKey(0);
  11. }else {
  12. node.setKey(Integer.MAX_VALUE);
  13. }
  14. Q.add(node);
  15. }
  16. //2、初始化生成树A,一开始树A为空,全部节点都还在Q中
  17. List<Node> A = new ArrayList<Node>();
  18. /**
  19. * 上面初始化最小堆的时间复杂度为O(V)
  20. */
  21. //3、开始执行逻辑
  22. while(Q.getSize()!=0) {//这个要执行|V|次
  23. //4、获取第一个节点
  24. Node minNode = Q.extractMin();//这一步的时间复杂度是:O(VlgV)
  25. //5、取出这个节点对应的连接边
  26. List<Node> adjNodes = graph.getAdjacentVertexIndex(minNode);
  27. for (int i = 0; i < adjNodes.size(); i++) {//这里要执行|E|次
  28. //6、检查该节点是否属于集合Q
  29. Node node = adjNodes.get(i);
  30. /**
  31. * 对每个节点维护一个标志位来指明该节点是否属于Q,
  32. * 并在将节点Q从Q中移除的时候将标志位进行更新,时间复杂度则为O(1)
  33. */
  34. if(node.getInQ()==1) {
  35. //7、获取这个邻接边的权重
  36. int weight = graph.edges[minNode.getIndex()][node.getIndex()];
  37. if(weight<node.getKey()) {
  38. //8、更新node的值
  39. node.setParent(minNode);
  40. //这一行操作涉及后面需要重新建堆
  41. node.setKey(weight);
  42. //重新建堆
  43. Q.rebuildHead(node);//这一步的时间复杂度是O(ElgV)
  44. }
  45. }
  46. }
  47. //10,将该节点加入集合A
  48. minNode.setInQ(0);
  49. A.add(minNode);
  50. }
  51. //所以时间复杂度为O(V+VlgV+ElgV)=O(ElgV)=O(ElgV)
  52. return A;
  53. }

好了,到这里就已经实现完了,把代码整合测试下:

Java实现Prim算法

  1. /**
  2. * 连通无向图最小生成树Prim算法Java实现
  3. * @author suibibk@qq.com
  4. */
  5. public class Prim {
  6. public static List<Node> prim(Graph graph){
  7. //1、初始化一个最小优先队列
  8. PriorityQueue<Node> Q = new PriorityQueue<Node>();
  9. //这里第一个顶点的key是0,其他都是Integer.MAX_VALUE 代表无穷
  10. List<Node> nodes = graph.getVertexs();
  11. for (int i = 0; i < nodes.size(); i++) {
  12. Node node = nodes.get(i);
  13. node.setParent(null);
  14. if(i==0) {
  15. node.setKey(0);
  16. }else {
  17. node.setKey(Integer.MAX_VALUE);
  18. }
  19. Q.add(node);
  20. }
  21. //2、初始化生成树A,一开始树A为空,全部节点都还在Q中
  22. List<Node> A = new ArrayList<Node>();
  23. /**
  24. * 上面初始化最小堆的时间复杂度为O(V)
  25. */
  26. //3、开始执行逻辑
  27. while(Q.getSize()!=0) {//这个要执行|V|次
  28. //4、获取第一个节点
  29. Node minNode = Q.extractMin();//这一步的时间复杂度是:O(VlgV)
  30. //5、取出这个节点对应的连接边
  31. List<Node> adjNodes = graph.getAdjacentVertexIndex(minNode);
  32. for (int i = 0; i < adjNodes.size(); i++) {//这里要执行|E|次
  33. //6、检查该节点是否属于集合Q
  34. Node node = adjNodes.get(i);
  35. /**
  36. * 对每个节点维护一个标志位来指明该节点是否属于Q,
  37. * 并在将节点Q从Q中移除的时候将标志位进行更新,时间复杂度则为O(1)
  38. */
  39. if(node.getInQ()==1) {
  40. //7、获取这个邻接边的权重
  41. int weight = graph.edges[minNode.getIndex()][node.getIndex()];
  42. if(weight<node.getKey()) {
  43. //8、更新node的值
  44. node.setParent(minNode);
  45. //这一行操作涉及后面需要重新建堆
  46. node.setKey(weight);
  47. //重新建堆
  48. Q.rebuildHead(node);//这一步的时间复杂度是O(ElgV)
  49. }
  50. }
  51. }
  52. //10,将该节点加入集合A
  53. minNode.setInQ(0);
  54. A.add(minNode);
  55. }
  56. //所以时间复杂度为O(V+VlgV+ElgV)=O(ElgV)=O(ElgV)
  57. return A;
  58. }
  59. /**
  60. * 打印最小生成树的节点A
  61. * @param graph 图 作用是找到节点名称
  62. * @param A
  63. */
  64. public static void printPrim(List<Node> A) {
  65. //这里就已经生成了最小生成树了,遍历输出A
  66. for (int i = 0; i < A.size(); i++) {
  67. Node node = A.get(i);
  68. String vertex = node.getValue();
  69. Node parent = node.getParent();
  70. String pVertex = "NIL";
  71. if(parent!=null) {
  72. pVertex=parent.getValue();
  73. }
  74. System.out.println("节点:"+vertex+";父节点:"+pVertex+";权重:"+node.getKey());
  75. }
  76. }
  77. public static Graph getGraph() {
  78. Graph graph = new Graph(6);
  79. Node A = new Node("A");
  80. Node B = new Node("B");
  81. Node C = new Node("C");
  82. Node D = new Node("D");
  83. Node E = new Node("E");
  84. Node F = new Node("F");
  85. graph.addVertex(A);
  86. graph.addVertex(B);
  87. graph.addVertex(C);
  88. graph.addVertex(D);
  89. graph.addVertex(E);
  90. graph.addVertex(F);
  91. graph.addEdge(A, B,6);
  92. graph.addEdge(A, D,5);
  93. graph.addEdge(A, C,1);
  94. graph.addEdge(B, C,5);
  95. graph.addEdge(C, D,5);
  96. graph.addEdge(B, E,3);
  97. graph.addEdge(D, F,2);
  98. graph.addEdge(C, F,4);
  99. graph.addEdge(E, F,6);
  100. graph.addEdge(E, C,6);
  101. return graph;
  102. }
  103. public static void main(String[] args) {
  104. //获取一个图
  105. Graph graph = getGraph();
  106. graph.printGraph();
  107. //获取该图的最小生成树
  108. List<Node> A = prim(graph);
  109. printPrim(A);
  110. }
  111. }
  112. //图的节点,当然也是最小优先队列Q的节点,也是最小生成树A的节点:因此多了属性key,parent,inQ
  113. class Node implements Comparable<Node>{
  114. private int index;//坐标
  115. private int key;//每个节点的key属性
  116. private String value;//节点名称
  117. private Node parent;//父节点
  118. private int inQ=1;//是否属于Q,默认是属于的,等离开才不属于
  119. @Override
  120. public int compareTo(Node o) {
  121. return this.key-o.key;
  122. }
  123. public Node(String value) {
  124. super();
  125. this.value = value;
  126. }
  127. public int getIndex() {
  128. return index;
  129. }
  130. public void setIndex(int index) {
  131. this.index = index;
  132. }
  133. public int getKey() {
  134. return key;
  135. }
  136. public void setKey(int key) {
  137. this.key = key;
  138. }
  139. public String getValue() {
  140. return value;
  141. }
  142. public void setValue(String value) {
  143. this.value = value;
  144. }
  145. public Node getParent() {
  146. return parent;
  147. }
  148. public void setParent(Node parent) {
  149. this.parent = parent;
  150. }
  151. public int getInQ() {
  152. return inQ;
  153. }
  154. public void setInQ(int inQ) {
  155. this.inQ = inQ;
  156. }
  157. }
  158. //定义图:无向图
  159. class Graph{
  160. //顶点数目
  161. int size;
  162. int index=0;
  163. //顶点
  164. private List<Node> vertexs;
  165. //边
  166. int[][] edges;
  167. //初始化
  168. public Graph(int size) {
  169. this.size=size;
  170. this.vertexs=new ArrayList<Node>(size);
  171. this.edges=new int[size][size];
  172. }
  173. //添加顶点
  174. public void addVertex(Node node) {
  175. node.setIndex(index);
  176. vertexs.add(node);
  177. index++;
  178. }
  179. //添加边:有权重有方向
  180. public void addEdge(Node vertex1,Node vertex2,int weight) {
  181. //因为是无向图,所以这里直接把两条边都加上
  182. edges[vertex1.getIndex()][vertex2.getIndex()]=weight;
  183. edges[vertex2.getIndex()][vertex1.getIndex()]=weight;
  184. }
  185. public List<Node> getVertexs() {
  186. return vertexs;
  187. }
  188. /***************上面已经做好了图,现在做遍历********************/
  189. /**
  190. * 打印图
  191. * @param index
  192. */
  193. public void printGraph() {
  194. System.out.print("图\t ");
  195. for (Node vertex: vertexs) {
  196. System.out.print(vertex.getValue()+"\t");
  197. }
  198. System.out.println("\n");
  199. for (int i = 0; i <size; i++) {
  200. Node vertex = vertexs.get(i);
  201. System.out.print(vertex.getValue()+"\t");
  202. for (int j = 0; j < size; j++) {
  203. System.out.print(edges[i][j]+"\t");
  204. }
  205. System.out.println("\n");
  206. }
  207. System.out.println();
  208. }
  209. /**
  210. * 获取节点index相邻的节点
  211. * @param index
  212. * @return
  213. */
  214. public List<Node> getAdjacentVertexIndex(Node node) {
  215. List<Node> lists = new ArrayList<Node>();
  216. for (int j = 0; j < size; j++) {
  217. if(edges[node.getIndex()][j]!=0) {
  218. lists.add(vertexs.get(j));
  219. }
  220. }
  221. return lists;
  222. }
  223. }
  224. /**
  225. *最小堆实现的一个优先队列
  226. * @author suibibk@qq.com
  227. */
  228. class PriorityQueue<E extends Comparable<E>> {
  229. //这里使用数组来实现
  230. private ArrayList<E> data;
  231. public PriorityQueue(int capacity) {
  232. data = new ArrayList<>(capacity);
  233. }
  234. public PriorityQueue() {
  235. data = new ArrayList<>();
  236. }
  237. //返回堆中元素的个数
  238. public int getSize() {
  239. return data.size();
  240. }
  241. //返回二叉树中索引为index的节点的父节点索引
  242. public int parent(int index) {
  243. if(index == 0) {
  244. throw new IllegalArgumentException("index-0 dosen't have parent");
  245. }
  246. return (index-1)/2;
  247. }
  248. //返回完全二叉树中索引为index的节点的左孩子的索引
  249. private int leftChild(int index) {
  250. return index*2+1;
  251. }
  252. //返回完全二叉树中索引为index的节点的右孩子的索引
  253. private int rightChild(int index) {
  254. return index * 2 + 2;
  255. }
  256. //交换索引为i、j的值
  257. private void swap(int i, int j) {
  258. E t = data.get(i);
  259. data.set(i, data.get(j));
  260. data.set(j, t);
  261. }
  262. //向堆中添加元素
  263. public void add(E e) {
  264. data.add(e);
  265. siftUp(data.size() - 1);
  266. }
  267. //上浮
  268. private void siftUp(int k) {
  269. //k不能是根节点,并且k的值要比父节点的值小
  270. while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) > 0) {
  271. swap(k, parent(k));
  272. k = parent(k);
  273. }
  274. }
  275. //看堆中最小的元素
  276. public E findMin() {
  277. if (data.size() == 0)
  278. throw new IllegalArgumentException("Can not findMax when heap is empty");
  279. return data.get(0);
  280. }
  281. //取出堆中最小的元素
  282. public E extractMin() {
  283. E ret = findMin();
  284. swap(0, data.size() - 1);
  285. data.remove(data.size() - 1);
  286. siftDown(0);
  287. return ret;
  288. }
  289. /**
  290. * 当修改了堆中一些元素后,要执行先向下浮再向上浮的操作,这里需要重新建堆
  291. */
  292. public void rebuildHead(E e) {
  293. // 这里优化为在建优先队列的时候,就指定节点在优先队列中的坐标,那么就不需要使用循环
  294. for (int j = 0; j < data.size(); j++) {
  295. if(e==data.get(j)) {
  296. siftDown(j);
  297. siftUp(j);
  298. break;
  299. }
  300. }
  301. }
  302. //下浮
  303. private void siftDown(int k) {
  304. //leftChild存在
  305. while (leftChild(k) < data.size()) {
  306. int j = leftChild(k);
  307. //rightChild存在,且值小于leftChild的值
  308. if (j + 1 < data.size() &&
  309. data.get(j).compareTo(data.get(j + 1)) > 0)
  310. j = rightChild(k);
  311. //data[j]是leftChild和rightChild中最小的
  312. if (data.get(k).compareTo(data.get(j)) <0)
  313. break;
  314. swap(k, j);
  315. k = j;
  316. }
  317. }
  318. //取出堆中最大的元素,替换为元素e
  319. public E replace(E e){
  320. E ret = findMin();
  321. data.set(0, e);
  322. siftDown(0);
  323. return ret;
  324. }
  325. //heapify操作:将数组转化为堆
  326. public PriorityQueue(E[] arrs) {
  327. data = new ArrayList<>(Arrays.asList(arrs));
  328. for (int i = parent(data.size() - 1); i >= 0; i--) {
  329. siftDown(i);
  330. }
  331. }
  332. public void print() {
  333. for (E e : data) {
  334. System.out.print(" "+e);
  335. }
  336. }
  337. public List<E> getDate() {
  338. return data;
  339. }
  340. }

输入上面的图,运行结果如下:

  1. A B C D E F
  2. A 0 6 1 5 0 0
  3. B 6 0 5 0 3 0
  4. C 1 5 0 5 6 4
  5. D 5 0 5 0 0 2
  6. E 0 3 6 0 0 6
  7. F 0 0 4 2 6 0
  8. 节点:A;父节点:NIL;权重:0
  9. 节点:C;父节点:A;权重:1
  10. 节点:F;父节点:C;权重:4
  11. 节点:D;父节点:F;权重:2
  12. 节点:B;父节点:C;权重:5
  13. 节点:E;父节点:B;权重:3

可以看到结果跟伪代码执行逻辑结果是一样的,大功搞成!要了老命,这篇笔记写了6个钟!

 2111

啊!这个可能是世界上最丑的留言输入框功能~


当然,也是最丑的留言列表

有疑问发邮件到 : suibibk@qq.com 侵权立删
Copyright : 个人随笔   备案号 : 粤ICP备18099399号-2