0001 using VStatus = enum { UNDISCOVERED, DISCOVERED, VISITED }; //顶点状态 0002 using EType = enum { UNDETERMINED, TREE, CROSS, FORWARD, BACKWARD }; //边在遍历树中所属的类型 0003 0004 template <typename Tv, typename Te> //顶点类型、边类型 0005 class Graph { //图Graph模板类 0006 private: 0007 void reset() { //所有顶点、边的辅助信息复位 0008 for ( Rank v = 0; v < n; v++ ) { //所有顶点的 0009 status( v ) = UNDISCOVERED; dTime( v ) = fTime( v ) = -1; //状态，时间标签 0010 parent( v ) = -1; priority( v ) = INT_MAX; //（在遍历树中的）父节点，优先级数 0011 for ( Rank u = 0; u < n; u++ ) //所有边的 0012 if ( exists( v, u ) ) type( v, u ) = UNDETERMINED; //类型 0013 } 0014 } 0015 void BFS( Rank, Rank& ); //（连通域）广度优先搜索算法 0016 void DFS( Rank, Rank& ); //（连通域）深度优先搜索算法 0017 void BCC( Rank, Rank&, Stack<Rank>& ); //（连通域）基于DFS的双连通分量分解算法 0018 bool TSort( Rank, Rank&, Stack<Tv>* ); //（连通域）基于DFS的拓扑排序算法 0019 template <typename PU> void PFS( Rank, PU ); //（连通域）优先级搜索框架 0020 public: 0021 // 顶点 0022 Rank n; //顶点总数 0023 virtual Rank insert( Tv const& ) = 0; //插入顶点，返回编号 0024 virtual Tv remove( Rank ) = 0; //删除顶点及其关联边，返回该顶点信息 0025 virtual Tv& vertex( Rank ) = 0; //顶点的数据（该顶点的确存在） 0026 virtual Rank inDegree( Rank ) = 0; //顶点的入度（该顶点的确存在） 0027 virtual Rank outDegree( Rank ) = 0; //顶点的出度（该顶点的确存在） 0028 virtual Rank firstNbr( Rank ) = 0; //顶点的首个邻接顶点 0029 virtual Rank nextNbr( Rank, Rank ) = 0; //顶点（相对当前邻居的）下一邻居 0030 virtual VStatus& status( Rank ) = 0; //顶点的状态 0031 virtual Rank& dTime( Rank ) = 0; //顶点的时间标签dTime 0032 virtual Rank& fTime( Rank ) = 0; //顶点的时间标签fTime 0033 virtual Rank& parent( Rank ) = 0; //顶点在遍历树中的父亲 0034 virtual int& priority( Rank ) = 0; //顶点在遍历树中的优先级数 0035 // 边：这里约定，无向边均统一转化为方向互逆的一对有向边，从而将无向图视作有向图的特例 0036 Rank e; //边总数 0037 virtual bool exists( Rank, Rank ) = 0; //边(v, u)是否存在 0038 virtual void insert( Te const&, int, Rank, Rank ) = 0; //在两个顶点之间插入指定权重的边 0039 virtual Te remove( Rank, Rank ) = 0; //删除一对顶点之间的边，返回该边信息 0040 virtual EType& type( Rank, Rank ) = 0; //边的类型 0041 virtual Te& edge( Rank, Rank ) = 0; //边的数据（该边的确存在） 0042 virtual int& weight( Rank, Rank ) = 0; //边(v, u)的权重 0043 // 算法 0044 void bfs( Rank ); //广度优先搜索算法 0045 void dfs( Rank ); //深度优先搜索算法 0046 void bcc( Rank ); //基于DFS的双连通分量分解算法 0047 Stack<Tv>* tSort( Rank ); //基于DFS的拓扑排序算法 0048 void prim( Rank ); //最小支撑树Prim算法 0049 void dijkstra( Rank ); //最短路径Dijkstra算法 0050 template <typename PU> void pfs( Rank, PU ); //优先级搜索框架 0051 };