图的最小生成树

图的生成树

图的生成树是指它的一棵含有其所有的顶点的无环连通子图。

图的最小生成树

最小生成树是指图中所有生成树中的一棵权值（树中所有的边的权值之和）最小的生成树（Minimum Cost Spanning Tree）。它含有图中所有的顶点，但只有足以构成一棵树的n-1条边。一般找到连通图的最小生成树有两种经典算法，Prim算法（普里姆）和Kruskal算法（克鲁斯卡尔）

回路和切分

• 回路 ，如图中实线部分构成一个回路

• 切分集合，一个切分S是顶点集合的一个子集，相应的切分集custset D 是边的一个子集，该集合中每条边都有一个终点在S中。cut s = {1,2,3,4}，cutset D = 2-5,3-6,4-5,4-6,4-7
  

回路和切分的性质

• 假设所有边的权重是不相同的。
• 切分性质，令S是顶点集合的任一子集，并令e是具有最小权重的边，该边的一个节点在点集S中，另一在V-S中，最小生成树必包含e。
• 回路性质，令C是任一一个回路，令f是C中具有最大权重的边，最小生成树一定不包含边f。

Prim算法

以下图为例说明Prim算法
Prim算法代码如下

/*Prim算法生成最小生成树*/
public class Prim {
  public static void prim(Graph graph) {
    Vertex[] vertices = graph.vertexs;
    int size = graph.vertexs.length;
    int[] cutset = new int[size];//切分集
    boolean[] visited = new boolean[size];//标记已经加入最小生成树的顶点
    for (int i = 1; i < size; i++) {
        cutset[i] = Integer.MAX_VALUE;
    }
    for (Edge edge : graph.getAdjEdge(0)) {
        cutset[edge.index] = edge.weight;
    }
    visited[0] = true;
    System.out.println(vertices[0].label);
    for (int i = 1; i < size; i++) {
        int minIndex = getMinVertex(visited, cutset);
        System.out.println(vertices[minIndex].label);
        visited[minIndex] = true;
        for (Edge edge : graph.getAdjEdge(minIndex)) {
            if (visited[edge.index]) {
                continue;
            }
            if (edge.weight < cutset[edge.index]) {
                cutset[edge.index] = edge.weight;
            }
        }
    }
  }
  public static int getMinVertex(boolean[] visited, int[] cutset) {
    int min = Integer.MAX_VALUE;
    int minIndex = 0;
    for (int i = 1; i < cutset.length; i++) {
        if (visited[i]) {
            continue;
        }
        if (cutset[i] < min) {
            min = cutset[i];
            minIndex = i;
        }
    }
    return minIndex;
  }
}

构建图和顶点。

public class MiniSpanTree(){

  public static void main(String[] args) {
    Vertex[] vertexs = {
              new Vertex("1"),
              new Vertex("2"),
              new Vertex("3"),
              new Vertex("4"),
              new Vertex("5"),
              new Vertex("6"),
              new Vertex("7")};
      Graph graph = new Graph(vertexs);
      graph.addEdge(0, 1, 3);
      graph.addEdge(0, 2, 4);
      graph.addEdge(0, 3, 5);

      graph.addEdge(1, 0, 3);
      graph.addEdge(1, 3, 6);
      graph.addEdge(1, 4, 7);

      graph.addEdge(2, 0, 4);
      graph.addEdge(2, 3, 7);
      graph.addEdge(2, 5, 9);

      graph.addEdge(3, 0, 5);
      graph.addEdge(3, 1, 6);
      graph.addEdge(3, 2, 7);
      graph.addEdge(3, 4, 9);
      graph.addEdge(3, 6, 11);
      graph.addEdge(3, 5, 10);

      graph.addEdge(4, 1, 7);
      graph.addEdge(4, 3, 9);
      graph.addEdge(4, 6, 12);

      graph.addEdge(5, 3, 10);
      graph.addEdge(5, 6, 13);
      graph.addEdge(5, 2, 9);

      graph.addEdge(6, 4, 12);
      graph.addEdge(6, 3, 11);
      graph.addEdge(6, 5, 13);

    prim(graph);
  }
}

:::tip
Prim算法是以某个顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树，
:::

Kruskal算法

Kruskal算法构造G的最小生成树的基本思想是：首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权值从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边，如果端点v和w在当前的同一个连通分支中，就跳过，直接查看第k+1条边。这个过程一直进行到只剩下一个连通分支为止。（切分性质）
以下图为例

