快要一整个月没有更新博客了，之前的几周每周都想着要写，但是最后时间还是排不开，最近的状态是一直在写代码，一直在怼工作的需求，顺便刷刷算法题，国庆则是没心没肺的玩了七八天，时间这么一分摊，写博客的时间总是挤不出来，罪过罪过。
其实数据结构的系列一直也没有写到头，之后还打算写一个Leetcode刷题系列，最近刷的题越多，越是感叹某些题目的解法精妙。
今天就接着上个月的来讲讲最小生成树的算法吧。
最小生成树是一副连通加权无向图中一棵权值最小的生成树。最小生成树其实是最小权重生成树的简称。
一个连通图可能有多个生成树。当图中的边具有权值时，总会有一个生成树的边的权值之和小于或等于其他生成树的边的权值之和。广义上而言，对于非联通无向图来说，它的每一连通分量同样有最小生成树。
以有线电视电缆的架设为例，若只能沿着街道布线，则以街道为边，而路口为顶点，其中必然有意最小的生成树能使布线成本最低。
简单点说有几个城市你要设计一个线路，这个线路能走完所有的这几个城市，而且路程最短，这个线路就是最小生成树的含义。
所以从上面的例子可以看出来，最小生成树这个算法，对于解决生活实际问题，是一个很重要的存在。下面我们看看最小生成树的算法：
#include <iostream>
#include <vector>
#include <cassert>
#include "Edge.h"
#include "IndexMinHeap.h"
using namespace std;
// 使用优化的Prim算法求图的最小生成树
template <typename Graph, typename Weight>
class PrimMST {
private:
Graph &G; // 图的引用
IndexMinHeap<Weight> ipq; // 最小索引堆，算法辅助数据结构
vector< Edge<Weight>* > edgeTo; // 访问的点所对应的边，算法辅助数据结构
bool* marked; // 标记数组，在算法运行过程中标记节点i是否被访问
vector< Edge<Weight> > mst; // 最小生成树所包含的所有边
Weight mstWeight; // 最小生成树的权值
// 访问节点v
void visit( int v ) {
assert( !marked[v] );
marked[v] = true;
typename Graph::adjIterator adj(G, v);
for (Edge<Weight>* e = adj.begin(); !adj.end(); e = adj.next()) {
int w = e->other(v);
// 如果另一个端点未被访问
if ( !marked[w] ) {
// 如果从没有考虑过这个端点，直接将这个端点和与之相连的边加入索引堆
if ( !edgeTo[w] ) {
edgeTo[w] = e;
ipq.insert(w, e->wt());
}
// 如果曾经考虑过这个端点，但现在的边比之前的边更短，则进行替换
else if ( e->wt() < edgeTo[w]->wt() ) {
edgeTo[w] = e;
ipq.change(w, e->wt());
}
}
}
}
public:
// 构造函数，使用Prim算法求图的最小生成树
PrimMST(Graph &graph):G(graph), ipq(IndexMinHeap<double>(graph.V())) {
assert( graph.E() >= 1 );
// 算法初始化
marked = new bool[G.V()];
for (int i = 0; i < G.V(); i++) {
marked[i] = false;
edgeTo.push_back(NULL);
}
mst.clear();
// Prim
visit(0);
while( !ipq.isEmpty() ) {
// 使用最小索引堆找出已经访问的边中权值最小的边
// 最小索引堆中存储的是点的索引，通过点的索引找到相对应的边
int v = ipq.extractMinIndex();
assert ( edgeTo[v] );
mst.push_back( *edgeTo[v] );
visit( v );
}
mstWeight = mst[0].wt();
for (int i = 1; i < mst.size(); i++) {
mstWeight += mst[i].wt();
}
}
~PrimMST() {
delete[] marked;
}
vector< Edge<Weight> > mstEdges() {
return mst;
}
Weight result() {
return mstWeight;
}
};
上面的是C++版本的最小生成树Prim MST算法，其中我引进了Edge这个类的数据结构：
#ifndef EDGE_H
#define EDGE_H
#include <iostream>
#include <cassert>
using namespace std;
// 边
template <typename Weight>
class Edge {
private:
int a, b; // 边的两个端点
Weight weight; // 边的权值
public:
// 构造函数
Edge(int a, int b, Weight weight) {
this->a = a;
this->b = b;
this->weight = weight;
}
// 空的构造函数，所有的成员变量都取默认值
Edge() {}
// 析构函数
~Edge() {}
int v() { return a; } // 返回第一个顶点
int w() { return b; } // 返回第二个顶点
Weight wt() { return weight; } // 返回权值
// 给定一个顶点，返回另一个顶点
int other( int x ) {
assert( x == a || x == b);
return x == a ? b : a;
}
// 输出边的信息
friend ostream& operator<<(ostream &os, const Edge &e) {
os << e.a << "-" << e.b << ": " << e.weight;
return os;
}
// 边的大小比较，是对边的权值的大小比较
bool operator<(Edge<Weight>& e) {
return weight < e.wt();
}
bool operator<=(Edge<Weight>& e) {
return weight <= e.wt();
}
bool operator>(Edge<Weight>& e) {
return weight > e.wt();
}
bool operator>=(Edge<Weight>& e) {
return weight >= e.wt();
}
bool operator==(Edge<Weight>& e) {
return weight == e.wt();
}
};
#endif //EDGE_H
接下来放上Java版本:
public class PrimMST<Weight extends Number & Comparable> {
private WeightedGraph<Weight> G; // 图的引用
private IndexMinHeap<Weight> ipq; // 最小索引堆，算法辅助数据结构
private Edge<Weight>[] edgeTo; // 访问的点所对应的边，算法辅助数据结构
private Vector<Edge<Weight>> mst; // 标记数组，在算法运行过程中标记节点i是否被访问
private boolean[] marked; // 最小生成树所包含的所有边
private Number mstWeight; // 最小生成树的权值
// 构造函数，使用Prim算法求图的最小生成树
public PrimMST(WeightedGraph graph) {
G = graph;
assert graph.E() >= 1;
ipq = new IndexMinHeap<Weight>(graph.V());
// 算法初始化
marked = new boolean[G.V()];
edgeTo = new Edge[G.V()];
for (int i = 0; i < G.V(); i++) {
marked[i] = false;
edgeTo[i] = null;
}
mst = new Vector<Edge<Weight>>();
// Prim
visit(0);
while (!ipq.isEmpty()) {
// 使用最小索引堆找出已经访问的边中权值最小的边
// 最小索引堆中存储的是点的索引，通过点的索引找到相对应的边
int v = ipq.extractMinIndex();
assert (edgeTo[v] != null);
mst.add(edgeTo[v]);
visit(v);
}
// 计算最小生成树的权值
mstWeight = mst.elementAt(0).wt();
for (int i = 1; i < mst.size(); i++) {
mstWeight = mstWeight.doubleValue() + mst.elementAt(i).wt().doubleValue();
}
}
// 访问节点v
private void visit(int v) {
assert (!marked[v]);
marked[v] = true;
// 将和节点v相连接的未访问的另一端点，和与之相连接的边，放入最小堆中
for (Object item : G.adj(v)) {
Edge<Weight> e = (Edge<Weight>)item;
int w = e.other(v);
// 如果边的另一个端点未被访问
if (!marked[w]) {
// 如果从没有考虑过这个端点，直接将这个端点和与之相连接的边加入索引堆
if (edgeTo[w] == null) {
edgeTo[w] = e;
ipq.insert(w, e.wt());
}
// 如果曾经考虑过这个端点，但现在的边比之前考虑的边更短，则进行替换
else if (e.wt().compareTo(edgeTo[w].wt()) < 0) {
edgeTo[w] = e;
ipq.change(w, e.wt());
}
}
}
}
// 返回最小生成树的边
Vector<Edge<Weight>> mstEdges() {
return mst;
}
// 返回最小生成树的权值
Number result() {
return mstWeight;
}
其中Edge的数据结构如下:
// 边
public class Edge <Weight extends Comparable> implements Comparable<Edge<Weight>> {
private int a; // 边的两个端点
private int b;
private Weight weight; // 边的权值
public Edge(int a, int b, Weight weight) {
this.a = a;
this.b = b;
this.weight = weight;
}
public Edge(Edge<Weight> e) {
this.a = e.a;
this.b = e.b;
this.weight = e.weight;
}
public int v() {
return a;
} // 返回第一个顶点
public int w() {
return b;
} // 返回第二个顶点
public Weight wt() {
return weight;
} // 返回权值
// 给定一个顶点，返回另一个顶点
public int other(int x) {
assert (x == a || x == b);
return x == a ? b : a;
}
/**
* 输出边的信息
* @return String
*/
public String toString() {
return "" + a + "-" + b + ": " + weight;
}
/**
* 边之间的比较
* @param that 另一个边
* @return Int
*/
public int compareTo(Edge that) {
if (weight.compareTo(that.wt()) < 0) {
return -1;
} else if (weight.compareTo(that.wt()) > 0) {
return +1;
} else {
return 0;
}
}
}
然后只要找到txt格式的测试用例，就能很轻易的测试出我们的最小生成树是否合格。
