图的相邻节点迭代器 ( adjIterato )

一、介绍

1. 迭代器是一种对象,它能够用来遍历标准模板库容器中的部分或全部元素,每个迭代器对象代表容器中的确定的地址。迭代器修改了常规指针的接口,所谓迭代器是一种概念上的抽象:那些行为上像迭代器的东西都可以叫做迭代器。用迭代器可以很大程度上隔离容器底层实现，使用时只需依赖迭代器相对统一的方法/接口。
2. 图的相邻节点迭代器 ( adjIterato )是用来高效的对图相邻节点遍历的，能对图进行操作。

二、实现

1. 稠密图相邻节点迭代器的实现：
   我们需要将此迭代器写在稠密图的类中

稠密图：

#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
//稠密图
class DenseGraph{
private:
    int n, m; //节点数和边数
    bool directed; //是否为有向图
    vector<vector<bool>> g; //图的具体数据,0 1 用bool值false和true表示
public:
    DenseGraph(int n, bool directed){
      assert(n >= 0);
      this->n = n;
      this->m = 0;
      this->directed = directed;
// g初始化为n*n的布尔矩阵, 每一个g[i][j]均为false, 表示没有任和边
      g = vector<vector<bool>>(n, vector<bool>(n, false));
}
  //析构函数
  ~DenseGraph(){}
//返回图中节点的个数
int getV(){
     return n;
}
//返回图中边的条数
int getE(){
     return m;
}
//向图中添加一条边
void addEdga(int v, int w){
      assert(v >= 0 && v < n);
      assert(w >= 0 && w < n);
      if(hasEdga(v, w)){
           return;
       }

      g[v][w] = true;
    //无向图是双向的
      if(!directed){
           g[w][v] = true;
       }
      m++;
}
//验证图中是否有v到w的边
bool hasEdga(int v, int w){
     assert(v >= 0 && v < n);
     assert(w >= 0 && w < n);
     return g[v][w];
}
//显示图中信息
void show(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cout<<g[i][j]<<"\t";
        }
        cout<<endl;
     }
    }

下面是稠密图迭代器的部分：

// 邻边迭代器, 传入一个图和一个顶点,
 // 迭代在这个图中和这个顶点向连的所有顶点  
 class adjIterator{
    private:
        DenseGraph &G; //图G的引用
        int v; //传入一个节点
        int index; //对应的索引

    public:
        adjIterator(DenseGraph &graph, int v): G(graph){
             assert(v >= 0 && v < G.n);
             this->v = v;
           // 索引从-1开始, 因为每次遍历都需要调用一次next()
             this->index = -1;
  }
        //析构函数
        ~adjIterator(){}

        // 返回图G中与顶点v相连接的第一个顶点
        int begin(){
            index = -1;
            return next();
        }
        // 返回图G中与顶点v相连接的下一个顶点
        int next(){
            for(index += 1; index <= G.getV(); index ++){
                if( G.g[v][index] ){
                    return index;
                }
                return -1;
            }
       }

        // 查看是否已经迭代完了图G中与顶点v相连接的所有顶点
         bool end(){
            return index >= G.getV();
        }
     };
};

2. 稀疏图的相邻节点迭代器
   同样我们需要在稀疏图这个类中编写相应的迭代器

稀疏图：

#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
//稀疏图—邻接表
class SparseGraph{
private:
    int n, m; //节点数和边数
    bool directed; //是否为无向图
    vector<vector<int>> g; //图的具体数据
public:
   SparseGraph(int n,bool directed){
       assert(n >= 0);
       this->n = n;
       this->directed = directed;
       // g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
       g = vector<vector<int>>(n, vector<int>());
}
  //析构函数
  ~SparseGraph(){}

  int getV(){
      return n;
}
  int getE(){
      return m;
}
// 向图中添加一个边
void addEdga(int v, int w){
      assert( v >= 0 && v < n );
      assert( w >= 0 && w < n );
     //将w放入g[v][i]中,将w与v相连
      g[v].push_back(w);
      if(v != w && !directed){
          g[w].push_back(v);
      }
      m ++;
}
// 验证图中是否有从v到w的边
bool hasEdga(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] == w)
                 return true;
            return false;  }
}
//显示图中信息
void show(){
    for(int i = 0; i < n; i++){
        cout<<"vector"<<":\t";
        for(int j = 0; j < g[i].size(); j++){
            cout<<g[i][j]<<":\t";
          }
        cout<<endl;
    }
  }

下面是迭代器部分：

// 邻边迭代器, 传入一个图和一个顶点,
 // 迭代在这个图中和这个顶点向连的所有顶点 
   class adjIterator{
    private:
        SparseGraph &G; //图的引用
           int v; //传入节点
           int index; //对应索引

  public:
        adjIterator(SparseGraph &graph, int v):G(graph){
            this->v = v;
            this->index = 0;
        }

        //析构函数
        ~adjIterator(){}
        // 返回图G中与顶点v相连接的第一个顶点
  int begin(){
            index = 0;
            if( G.g[v].size() ){
                return G.g[v][index];
            }
            return -1;
  }

   // 返回图G中与顶点v相连接的下一个顶点
  int next(){
            index++;
            if( index < G.g[v].size() )
                return G.g[v][index];
  }

  bool end(){
            return index >= G.g[v].size();
       }
    };
};

本作品采用《CC 协议》，转载必须注明作者和本文链接