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