从图到树：最小生成树

最小生成树是什么

在之前的 文章 中，我们介绍了图的基本概念，以及图跟树的关系。我们知道树其实是特殊的图，树与图相比，节点都是一样，区别无非是在边上做了些限制。

我们现在考虑一个问题，给定一个无向连通有权图 G = (V, E)，需要选出一系列的边，形成一个新的图，这个图依旧连通着之前图上的所有节点，并使得所有边的权重和最小。

先不着急解答这个问题，首先思考一点，假设节点数量是 V，我们需要找到多少条边才能将这些节点组成连通无向图？答案很明显，V - 1，如果不能理解，就想想最简单的链性结构————链表。假设链表的边是无向的，链表节点与节点挨个首尾相连，少了任意一条边，都会导致链表一分为二，无法连通。多出了任何的节点与节点相连的边，都会导致环的形成，这里即使我们去掉环上的某个边，图依然会是连通的。所以，不多不少，我们需要在原图上找到 V - 1 个边。

可以确定，最后的图一定是一颗树，树的边和节点一定满足 E = V - 1 的关系式，并且树上没有环。当然了，这里我们并没有考虑树的其他概念，比如根节点，边的有向性等等，只是单从结构上来说。

最后说说最小生成树的应用，这可就太广了。随便想想都有很多，比如构建一个整体带宽最大的联通网络，规划并建设成本最低的连通道路，如何规划旅行线路等等。

最小生成树算法

在讲具体的算法之前，我们先来感性地认识下问题本身。假设我们已经基于原图构建好了最小生成树，此时多加一个边都会给这个最小生成树带来环，那么我们需要在环上移除一个边，至于移哪个边，肯定是最大，因为移除这个可以使得边的权重和最小。那么再往前一步，当我们在选择边的时候，是不是选择最小的就可以了？这和之前的 Dijkstra 算法 思想如出一辙————贪心算法。

这里我们展示两个最为常见的最小生成树算法，Prim 和 Kruskal。

Prim’s Algorithm

Prim 算法的基本思路和实现与之前的 Dijkstra 算法大差不差。具体思路如下：

1. 在图上选择任意一节点作为起始节点，此时图（树）上就这一个节点，这个节点必然会被连通，也就是说这个节点必然有边与其相连（除非整个图就这一个节点，如果是这样的话，就不用找了，直接提早结束算法）
2. 选择权重最小的边，道理很简单————这是把该节点纳入图的最小开销
3. 每当选择一条边，我们就会把另一个节点纳入图中，同时会有更多的边进入我们的考虑范围，这里我们标记已经被选入的节点
4. 回到步骤 2 重复，直到所有节点被纳入到图中（连通）

由于每次选择一条边，我们都会将两个节点相连，直到所有 V 个节点均被连在一起，最后不多不少，我们只会考虑 V - 1 条边。因而，每个节点只需要对应考虑与其相连的边即可，局部最优就等同于全局最优。

同样也可以使用 反证法 证明这个算法的有效性，假设通过这个算法我们得到了最小生成树，如果现在存在一个边 $ e_i $，这个边可以替换掉最小生成树上的某个边 $ e_j $，使得最小生成树的权重和变小。我们可以先将 $ e_j $ 移除，这样某个节点，假设是 v，必然会和树分离，如果我们将 $ e_i $ 加上，这个 $ e_i $ 必然是要连接到 v 上，否则构建出来的就不是连通图，然而，根据我们的算法 $ e_j $ 是与节点连接权重最小的边，也就是 $ e_j <= e_i $，这和前面的假设自相矛盾，从而说明 $ e_i $ 并不存在，证明此算法有效。

具体代码实现：

class Vertex {
  public Map<Vertex, Integer> adj;  // adjacency vertex to edge's weight
  public boolean visited;
  public int dist;
  public int no;
  public int prev;

  class Vertex(boolean visited, int no) {
    this.visited = visited;
    this.no = no;
  }
}

class VertexCompare implements Comparator<Vertex> {
  public int compare(Vertex s1, Vertex s2) {
    return s1.dist - s2.dist;
  }
}

Vertex[] prim(Vertex[] graph) {
  Vertex[] tree = new Vertex[graph.length];

  for (int i = 0; i < graph.length; i++) {
    tree[i] = new Vertex(false, i);
    v.visited = false;
    v.no = i;
    v.dist = Integer.MAX_VALUE;
  }

  PriorityQueue<Vertex> pq = new PriorityQueue<>(
    new VertexCompare<Vertex>()
  );

  group[0].dist = 0;
  pq.add(group[0]);

  while (!pq.isEmpty()) {
    Vertex cur = pq.poll();

    if (cur.visited) {
      continue;
    }

    // 标记节点
    cur.visited = true;

    // 构建最小生成树
    if (cur.prev != null) {
      tree[cur.no].adj.put( tree[cur.prev.no], cur.dist );
      tree[cur.prev.no].adj.put( tree[cur.no], cur.dist );
    }

    // 将可能的边纳入考虑范围
    for (Vertex n : cur.adj.keySet()) {
      if (!n.visited) {
        n.dist = cur.adj.get(n);
        n.prev = cur;
        pq.add(n);
      }
    }
  }
  return tree;
}

Dijkstra 算法的时间复杂度分析在这里同样奏效，时间复杂度为 O(ElogV)，空间复杂度为 O(E)。

Kruskal’s Algorithm

Dijkstra 以及 Prim 算法都是以节点为出发点来考虑问题，那么我们可不可单单从边来考虑？

我们从小到大依次考虑原图上的边，如果该边的加入没有造成当前构造的最小生成树形成环，那么我们就将其加入，如果形成环，我们就将其丢弃，直到最后我们找到 V - 1 个边连通所有的节点，算法结束。

这个算法的底层思想依旧是贪心————每次只考虑当前最优，通过局部最优我们可以得出全局最优。

同样，可以使用 反证法 证明这个算法的有效性，这里就不过多赘述，可以参照前面 Prim 的方式进行推导证明。

这个算法的实现可以借助 并查集 这个数据结构，关于并查集，有兴趣的话可以看看之前的一篇 文章。这里简单说一下，并查集这个数据结构就是天然用来解决有关连通域问题的。

具体代码实现：

ArrayList<Edge> kruskal(List<Edge> edges, int numVertices) {
  DisjSets ds = new DisjSets(numVertices);
  PriorityQueue<Edge> pq = new PriorityQueue<>(edges);
  List<Edge> mst = new ArrayList<>();

  while (mst.size() != numVertice - 1) {
    Edge e = pq.poll();
    Vertex uSet = ds.find(e.getu());
    Vertex vSet = ds.find(e.getv());

    if (uSet != vSet) {
      mst.add(e);
      ds.union(uSet, vSet);
    }
  }
  return mst;
}

由于优化的并查集的操作复杂度是常数级别的，因此我们可以很容易得到算法的时间复杂度为 O(ElogE)，因为 E = O(V^2)，因此时间复杂度还是 O(ElogV)，这里我们对边进行了考虑，所以空间复杂度依旧是 O(E)。

总结

可以看到，这两个算法的底层思想其实都是贪心，但是他们分别从节点以及与节点相连的边为出发点来考虑，最终殊途同归。