有权图
表示边的类
// 边
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 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();
}
};
};
有权邻接矩阵
// 稠密图 - 邻接矩阵
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();
}
};
};
最小生成树
找v-1条边连接v个顶点总权值最小
针对带权无向图、针对连通图
稀疏图适合kruskal
稠密图适合prim
Lazy Prim O(ElogE)
Prim O(ElogV)
Kruskal O(ElogE)
切分定理
如果一条边的两个端点属于切分不同的两边，这个边称为横切边。
切分定理：给定任意切分，横切边中权值最小的边必然属于最小生成树
Lazy Prim
Lazy Prim的时间复杂度为O(ElogE)
该算法是将一个点的所以边全部扔入最小堆中，接着逐条从堆中取堆顶的边进行判断，再visit
// 使用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算法的优化
Prim算法的时间复杂度为O(ElogV)
// 使用优化的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;
};
};
Kruskal算法
用到并查集，判断两个点是否相连，若将两点相连的边加入最小生成树将会生成环
时间复杂度O(ElogE+ElogV) 即将E条边进行排序ElogE+将E条边取出来判断是否成环ElogV
kruskal较适合稀疏图
// 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;
};
};
