【贪心算法】Kruskal算法的实现与应用

2016-08-14

问题背景

假设我们有n个位置的集合V={v1, v2, ..., vn}，我们想在它们顶部建立一个通信网络，网络应该是连通的，即任何两个位置vi和vj之间至少存在一条路径可以相互到达。对于确定的两个位置(vi,vj)，假设在这两个位置之间建立网络连接的费用为c(i,j)，c(i,j) > 0。将上述问题抽象成一个无向图G=(V,E)，用图来表示可能被建立的链接的集合，图的每个结点代表每个位置，图的每条边e的长度表示该边连接的两个结点vi和vj之间建立网络连接的费用c(i,j)。为了求得最小的建造费用，只需要找到n-1条边将n个结点连接起来并确保图的连通性，然后这n-1条边的权值尽可能小。抽象为图之后上述问题可以用最小生成树模型来解决。

算法描述

Kruskal算法是用于解决最小生成树问题的一种优秀的算法，其主要思路是，先将原图G的所有边按照权值大小进行排序，同时假定我们有一个n个结点，但是还没有边的子图T。每次都从G的边中取出权值最小的边e并尝试加入到子图T中，加入e时需要保持子图T中不能产生环，如果加入e之后会产生环则放弃该边，否则把边e加入子图T。重复这样的操作，直到子图T变成一个连通图时结束算法，对于一个有n个结点的图，等价于在得到n-1条边时就可以结束算法了。Kruskal算法的过程展示图如下所示：

Kruskal算法流程图

算法实现

要实现kruskal算法，先来了解一些背景知识，【图的连通分支】，一个图被分成几个小块，每个小块都是连通的。小块与小块之间不连通，那么每个小块称为一个连通分支。一个孤立结点也算一个连通分支。

下面，还要需要了解一种数据结构，这里我暂且将它称为MergeQuery数据结构。在Kruskal算法中，当考虑一条边e = (u, v)时，我们需要有效地找出包含结点u和v的连通分支。如果两个连通分支不同，u和v位于不同的连通分支，不存在连接结点u和v的路径，此时边e可以加入到最小生成树中。如果连通分支相同，那么u和v处于同一个连通分支中，也就是已经存在一条从u到v路径，此时边e不能加入最小生成树(加入的话会产生环)。接着，我们在考虑如果一条边e连接的结点u和v位于不同的连通分支可以加入的情况，此时将边e加入之后，u和v就连通了，原本u和v所在的两个连通分支也将合并称为一个连通分支。MergeQuery数据结构将用于支持Kruskal算法的相关操作，该数据结构维护不相交的集合(即图的连通分支)，对于一个结点u，操作query(u)返回包含u的集合的名字。若query(u) == query(v)则说明u和v位于同一连通分支。此外还有一个操作merge(A, B)，用于将两个集合合并为一个集合(两个连通分支合并)。在Kruskal算法中，选取权值最小的边e = (u, v)之后，先使用query操作检测u和v是否位于同一连通分支，若是则放弃这条边，如果不是，则加入边e，使用merge(A, B)将u和v所在的两个连通分支合并。

实现MergeQuery的一种简单的数据结构：维护一个数组component，假设图有n个结点{1, 2, ..., n}，创建一个长度为n的component数组，初始化component[i] = i。查找操作query(u)可以用O(1)的时间给出一个结点u所属的集合，合并操作merge(A, B)则需要O(n)的时间来合并两个集合。merge(A, B)的实现如下，任意选择一个保留的集合名，比如选到A，对于另一个集合B中的所有元素i都令component[i] = A。

最后，基于kruskal算法的特点，我们存储一个图的方式将不会使用邻接表或者邻接矩阵，而是直接存储边，具体的数据结构如下所示，重载小于操作符的目的是为了方便对边进行排序。

struct Edge {
  Edge(int vertex1 = 0, int vertex2 = 0, int weight = 0) {
    this->vertex1 = vertex1;
    this->vertex2 = vertex2;
    this->weight  = weight;
  }
  int vertex1, vertex2, weight;
};

bool operator<(const Edge& e1, const Edge& e2) {
  return e1.weight < e2.weight;
}

最后，kruskal算法的整个算法流程的伪代码实现如下所示：

输入为n个结点m条边的图，每条边都带有一个权值w
对所有边按照权值大小进行排序，排序结果为{e1,e2,...,em}
初始化MergeQuery数据结构mq，结点数量为n
minimalSpanningTree = {};
for i=1 to m, do
  A = mq.query(ei.u);
  B = mq.query(ei.v);
  if A != B
    mq.merge(A, B, ei);
    将边ei加入minimalSpanningTree;
  endIf
endFor
return minimalSpanningTree;

整个算法的C++实现如下，下面代码运行之后会输出一个连通图，该图为原图的最小生成树。同时还会输出最小生成树所有边的权值的和。

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_VERTEX_NUM = 10;

struct Edge {
  Edge(int vertex1 = 0, int vertex2 = 0, int weight = 0) {
    this->vertex1 = vertex1;
    this->vertex2 = vertex2;
    this->weight  = weight;
  }
  int vertex1, vertex2, weight;
};

bool operator<(const Edge& e1, const Edge& e2) {
  return e1.weight < e2.weight;
}

