0001 template <typename Tv> struct Vertex { //顶点
0002    Tv data;  int inDeg = 0, outDeg = 0; //数据、入度、出度
0003    Rank dTime = -1, fTime = -1;  VStatus status = UNDISCOVERED; //时间戳、状态
0004    int prio = INT_MAX;  Rank parent = -1; //优先级数、在遍历树或森林中的父节点
0005    Vertex(const Tv& d = Tv{}) : data(d) {} //构造新顶点
0006 }; //Vertex
0007 
0008 template <typename Te> struct Edge { //边
0009    Te data;  int wt;  EType type = UNDETERMINED; //数据、权重、类型
0010    Edge(const Te& d, const int w) : data(d), wt(w) {} //构造
0011 }; //Edge
0012 
0013 //基于向量，以邻接矩阵形式实现的图
0014 template <typename TV, typename TE> class GraphMatrix : public Graph<TV, TE> {
0015 private:
0016    Vector<Vertex<TV>> V; //顶点集（向量）
0017    Vector<Vector<Edge<TE>*>> E; //边集（邻接矩阵）
0018 public:
0019    GraphMatrix() { n = e = 0; } //构造
0020    ~GraphMatrix() { //析构
0021       for (Rank v = 0; v < n; v++) //所有动态创建的
0022          for (Rank u = 0; u < n; u++) //边记录
0023             delete E[v][u]; //逐条清除
0024    }
0025    //边操作
0026    bool exists(Rank v, Rank u) { return (v<n) && (u<n) && E[v][u]; } //边(v,u)是否存在
0027    EType& type(Rank v, Rank u) { return E[v][u]->type; } //边(v,u)的类型
0028    TE& edge(Rank v, Rank u) { return E[v][u]->data; } //边(v,u)的数据
0029    int& wt(Rank v, Rank u) { return E[v][u]->wt; } //边(v,u)的权重
0030    void insert(const TE& edge, int w, Rank v, Rank u); //插入权重为w的边(v,u)
0031    TE remove(Rank v, Rank u); //删除边(v,u)
0032    //顶点操作
0033    TV& vertex(Rank v) { return V[v].data; } //数据
0034    Rank inDeg(Rank v) { return V[v].inDeg; } //入度
0035    Rank outDeg(Rank v) { return V[v].outDeg; } //出度
0036    VStatus& status(Rank v) { return V[v].status; } //状态
0037    Rank& dTime(Rank v) { return V[v].dTime; } //时间戳dTime
0038    Rank& fTime(Rank v) { return V[v].fTime; } //时间戳fTime
0039    Rank& parent(Rank v) { return V[v].parent; } //在遍历树中的父亲
0040    int& prio(Rank v) { return V[v].prio; } //在遍历树中的优先级数
0041    Rank firstNbr(Rank v); //首个邻接顶点
0042    Rank nextNbr(Rank v, Rank u); //相对于顶点u的下一邻接顶点（改用邻接表效率更高）
0043    Rank insert(const TV& vertex); //插入顶点，返回编号
0044    TV remove(Rank v); //删除第v个顶点及其关联边（0 <= v < n）
0045 }; //GraphMatrix