0001 #include "Vector/Vector.h" //引入向量
0002 #include "Graph/Graph.h" //引入图ADT
0003 
0004 template <typename Tv> struct Vertex { //顶点对象（为简化起见，并未严格封装）
0005    Tv data; int inDegree, outDegree; VStatus status; //数据、出入度数、状态
0006    Rank dTime, fTime; //时间标签
0007    Rank parent; int priority; //在遍历树中的父节点、优先级数
0008    Vertex( Tv const& d = (Tv)0 ) : //构造新顶点
0009       data( d ), inDegree( 0 ), outDegree( 0 ), status( UNDISCOVERED ), dTime( -1 ),
0010       fTime( -1 ), parent( -1 ), priority( INT_MAX ) {} //暂不考虑权重溢出
0011 };
0012 
0013 template <typename Te> struct Edge { //边对象（为简化起见，并未严格封装）
0014    Te data; int weight;
0015    EType type; //数据、权重、类型
0016    Edge( Te const& d, int w ) : data( d ), weight( w ), type( UNDETERMINED ) {} //构造
0017 };
0018 
0019 template <typename Tv, typename Te> //顶点类型、边类型
0020 class GraphMatrix : public Graph<Tv, Te> { //基于向量，以邻接矩阵形式实现的图
0021 private:
0022    Vector<Vertex<Tv>> V; //顶点集（向量）
0023    Vector<Vector<Edge<Te>*>> E; //边集（邻接矩阵）
0024 public:
0025    GraphMatrix() { n = e = 0; } //构造
0026    ~GraphMatrix() { //析构
0027       for ( Rank v = 0; v < n; v++ ) //所有动态创建的
0028          for ( Rank u = 0; u < n; u++ ) //边记录
0029             delete E[v][u]; //逐条清除
0030    }
0031 // 顶点的基本操作：查询第v个顶点（0 <= v < n）
0032    virtual Tv& vertex( Rank v ) { return V[v].data; } //数据
0033    virtual Rank inDegree( Rank v ) { return V[v].inDegree; } //入度
0034    virtual Rank outDegree( Rank v ) { return V[v].outDegree; } //出度
0035    virtual Rank firstNbr( Rank v ) { return nextNbr( v, n ); } //首个邻接顶点
0036    virtual Rank nextNbr( Rank v, Rank u ) //相对于顶点u的下一邻接顶点（改用邻接表效率更高）
0037       { while ( ( -1 != --u ) && !exists( v, u ) ); return u; } //逆向线性试探
0038    virtual VStatus& status( Rank v ) { return V[v].status; } //状态
0039    virtual Rank& dTime( Rank v ) { return V[v].dTime; } //时间标签dTime
0040    virtual Rank& fTime( Rank v ) { return V[v].fTime; } //时间标签fTime
0041    virtual Rank& parent( Rank v ) { return V[v].parent; } //在遍历树中的父亲
0042    virtual int& priority( Rank v ) { return V[v].priority; } //在遍历树中的优先级数
0043 // 顶点的动态操作
0044    virtual Rank insert( Tv const& vertex ) { //插入顶点，返回编号
0045       for ( Rank u = 0; u < n; u++ ) E[u].insert( NULL ); n++; //各顶点预留一条潜在的关联边
0046       E.insert( Vector<Edge<Te>*>( n, n, (Edge<Te>*)NULL ) ); //创建新顶点对应的边向量
0047       return V.insert( Vertex<Tv>( vertex ) ); //顶点向量增加一个顶点
0048    }
0049    virtual Tv remove( Rank v ) { //删除第v个顶点及其关联边（0 <= v < n）
0050       for ( Rank u = 0; u < n; u++ ) //所有
0051          if ( exists( v, u ) ) //出边
0052             { delete E[v][u]; V[u].inDegree--; e--; } //逐条删除
0053       E.remove( v ); n--; //删除第v行
0054       Tv vBak = vertex( v ); V.remove( v ); //删除顶点v
0055       for ( Rank u = 0; u < n; u++ ) //所有
0056          if ( Edge<Te>* x = E[u].remove( v ) ) //入边
0057             { delete x; V[u].outDegree--; e--; } //逐条删除
0058       return vBak; //返回被删除顶点的信息
0059    }
0060 // 边的确认操作
0061    virtual bool exists( Rank v, Rank u ) //边(v, u)是否存在
0062       { return ( v < n ) && ( u < n ) && ( E[v][u] != NULL ); }
0063 // 边的基本操作：查询顶点v与u之间的联边（0 <= v, u < n且exists(v, u)）
0064    virtual EType& type( Rank v, Rank u ) { return E[v][u]->type; } //边(v, u)的类型
0065    virtual Te& edge( Rank v, Rank u ) { return E[v][u]->data; } //边(v, u)的数据
0066    virtual int& weight( Rank v, Rank u ) { return E[v][u]->weight; } //边(v, u)的权重
0067 // 边的动态操作
0068    virtual void insert( Te const& edge, int w, Rank v, Rank u ) { //插入权重为w的边(v, u)
0069       if ( exists( v, u ) ) return; //确保该边尚不存在
0070       E[v][u] = new Edge<Te>( edge, w ); //创建新边
0071       e++; V[v].outDegree++; V[u].inDegree++; //更新边计数与关联顶点的度数
0072    }
0073    virtual Te remove( Rank v, Rank u ) { //删除顶点v和u之间的联边（exists(v, u)）
0074       Te eBak = edge( v, u ); delete E[v][u];
0075       E[v][u] = NULL; //备份后删除边记录
0076       e--; V[v].outDegree--; V[u].inDegree--; //更新边计数与关联顶点的度数
0077       return eBak; //返回被删除边的信息
0078    }
0079 }; //Graph