最小生成树_设计资源叔(未授权)

本篇我们会聊聊最小生成树，最小生成树和之前的无向图最大的区别是这个每一条边都是带有权重的。在聊最小生成树之前我们要先聊两个理念，因为最小生成树是基于这两个理念的基础上得到的相关数据结构算法。

小生小生我怕怕鬼片_最小生成树算法_鱼群算法与粒子群算法

首先我们先了解下切分定理。在一幅加权图中，给定任意的切分，他的横切边中权重最小者必然属于图的最小生成树。找个可以想想下要是3个节点形成换的一个节点图最小生成树算法，要是不把最小的边加进去，那么必然要把另外两个节点加入图中而剩下的两条边之和肯定小于最小的边在加上随机一条边，所以可以得到这个定理。

第二是我们常见的一个贪心算法，这个大家都熟所以不细述了。在这里的应用就是找到最小生成树的一条边，不断重复直到找到最小生成树的所有边。

而最小生成树也主要用到了这两种理念，我先找到最小的一条边，生成一副图，然后找所有节点到这副图最小的权重，然后加入这图中最小生成树算法，直至所有节点全部加入为止，这个最小生成树就算完成了，如下图。

现在常用在最小生成树的算法代码是prim算法

package com.jimmysun.algorithms.chapter4_3;

import com.jimmysun.algorithms.chapter1_3.Queue;

import edu.princeton.cs.algs4.IndexMinPQ;

public class Ex22PrimMST {
   private Edge[] edgeTo;
   private double[] distTo;
   private boolean[] marked;
   private IndexMinPQ pq;

   public Ex22PrimMST(EdgeWeightedGraph G) {
      edgeTo = new Edge[G.V()];
      distTo = new double[G.V()];
      marked = new boolean[G.V()];
      for (int v = 0; v < G.V(); v++) {
         distTo[v] = Double.POSITIVE_INFINITY;
      }
      pq = new IndexMinPQ(G.V());

      for (int v = 0; v < G.V(); v++) {
         if (!marked[v]) {
            distTo[v] = 0.0;
            pq.insert(v, 0.0);
            while (!pq.isEmpty()) {
               visit(G, pq.delMin());
            }
         }
      }
   }

   private void visit(EdgeWeightedGraph G, int v) {
      marked[v] = true;
      for (Edge e : G.adj(v)) {
         int w = e.other(v);

         if (marked[w]) {
            continue;
         }
         if (e.weight() < distTo[w]) {
            edgeTo[w] = e;

            distTo[w] = e.weight();
            if (pq.contains(w)) {
               pq.changeKey(w, distTo[w]);
            } else {
               pq.insert(w, distTo[w]);
            }
         }
      }
   }

   public Iterable edges() {
      Queue mst = new Queue();
      for (Edge edge : edgeTo) {
         if (edge != null) {
            mst.enqueue(edge);
         }
      }
      return mst;
   }
}