class MergeQuery {
public:
  MergeQuery(const int& vertexNum): vertexNum(vertexNum) {
    component = new int[vertexNum];
    for (int i = 0; i < vertexNum; ++i) {
      component[i] = i;
    }
  }
  ~MergeQuery() {
    if (component != NULL)
      delete [] component;
  }
  int query(const int& vertex) const { return component[vertex]; }
  void merge(int A, int B) {
    for (int i = 0; i < vertexNum; ++i) {
      if (component[i] == B)
        component[i] = A;
    }
  }
private:
  int vertexNum;
  int* component;
};

class Kruskal {
public:
  Kruskal(const int& vertexNum, const int& edgeNum) {
    this->vertexNum = vertexNum;
    this->edgeNum   = edgeNum;
    mq = new MergeQuery(vertexNum);
    edges = new Edge[edgeNum];
    minimalSpanningTree = new int[vertexNum-1];
  }
  ~Kruskal() {
    if (mq != NULL)
      delete mq;
    if (edges != NULL)
      delete [] edges;
  }
  void getEdge() {
    for (int i = 0; i < edgeNum; ++i) {
      cin >> edges[i].vertex1 >> edges[i].vertex2 >> edges[i].weight;
    }
  }
  void minimalSpanning() {
    sort(edges, edges + edgeNum);
    int treeEdgeNum = 0;
    for (int i = 0; i < edgeNum; ++i) {
      int A = mq->query(edges[i].vertex1);
      int B = mq->query(edges[i].vertex2);
      if (A != B) {
        mq->merge(A, B);
        minimalSpanningTree[treeEdgeNum++] = i;
      }
    }
  }
  void getTree() {
    int weightSum = 0;
    cout << "最小生成树: (v1, v2, weight)" << endl;
    for (int i = 0; i < vertexNum-1; ++i) {
      weightSum += edges[minimalSpanningTree[i]].weight;
      cout << edges[minimalSpanningTree[i]].vertex1 << ' '
           << edges[minimalSpanningTree[i]].vertex2 << ' '
           << edges[minimalSpanningTree[i]].weight << endl;
    }
    cout << "最小生成树边权值总和为: " << weightSum << endl;
  }
private:
  int vertexNum;
  int edgeNum;
  int* minimalSpanningTree;
  MergeQuery* mq;
  Edge* edges;
};

int main() {
  int vertexNum, edgeNum;
  cin >> vertexNum >> edgeNum;
  if (vertexNum > MAX_VERTEX_NUM) {
    cout << "结点数量过多" << endl;
    return -1;
  }

  Kruskal k(vertexNum, edgeNum);
  k.getEdge(); // 输入图的所有边
  k.minimalSpanning(); // kruskal最小生成树算法
  k.getTree(); // 输出结果

  return 0;
}

Kruskal算法的其他应用—聚类

最大间隔聚类：给定集合U = {p1, p2, ..., pn}，对于每对个体pi和pj，d(pi, pj)表示两个个体之间的距离，规定d(pi, pi)=0，d(pi, pj) > 0(i != j)，并且d(pi, pj) = d(pj, pi)。给定参数k(k <= n)，将U中的个体划分称为k组，则一个U的k聚类是把U分成k个非空集合C1, C2, ..., Ck的划分。我们希望每个聚类内部的点都尽可能地聚集，密集程度尽可能高，而位于两个不同聚类中的点尽可能地相互远离，寻找具有最大可能间隔的k聚类。在此，我们定义一个k聚类的间隔是处在两个不同聚类中的任何一对点之间的距离的最小值，简单点说就是k个聚类里面任意两个聚类之间的距离的最小值，我们希望这个最小值是所有可能的划分中最大的，这样，k个聚类就能最大程度地远离彼此。

最大间隔聚类问题可以使用kruskal算法来解决。把集合U中的个体看成结点，个体之间的距离看成边，在集合U上生成一个具有k个连通分支的图，这k个连通分支就是k个聚类。在生成图的过程中都将邻近点尽可能地一起带入同一个聚类中。通过对前面kruskal算法的理解我们可以知道，算法开始会初始化n个连通分支，然后每次加入一条边就相当于合并两个连通分支，知道最后剩下一个连通分支时就是最小生成树了。那，我们把终止条件修改一下，在使用Kruskal最小生成树算法时，一旦得到k个连通分支就停止算法，由于Kruskal算法每次加入新边时都是考虑权值最小的边，因此，当得到K个连通分支时，还未加入的k-1条边中其实就是最小生成树中距离最大的k-1条边，因此，当去掉这最长的k-1条边时得到的这k个聚类的间隔也是最大的。若图有n个结点，那么最小生成树有n-1边，要在加入最小生成树的最后k-1边时结束算法，那么最后得到的k个连通分支一共有n-k条边，也就是算法在加入n-k条边之后即可停止了。最后算法的伪代码如下所示：

输入n个结点m条边的图，每条边都带有一个权值w
对所有边按照权值大小进行排序，排序结果为{e1,e2,...,em}
初始化MergeQuery数据结构mq，结点数量为n
KCluster = {};
edgeNum = 0;
for i=1 to m && edgeNum != n-k, do
  A = mq.query(ei.u);
  B = mq.query(ei.v);
  if A != B
    mq.merge(A, B, ei);
    将边ei加入KCluster;
    edgeNum = edgeNum + 1;
  endIf
endFor
return KCluster;

可以回顾上面的kruskal算法流程图，假如我们要聚出3个类，那么在进行到(d)这一步即可停止算法了，此时的3个连通分支就是3个最大间隔聚类，{v1, v3}，{v2, v5}，{v4, v6}。