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

一、介绍

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

二、实现

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

稠密图：

#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();
        }
    };
};

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

稀疏图：

#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();
        }
    };
};

图论系列之「相邻节点迭代器 ( adjIterato ) 」

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

一、介绍

二、实现