Minimum Spanning Tree

最小生成树

基本概念

最小生成树(Minimum Spanning Tree)

最小生成树即一个图其代价最小的生成树，生成树必须包含图中所有顶点，并使图中任意两个顶点之间存在唯一一条路径，设顶点数为n，则生成树的边数为n - 1，对连接顶点的边赋予权重，权重之和最小的生成树即为最小生成树。图的生成树并不是唯一的，最小生成树也是如此(但代价唯一)。

在实际应用中，假如对n个城市铺设电缆，在确保n个城市是连通的情况下，需要n - 1条线路，如果铺设每条电缆的代价都是不一样的，那么如何使得代价最低？最小生成树就用来可以解决这个问题。在下图中，最下面的生成树为最小生成树，它连接了图的所有顶点，也保证了边的权重是最小的。构造最小生成树的算法有多种，本文介绍的是最为广泛的两种:普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。

---

Prime算法

算法思想

Prime算法是通过点来构建最小生成树，对于稠密图，prim比kruskal性能更优。

给定一个连通网 N = (V, {E}) ,其顶点集合为 V ,边集合为 E ,另有顶点集合 U ，初始化为集合 V 中的任意一个顶点作为起始点，边集合 TE ，初始化为空，该集合为最小生成树的边集合。重复以下步骤，直到 U = V 。

从集合 E 中，找到代价最小的一条边 (u,v) ,其中 u 为集合 U 中的顶点，v 为集合 V - U 的顶点，将其加入集合 TE 中，并将顶点 v 纳入集合 U 中。

当 U = V 时， T = {V, {TE}} 为 N 的最小生成树。

示例

我们将所有的顶点划分成两个集合，将一个集合的顶点不断加入到另一个集合中去。初始化 U = {a} , V - U = {b, c, d, e ,f} ,closedge记录着从 U 到 V - U 具有最小代价的边，由于最开始集合 U 只存在 a ，closedge此时记录着的是 b - f 到 a 的代价。

接着从中选取代价最小的边为 {a,d}(1) ，将 d 纳入 U 中，此时 U 为 {a, d} ，我们需要检查的是其余边到 d 的代价有没有小于到 a 的代价，如果有则进行更新，可以发现 {d, e}(4)、{d, f}(5) 、 {d, c}(5) 的代价是小于 {a, c}(8) 、 {a, e}(∞)、{a, f}(∞) 的，进行更新。

从中选取代价最小的边为 {e, d}(4) ,将e纳入U中，此时 U 为 {a, d, e} ，将 {d, c}(5)、{d, f}(5) 更新为 {c, e}(3)、{e, f}(2) 。

选择最小边 {e, f}(2) ,将 f 纳入集合U中,此时集合 U 为 {a, d, e, f} ,本轮没有更新。

选择最小边 {c, e}(3) ，将 c 纳入集合U中，此时集合 U 为 {a, d, e, f, c} ，本轮没有更新。

选择最小边 {a, b}(13) ,将 b 纳入集合 U 中，此时集合 U = V ，最小生成树构造完成。

代码实现

/*
typedef char VerTexType;
typedef int ArcType;
typedef int Status;
typedef struct {
  VerTexType vexs[MAX];//顶点表
  ArcType m[MAX][MAX];//矩阵
  int vexnum, arcnum;//顶点数和边数
}AMG;

typedef struct {
  VerTexType v;
  int lowcost;
}closeDge;
*/

int getMin(const closeDge *close, int size) {
  int min = INT_MAX, idx = -1;
  for (int i = 0 ; i < size ; ++i) {
	//close[i].lowcost == 0 说明已经加入
	if (close[i].lowcost && close[i].lowcost < min) {
	  min = close[i].lowcost;
	  idx = i;
	}
  }
  return idx;
}

void Prim(const AMG *G, VerTexType v) {
  if (!G) return;
  closeDge *close = (closeDge*)malloc(sizeof(closeDge) * G -> vexnum);
  int k = locateVex(G, v);
  close[k].lowcost = 0;
  for (int i = 0 ; i < G -> vexnum ; ++i) {
	if (i != k) {
	  close[i].v = v;
	  close[i].lowcost = G -> m[k][i];
	}
  }
  for (int i = 0 ; i < G -> vexnum - 1 ; ++i) {
	k = getMin(close, G -> vexnum);
	printf("%c ---> %c\n", close[k].v, G -> vexs[k]);
	close[k].lowcost = 0;
	for (int j = 0 ; j < G -> vexnum ; ++j) {
	  if (G -> m[k][j] < close[j].lowcost) {
		close[j].v = G -> vexs[k];
		close[j].lowcost = G -> m[k][j];
	  }
	}
  }
}

运行结果

---

Kruskal算法

算法思想

不同于prime算法，kruskal算法通过找边来构建最小生成树，对于稀疏图，其性能优于prime算法。

给定一个连通网 N = (V, {E}) ,将生成树 T 初始化为 (V, {}) ，即只包含 n 个顶点而无边的非连通图，对边集合 E 进行排序，从小到大选择代价最小的边，如果该边 (v, u) 依附的两个顶点 v 和 u 属于不同的集合，自成连通分量，则将该边加入 T 集合中，否则舍弃该边，重复执行以上步骤，直到 T 集合中所有的顶点都在同一连通分量中。

示例

将图中的所有边从小到大排序，依次选择 {a, d}(1) 、 {e, f}(2) 、 {c, e}(3) 、 {e, d}(4) 加入到 T 中去。

代码实现

/*
typedef struct Edge {
  int begin;
  int end;
  int weight;
  Edge(int b, int e, int w)
  	: begin(b), end(e), weight(w) {}
  friend bool operator<(const Edge &a, const Edge &b) {
	return b.weight < a.weight;
  }
}Edge;
*/

int* initSet(int len) {
  int *set = (int*)malloc(sizeof(int) * len);
  for (int i = 0 ; i < len ; ++i) {
	set[i] = i;
  }
  return set;
}

std::priority_queue<Edge> *initEdge(const AMG *G) {
  std::priority_queue<Edge> *q = new std::priority_queue<Edge>();
  for (int i = 0 ; i < G -> vexnum ; ++i) {
	for (int j = i + 1 ; j < G -> vexnum ; ++j) {
	  if (G -> m[i][j] && G -> m[i][j] != INT_MAX) {
		q -> push(Edge(j, i, G -> m[i][j]));
	  }
	}
  }
  return q;
}

void Kruskal(const AMG *G) {
	if (!G) return;
	int *set = initSet(G -> vexnum);
	std::priority_queue<Edge> *q = initEdge(G);
	int cnt = 0;
	while (cnt != G -> vexnum - 1) {
	  int a = set[q -> top().begin], b = set[q -> top().end];
	  if (a != b) {
		++cnt;
		printf("%c ---> %c\n", G -> vexs[q -> top().end], G -> vexs[q -> top().begin]);
		for (int j = 0 ; j < G -> vexnum ; ++j) {
		  if (set[j] == a) {
			set[j] = b;
		  }
		}
	  }
	  q -> pop();
	}
}

运行结果