0001 using VStatus = enum { UNDISCOVERED, DISCOVERED, VISITED }; //顶点在遍历过程中的状态 0002 using EType = enum { UNDETERMINED, TREE, CROSS, FORWARD, BACK }; //边经过遍历之后的分类 0003 0004 template <typename Tv, typename Te> //顶点类型、边类型 0005 class Graph { //图ADT 0006 private: 0007 void reset() { //整体复位 0008 for (Rank v = 0; v < n; v++) { //所有顶点的 0009 status(v) = UNDISCOVERED; dTime(v) = fTime(v) = -1; //状态、时间戳 0010 prio(v) = INT_MAX; parent(v) = v; //优先级暂取作最低，父亲暂取作自己 0011 for (Rank u = 0; u < n; u++) //所有边的 0012 if (exists(v,u)) type(v,u) = UNDETERMINED; //类型待定 0013 } //for 0014 } //reset 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(const Tv&) = 0; //插入顶点，返回编号 0024 virtual Tv remove(Rank) = 0; //删除顶点及其关联边，返回该顶点信息 0025 virtual Tv& vertex(Rank) = 0; //数据（该顶点的确存在） 0026 virtual Rank inDeg(Rank) = 0; //入度（该顶点的确存在） 0027 virtual Rank outDeg(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& prio(Rank) = 0; //在遍历树中的优先级数 0035 //边：约定无向边均转化为方向互逆的一对有向边 0036 Rank e; //边总数 0037 virtual bool exists(Rank, Rank) = 0; //检测边是否存在 0038 virtual void insert(const Te&, 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& wt(Rank, Rank) = 0; //权重 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 dijk(Rank); //最短路径Dijkstra 0050 template <typename PU> void pfs(Rank, PU); //优先级搜索 0051 }; //Graph