有向图的拓扑排序——DFSYVVTReal

首先，我们需要维护一个栈，用来存放DFS到的节点。另外规定每个节点有两个状态：已访问（这里用蓝绿色表示）、未访问（这里用黑色表示）。

任选一个节点开始DFS，比如这里就从0开始吧。

首先将节点0的状态设为已访问，然后节点0的邻居（节点0的出边指向的节点）共有1个：节点2，它是未访问状态，于是顺下去访问节点2。

节点2的状态也设为已访问。节点2有3个邻居：3、4、5，都是未访问状态，不妨从3开始。一直这样访问下去，直到访问到没有出边的节点7。

节点7没有出边了，这时候就将节点7入栈。

退回到节点6，虽然6还有邻居，但是唯一的邻居节点7是已访问状态，也入栈。再次退回，节点4的两个邻居也都已访问，依旧入栈并后退。以此类推，退回到节点2。

节点2有3个邻居，其中节点3和4已访问，但是节点5还未访问，访问节点5。

接下来的步骤是一样的，不再赘述了，直接退回到节点0并将0入栈。

现在，从节点0开始的DFS宣告结束，但是图中还有未访问的节点：节点1，从节点1继续开始DFS。

节点1的邻居节点2已经访问过了，直接将节点1入栈。

至此，整个DFS过程宣告结束。从栈顶到栈底的节点序列10253467就是整个图的一个拓扑排序序列。

这里同样使用类型别名node_t代表节点序号unsignedlonglong：

usingnode_t=unsignedlonglong;同样使用邻接表来存储图结构，整个图的定义如下：

classGraph{unsignedlonglongn;vector>adj;protected:voiddfs(node_tcur,vector&visited,stack&nodeStack);public:Graph(initializer_list>list):n(list.size()),adj({}){for(auto&l:list){adj.emplace_back(l);}}vectortoposortDfs();};DFS函数dfs的参数及说明如下：

整个过程如下：

visited[cur]=true;for(node_tneighbor:adj[cur]){//...}if(visited[neighbor])continue;dfs(neighbor,visited,nodeStack);nodeStack.push(cur);整个dfs函数的代码如下：

voidGraph::dfs(node_tcur,vector&visited,stack&nodeStack){visited[cur]=true;for(node_tneighbor:adj[cur]){if(visited[neighbor])continue;dfs(neighbor,visited,nodeStack);}nodeStack.push(cur);}拓扑排序首先，我们需要初始化3个数据结构：

vectorsort;vectorvisited(n,false);stacknodeStack;整个过程如下：

for(node_tnode=0;node

vectorGraph::toposortDfs(){vectorsort;vectorvisited(n,false);stacknodeStack;for(node_tnode=0;node

intmain(){Graphgraph{{2},{2},{3,4,5},{4},{6,7},{4},{7},{}};autosort=graph.toposortDfs();cout<<"Thetopologysortsequenceis:\n";for(constauto&node:sort){cout<