图论之有权图「带权图的表示及相邻节点迭代器」

带权图的表示

一、介绍

带权图(Weighted Graph):带权图就是指图中的每一条边都有对应的一个或一组值,通常情况下这个值的是数值。
如:在交通运输网中,边上的权值可能表示的是路程,也可能表示
的是运输费用(显然二者都是数字)。不过,边上的权值也有可能
是其它东西,比如说是一个字符串,甚至是一个更加复杂的数据包,
里面集合了更多的数据。

图论之有权图「带权图的表示」

二、表示方法

  1. 邻接表
    在无权图中邻接表只存放了相应顶点,而现在带权图既需要存放顶点又需要存放权值,所以在带权图中的需要一个Edge的类来表示有权图的顶点和权值,表示方法如下:
    图论之有权图「带权图的表示」
    这里再将权值的类型写成指针类型

图论之有权图「带权图的表示」

  1. 邻接矩阵
    在带权中不再使用bool值,但是这里为了统一接口,统一将邻接矩阵的表示写成一个Edge类
    图论之有权图「带权图的表示」
    这里再将权值的类型写成指针类型

图论之有权图「带权图的表示」

三、带权图的实现

  1. 首先需要编写一个Edge的类,用来表示带全图

    #include <iostream>
    #include <cassert>
    using namespace std;
    // 边
    //使用模板类型Weight
    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;
     }   
    
     // 给定一个顶点, 返回另一个顶点
     //other(int x)在图的算法中常用
    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();
     }
    };
  2. 稀疏图(邻接表)的实现
    在带权图中,我们需要将Edge的类的头文件引入

    #include <iostream>
    #include <vector>
    #include <cassert>
    #include "Edge.h"

    需要将原来的数据类型int类型改为:<Edge<Weight>*>类型,如下:
    vector<vector<Edge<Weight> *> > g;

    
    using namespace std;
    // 稀疏图 - 邻接表
    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 );
    
         // 注意, 由于在邻接表的情况, 查找是否有重边需要遍历整个链表
         // 我们的程序允许重边的出现
         //需要开空间,Edge<Weight>类型,包括:两个节点和权值
         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;
        }
    }
    • 下面来看看稀疏图的迭代器
      其实和前面一样, 将原来的int类型改为Edge<Weight>*

      // 邻边迭代器, 传入一个图和一个顶点,
      // 迭代在这个图中和这个顶点向连的所有边  
      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();
        }
       };
      };
  3. 稠密图—邻接矩阵的实现
    同样需要将Edge类的头文件引入

    #include <iostream>
    #include <vector>
    #include <cassert>
    #include "Edge.h"
    using namespace std;

    编写一个类
    同理,需要将原来的bool类型改为Edge<Weight> *

    // 稠密图 - 邻接矩阵
    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;
           }
      }
    }
  • 稠密图迭代器的实现
    在迭代器中只需要把原来的bool类型改为Edge<Weight>*
// 邻边迭代器, 传入一个图和一个顶点,
// 迭代在这个图中和这个顶点向连的所有边
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();
    }
  };
};
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!