Kruskal算法代码如下

public static void kruskal(GraphForAdjTable graph) {
  Vertex[] vertexs = graph.vertexs;
  int size = vertexs.length;

  Set<SortEdge> sortEdgeSet = new TreeSet<SortEdge>();
  for (int i = 0; i < size; i++) {
      for (Edge edge : graph.getAdjEdge(i)) {
          sortEdgeSet.add(new SortEdge(i, edge.index, edge.weight));
      }
  }

  int[] cutset = new int[sortEdgeSet.size()]; // 切分集用于保存"已有最小生成树"中每个顶点在该最小树中的终点。
  SortEdge[] rets = new SortEdge[sortEdgeSet.size()];  // 结果数组，保存kruskal最小生成树的边

  List<SortEdge> sortEdgeList = sortEdgeSet.stream().sorted().collect(Collectors.toList());

  int index = 0;
  for (SortEdge sortEdge : sortEdgeList) {
      int m = getEnd(cutset, sortEdge.startIndex);
      int n = getEnd(cutset, sortEdge.endIndex);
      // 如果m!=n，意味着"边index"与"已经添加到最小生成树中的顶点"没有形成环路
      if (m != n) {
          cutset[m] = n;  // 设置m在"已有的最小生成树"中的终点为n
          rets[index++] = sortEdge; // 保存结果
      }
  }
  //打印
  for (int i = 0; i < index; i++) {
      System.out.println(vertexs[rets[i].startIndex].label + "-->" + vertexs[rets[i].endIndex].label);
  }
}

//获取index的终点
private static int getEnd(int[] cutset, int index) {
    while (cutset[index] != 0)
        index = cutset[index];
    return index;
}

定义kruskal要用到的边对象，使用比较器compareTo进行比较，使用hashCode去重。

class SortEdge implements Comparable<SortEdge> {
    public int startIndex;
    public int endIndex;
    public int weight;

    public SortEdge(int startIndex, int endIndex, int weight) {
        this.startIndex = startIndex;
        this.endIndex = endIndex;
        this.weight = weight;
    }

    @Override
    public int compareTo(SortEdge o) {
        return this.weight - o.weight;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        SortEdge sortEdge = (SortEdge) o;
        return startIndex == sortEdge.startIndex && endIndex == sortEdge.endIndex;
    }

    @Override
    public int hashCode() {
        return Objects.hash(startIndex, endIndex);
    }
}

构建图和顶点。

public class MiniSpanTree(){

  public static void main(String[] args) {
    Vertex[] vertexs = {
              new Vertex("1"),
              new Vertex("2"),
              new Vertex("3"),
              new Vertex("4"),
              new Vertex("5"),
              new Vertex("6"),
              new Vertex("7")};
      Graph graph = new Graph(vertexs);
      graph.addEdge(0, 1, 3);
      graph.addEdge(0, 2, 4);
      graph.addEdge(0, 3, 5);

      graph.addEdge(1, 0, 3);
      graph.addEdge(1, 3, 6);
      graph.addEdge(1, 4, 7);

      graph.addEdge(2, 0, 4);
      graph.addEdge(2, 3, 7);
      graph.addEdge(2, 5, 9);

      graph.addEdge(3, 0, 5);
      graph.addEdge(3, 1, 6);
      graph.addEdge(3, 2, 7);
      graph.addEdge(3, 4, 9);
      graph.addEdge(3, 6, 11);
      graph.addEdge(3, 5, 10);

      graph.addEdge(4, 1, 7);
      graph.addEdge(4, 3, 9);
      graph.addEdge(4, 6, 12);

      graph.addEdge(5, 3, 10);
      graph.addEdge(5, 6, 13);
      graph.addEdge(5, 2, 9);

      graph.addEdge(6, 4, 12);
      graph.addEdge(6, 3, 11);
      graph.addEdge(6, 5, 13);

    kruskal(graph);
  }
}

Prim VS Kruskal

• Prim最小生成树
  1. 以连通为主
  2. 选保证连通的代价最小的邻接边(n-1次)
  3. Prim算法的时间复杂度与边无关，为
  4. 适合于求边稠密网的最小生成树
• Kruskal最小生成树
  1. 以最小代价边为主
  2. 添加不行成回路的当前最小代价边
  3. 算法时间复杂度与边相关，为
  4. 适合于求边稀疏网的最小生成树