算法与数据结构（八）图论：带权图&最小生成树

作者: 天涯明月笙 | 来源:发表于2017-09-18 11:47 被阅读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：

将边逐渐地添加到生成树中
一旦形成环，删除环中权值最大的边.

算法与数据结构（八）图论：带权图&最小生成树

带权图 Weighted Graph

最小生成树问题 Minimum Span Tree

Lazy Prim

Kruskal 算法

算法的更多思考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据结构与算法

数据结构与算法

C语言

程序员

C++

数据结构和算法分析

算法与数据结构（八） 图论：带权图&最小生成树

带权图 Weighted Graph

最小生成树问题 Minimum Span Tree

Lazy Prim

Kruskal 算法

算法的更多思考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据结构与算法

数据结构与算法

C语言

程序员

C++

数据结构和算法分析

算法与数据结构（八）图论：带权图&最小生成树