算法 -- 图论

#ifndef SPARSEGRAPH_H
#define SPARSEGRAPH_H
#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){
        this->n = n;
        this->m = 0;
        this->directed = directed;
        for(int i=0;i<n;i++)
            g.push_back(vector<int>());
    }
    ~SparseGraph(){

    };
    int V(){return n;}//顶点
    int E(){return m;}//边

    void addEdge(int v,int w){
        assert(v>=0 && v<n);
        assert(w>=0 && w<n);

        g[v].push_back(w);
        if(v != w && !directed)//处理自环边
            g[w].push_back(v);
        m++;
    }
    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] == w)
                return true;
        }
        return false;
    };
    //迭代器,迭代顶点的相邻的边
    class adjIterator{
    private:
        SparseGraph &G;
        int v;
        int index;
    public:
        adjIterator(SparseGraph &graph,int v):G(graph){
            this->v = v;
            this->index=0;
        }
        int begin(){
            index =0;
            if(G.g[v].size())
                return G.g[v][index];
            return -1;
        }
        int next(){
            index ++;
            if(index <G.g[v].size())
                return G.g[v][index];
            return -1;
        }
        bool end(){
            return index>= G.g[v].size();

        }
    };

};

#endif

#ifndef DENSEGRAPH_H
#define DENSEGRAPH_H
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;

//稠密图 -- 邻接矩阵
class DenseGraph{
private:
    int n,m;//点数和边数
    bool directed;//有向图还是无向图
    vector<vector<bool>> g;//邻接矩阵，两个向量嵌套
public:
    DenseGraph(int n,bool directed){
        this->n = n;
        this->m = 0;
        this->directed = directed;
        for(int i=0;i<n;i++)
            g.push_back(vector<bool>(n,false));//创建矩阵
    }
    ~DenseGraph(){
    }
    int V(){return n;}//顶点
    int E(){return m;}//边

    void addEdge(int v,int w){
        assert(v>=0 && v<n);
        assert(w>=0 && w<n);
        if (hasEdge(v,w))
            return;

        g[v][w] = true;
        if(!directed)
            g[w][v] = true;
        m ++;
    }
    bool hasEdge(int v,int w){
        assert(v>=0 && v<n);
        assert(w>=0 && w<n);
        return g[v][w];
    }
    class adjIterator{
    private:
        DenseGraph &G;
        int v;
        int index;
    public:
        adjIterator(DenseGraph &graph,int v):G(graph){
            this->v = v;
            this->index=-1;
        }
        int begin(){
            index = -1;
            return next();
        }
        int next(){
            for(index +=1;index <= G.V(); index++)
                if(G.g[v][index])
                    return index;
            return -1;

        }
        bool end(){
            return index >= G.V();
        }
    };

};

#endif