算法与数据结构（八） 图论：带权图&最小生成树
2017-09-18 本文已影响283人
天涯明月笙
带权图 Weighted Graph
带权图
边上都有自己的权值的带权图。
邻接矩阵
把原来的1/0变成权值。
邻接表的改造
邻接表
邻接表的点变成键值对。节点的索引：权值。封装成Edge类
为了让邻接表和邻接矩阵有一个统一的接口：Edge。i到j的。
没有边的地方用空。edge中存储一个指针。
代码实现：
// 边
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();
}
};
稠密图编码：
// 稠密图 - 邻接矩阵
template <typename Weight>
class DenseGraph{
private:
int n, m; // 节点数和边数
bool directed; // 是否为有向图
vector<vector<Edge<Weight> *>> g; // 图的具体数据
public:
// 构造函数
DenseGraph( int n , bool directed){
assert( n >= 0 );
this->n = n;
this->m = 0;
this->directed = directed;
// g初始化为n*n的矩阵, 每一个g[i][j]指向一个边的信息, 初始化为NULL
g = vector<vector<Edge<Weight> *>>(n, vector<Edge<Weight> *>(n, NULL));
}
// 析构函数
~DenseGraph(){
for( int i = 0 ; i < n ; i ++ )
for( int j = 0 ; j < n ; j ++ )
if( g[i][j] != NULL )
delete g[i][j];
}
int V(){ return n;} // 返回节点个数
int E(){ return m;} // 返回边的个数
// 向图中添加一个边, 权值为weight
void addEdge( int v, int w , Weight weight ){
assert( v >= 0 && v < n );
assert( w >= 0 && w < n );
// 如果从v到w已经有边, 删除这条边
if( hasEdge( v , w ) ){
delete g[v][w];
if( v != w && !directed )
delete g[w][v];
m --;
}
g[v][w] = new Edge<Weight>(v, w, weight);
if( v != w && !directed )
g[w][v] = new Edge<Weight>(w, v, weight);
m ++;
}
// 验证图中是否有从v到w的边
bool hasEdge( int v , int w ){
assert( v >= 0 && v < n );
assert( w >= 0 && w < n );
return g[v][w] != NULL;
}
// 显示图的信息
void show(){
for( int i = 0 ; i < n ; i ++ ){
for( int j = 0 ; j < n ; j ++ )
if( g[i][j] )
cout<<g[i][j]->wt()<<"\t";
else
cout<<"NULL\t";
cout<<endl;
}
}
// 邻边迭代器, 传入一个图和一个顶点,
// 迭代在这个图中和这个顶点向连的所有边
class adjIterator{
private:
DenseGraph &G; // 图G的引用
int v;
int index;
public:
// 构造函数
adjIterator(DenseGraph &graph, int v): G(graph){
this->v = v;
this->index = -1; // 索引从-1开始, 因为每次遍历都需要调用一次next()
}
~adjIterator(){}
// 返回图G中与顶点v相连接的第一个边
Edge<Weight>* begin(){
// 索引从-1开始, 因为每次遍历都需要调用一次next()
index = -1;
return next();
}
// 返回图G中与顶点v相连接的下一个边
Edge<Weight>* next(){
// 从当前index开始向后搜索, 直到找到一个g[v][index]为true
for( index += 1 ; index < G.V() ; index ++ )
if( G.g[v][index] )
return G.g[v][index];
// 若没有顶点和v相连接, 则返回NULL
return NULL;
}
// 查看是否已经迭代完了图G中与顶点v相连接的所有边
bool end(){
return index >= G.V();
}
};
};
main.cpp:
// 测试有权图和有权图的读取
int main() {
string filename = "testG1.txt";
int V = 8;
cout<<fixed<<setprecision(2);
// Test Weighted Dense Graph
DenseGraph<double> g1 = DenseGraph<double>(V, false);
ReadGraph<DenseGraph<double>,double> readGraph1(g1, filename);
g1.show();
cout<<endl;
// Test Weighted Sparse Graph
SparseGraph<double> g2 = SparseGraph<double>(V, false);
ReadGraph<SparseGraph<double>,double> readGraph2(g2, filename);
g2.show();
cout<<endl;
return 0;
}
稀疏图：
// 稀疏图 - 邻接表
template<typename Weight>
class SparseGraph{
private:
int n, m; // 节点数和边数
bool directed; // 是否为有向图
vector<vector<Edge<Weight> *> > g; // 图的具体数据
public:
// 构造函数
SparseGraph( int n , bool directed){
assert(n >= 0);
this->n = n;
this->m = 0; // 初始化没有任何边
this->directed = directed;
// g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
g = vector<vector<Edge<Weight> *> >(n, vector<Edge<Weight> *>());
}
// 析构函数
~SparseGraph(){
for( int i = 0 ; i < n ; i ++ )
for( int j = 0 ; j < g[i].size() ; j ++ )
delete g[i][j];
}
int V(){ return n;} // 返回节点个数
int E(){ return m;} // 返回边的个数
// 向图中添加一个边, 权值为weight
void addEdge( int v, int w , Weight weight){
assert( v >= 0 && v < n );
assert( w >= 0 && w < n );
// 注意, 由于在邻接表的情况, 查找是否有重边需要遍历整个链表
// 我们的程序允许重边的出现
g[v].push_back(new Edge<Weight>(v, w, weight));
if( v != w && !directed )
g[w].push_back(new Edge<Weight>(w, v, weight));
m ++;
}
// 验证图中是否有从v到w的边
bool hasEdge( int v , int w ){
assert( v >= 0 && v < n );
assert( w >= 0 && w < n );
for( int i = 0 ; i < g[v].size() ; i ++ )
if( g[v][i]->other(v) == w )
return true;
return false;
}
// 显示图的信息
void show(){
for( int i = 0 ; i < n ; i ++ ){
cout<<"vertex "<<i<<":\t";
for( int j = 0 ; j < g[i].size() ; j ++ )
cout<<"( to:"<<g[i][j]->w()<<",wt:"<<g[i][j]->wt()<<")\t";
cout<<endl;
}
}
// 邻边迭代器, 传入一个图和一个顶点,
// 迭代在这个图中和这个顶点向连的所有边
class adjIterator{
private:
SparseGraph &G; // 图G的引用
int v;
int index;
public:
// 构造函数
adjIterator(SparseGraph &graph, int v): G(graph){
this->v = v;
this->index = 0;
}
~adjIterator(){}
// 返回图G中与顶点v相连接的第一个边
Edge<Weight>* begin(){
index = 0;
if( G.g[v].size() )
return G.g[v][index];
// 若没有顶点和v相连接, 则返回NULL
return NULL;
}
// 返回图G中与顶点v相连接的下一个边
Edge<Weight>* next(){
index += 1;
if( index < G.g[v].size() )
return G.g[v][index];
return NULL;
}
// 查看是否已经迭代完了图G中与顶点v相连接的所有顶点
bool end(){
return index >= G.g[v].size();
}
};
};
运行结果
最小生成树问题 Minimum Span Tree
最小生成树
各个节点之间连通，连通总费用最小。
- 针对带权无向图
- 针对连通图（不连通的图，是连通分量。最小森林）
找 V-1 条边
连接V个顶点
总权值最小
切分定理：Cut Property
把图中的节点分成两部分，成为一个切分（cut）
切分
横切边
如果一个边的两个端点，属于切分(Cut)不同的两边，这个边称为横切边(Crossing Edge)。
切分定理：
给定任意切分，横切边中权值最小的边必然属于最小生成树。
证明：
图：两部分
图被分成了两部分。蓝红。横切边。假设红色不是最小权值边。它是最小生成树的一条边。已经生成最小生成树，添加一条边：v+1形成环。
0.4属于
Lazy Prim
所有边中选取出v-1条。
找出四条横切边中最小的
最小堆。把最小边加入后。进行新的切分
新的切分
不断加入最小横切边的点。
不断加入
懒惰：虽然不是横切边，但是没有被扔掉。
直到最后所有节点被访问过。
// 使用Prim算法求图的最小生成树
template<typename Graph, typename Weight>
class LazyPrimMST{
private:
Graph &G; // 图的引用
MinHeap<Edge<Weight>> pq; // 最小堆, 算法辅助数据结构
bool *marked; // 标记数组, 在算法运行过程中标记节点i是否被访问
vector<Edge<Weight>> mst; // 最小生成树所包含的所有边
Weight mstWeight; // 最小生成树的权值
// 访问节点v
void visit(int v){
assert( !marked[v] );
marked[v] = true;
// 将和节点v相连接的所有未访问的边放入最小堆中
typename Graph::adjIterator adj(G,v);
for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() )
if( !marked[e->other(v)] )
pq.insert(*e);
}
public:
// 构造函数, 使用Prim算法求图的最小生成树
LazyPrimMST(Graph &graph):G(graph), pq(MinHeap<Edge<Weight>>(graph.E())){
// 算法初始化
marked = new bool[G.V()];
for( int i = 0 ; i < G.V() ; i ++ )
marked[i] = false;
mst.clear();
// Lazy Prim
visit(0);
while( !pq.isEmpty() ){
// 使用最小堆找出已经访问的边中权值最小的边
Edge<Weight> e = pq.extractMin();
// 如果这条边的两端都已经访问过了, 则扔掉这条边
if( marked[e.v()] == marked[e.w()] )
continue;
// 否则, 这条边则应该存在在最小生成树中
mst.push_back( e );
// 访问和这条边连接的还没有被访问过的节点
if( !marked[e.v()] )
visit( e.v() );
else
visit( e.w() );
}
// 计算最小生成树的权值
mstWeight = mst[0].wt();
for( int i = 1 ; i < mst.size() ; i ++ )
mstWeight += mst[i].wt();
}
// 析构函数
~LazyPrimMST(){
delete[] marked;
}
// 返回最小生成树的所有边
vector<Edge<Weight>> mstEdges(){
return mst;
};
// 返回最小生成树的权值
Weight result(){
return mstWeight;
};
};
运行结果
只关注最小边保存节点的最小边。
最小堆
// 使用优化的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;
// 将和节点v相连接的未访问的另一端点, 和与之相连接的边, 放入最小堆中
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;
};
};
int main() {
string filename = "testG1.txt";
int V = 8;
SparseGraph<double> g = SparseGraph<double>(V, false);
ReadGraph<SparseGraph<double>, double> readGraph(g, filename);
// Test Lazy Prim MST
cout<<"Test Lazy Prim MST:"<<endl;
LazyPrimMST<SparseGraph<double>, double> lazyPrimMST(g);
vector<Edge<double>> mst = lazyPrimMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
cout<<mst[i]<<endl;
cout<<"The MST weight is: "<<lazyPrimMST.result()<<endl;
cout<<endl;
// Test Prim MST
cout<<"Test Prim MST:"<<endl;
PrimMST<SparseGraph<double>, double> primMST(g);
mst = primMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
cout<<mst[i]<<endl;
cout<<"The MST weight is: "<<primMST.result()<<endl;
cout<<endl;
return 0;
}
Kruskal 算法
直接找最小边。未成环就行。
按顺序来，成环的抛弃
使用Union Find快速判断环
// Kruskal算法
template <typename Graph, typename Weight>
class KruskalMST{
private:
vector<Edge<Weight>> mst; // 最小生成树所包含的所有边
Weight mstWeight; // 最小生成树的权值
public:
// 构造函数, 使用Kruskal算法计算graph的最小生成树
KruskalMST(Graph &graph){
// 将图中的所有边存放到一个最小堆中
MinHeap<Edge<Weight>> pq( graph.E() );
for( int i = 0 ; i < graph.V() ; i ++ ){
typename Graph::adjIterator adj(graph,i);
for( Edge<Weight> *e = adj.begin() ; !adj.end() ; e = adj.next() )
if( e->v() < e->w() )
pq.insert(*e);
}
// 创建一个并查集, 来查看已经访问的节点的联通情况
UnionFind uf = UnionFind(graph.V());
while( !pq.isEmpty() && mst.size() < graph.V() - 1 ){
// 从最小堆中依次从小到大取出所有的边
Edge<Weight> e = pq.extractMin();
// 如果该边的两个端点是联通的, 说明加入这条边将产生环, 扔掉这条边
if( uf.isConnected( e.v() , e.w() ) )
continue;
// 否则, 将这条边添加进最小生成树, 同时标记边的两个端点联通
mst.push_back( e );
uf.unionElements( e.v() , e.w() );
}
mstWeight = mst[0].wt();
for( int i = 1 ; i < mst.size() ; i ++ )
mstWeight += mst[i].wt();
}
~KruskalMST(){ }
// 返回最小生成树的所有边
vector<Edge<Weight>> mstEdges(){
return mst;
};
// 返回最小生成树的权值
Weight result(){
return mstWeight;
};
};
// 测试Kruskal算法
int main() {
string filename = "testG1.txt";
int V = 8;
SparseGraph<double> g = SparseGraph<double>(V, false);
ReadGraph<SparseGraph<double>, double> readGraph(g, filename);
// Test Lazy Prim MST
cout<<"Test Lazy Prim MST:"<<endl;
LazyPrimMST<SparseGraph<double>, double> lazyPrimMST(g);
vector<Edge<double>> mst = lazyPrimMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
cout<<mst[i]<<endl;
cout<<"The MST weight is: "<<lazyPrimMST.result()<<endl;
cout<<endl;
// Test Prim MST
cout<<"Test Prim MST:"<<endl;
PrimMST<SparseGraph<double>, double> primMST(g);
mst = primMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
cout<<mst[i]<<endl;
cout<<"The MST weight is: "<<primMST.result()<<endl;
cout<<endl;
// Test Kruskal MST
cout<<"Test Kruskal MST:"<<endl;
KruskalMST<SparseGraph<double>, double> kruskalMST(g);
mst = kruskalMST.mstEdges();
for( int i = 0 ; i < mst.size() ; i ++ )
cout<<mst[i]<<endl;
cout<<"The MST weight is: "<<kruskalMST.result()<<endl;
return 0;
}
运行结果：
运行结果
算法的更多思考
Lazy Prim O( ElogE )
Prim O( ElogV )
Kruskal O( ElogE )
根据算法的具体实现，每次选择一个边
此时，图存在多个最小生成树
Vyssotsky’s Algorithm：
将边逐渐地添加到生成树中
一旦形成环，删除环中权值最大的边.
