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