对图的深度遍历与对树的深度遍历思想类似，采用的是递归函数的办法。
如果是非连通图，则DFS遍历所有顶点即可。
//Graph 图//vertex 顶点，用一个int型变量表示//返回有向图G中顶点v的第一个邻接点，如没有返回-1int FirstNeighbor(Graph G, int v){//(......具体实现细节)return w;}//假设图G中w是v的一个邻接点，返回除w外的v的下一个邻接点，若没有，返回-1int NextNeighbor(Graph G, int v, int w){//(......具体实现细节)return w;}//访问v顶点void visit(int v);//标记顶点被访问状态的数组，初始时全为falsebool visited[MAX_NUM];//从图G中的顶点v开始进行深度优先遍历，是递归函数void DFS(Graph G, int v){visit(v);visited[v] = true; //顶点v已被访问for (w = FirstNeighbor(G, v); w != -1; w = NextNeighbor(G, v, w)){if (visited[w] == false)DFS(G, w);}}
对于有向无环图，则肯定是非强连通的，需遍历所有顶点。
拓扑排序：有向无环图的一种排序，若图中有A指向B的路径，则排序中A一定在B的前面。一个有向无环图可能存在多种拓扑排序。
下图表示“吃番茄炒蛋”的过程，可以有多种途径吃上番茄炒蛋，但无论哪种途径，必须先买菜再打鸡蛋、先准备厨具再切番茄等等。任何一种能“吃上鸡蛋”的过程就是下图的一个拓扑排序。
图来源：b站王道计算机考研 数据结构 P66
每一种拓扑排序都存在其对应的逆拓扑排序，将排序反向即可。
倘若要逆拓扑排序输出一个图，则可采用DFS算法。
//初始时默认visited数组全为false//为保证所有顶点都被排序，需遍历所有顶点for (int i = 0; i < MAX_NUM; i++){if (!visited[i])DFS(G, i);}void DFS(Graph G, int v){visited[v] = true;for (w = FirstNeighbor(G, v); w != -1; w = NextNeighbor(G, v, w)){if (!visited[w])DFS(G, w);}print(v); //输出v信息进行逆拓扑排序}
原理：无论从任何顶点v开始DFS，DFS递归函数运行时会存在函数调用栈，最先执行结束的那一层函数是某条路上最深的那个顶点，结束之前将其输出排序，这样v为起点的这条路径（包括有分路的情况，但分路的先后顺序没有要求）上所有顶点就都被“反向输出”了。
再遍历其他顶点w时，要么w与v不存在路径，要么一定是有w指向v的路径，因为如果v存在指向w的路径，DFS(v)过程中一定会输出w，visited[w] == false，DFS对w也不会生效了。
所以上述输出一定可以满足逆拓扑排序要求。
question：如果图是存在环的，上述算法会失效。如下：
如果DFS(G, 0)，会输出2 4 3 1 0。但有环图根本不存在逆拓扑排序。（有环代表永远输出不完，无拓扑，更不谈逆拓扑），所以需要修改DFS内容来判断是否存在环。
方法：从新设置一个数组 if_visiting[MAX_NUM] 记录该顶点是否正处于被访问状态
//初始时默认visited数组、if_visiting数组全为false//为保证所有顶点都被排序，需遍历所有顶点for (int i = 0; i < MAX_NUM; i++){if (!visited[i])DFS(G, i);}void DFS(Graph G, int v){visited[v] = true;if_visiting[v] = true;for (w = FirstNeighbor(G, v); w != -1; w = NextNeighbor(G, v, w)){if (!visited[w]){DFS(G, w);}if (if_visiting[w]){cout << "存在回路" <<endl;return;}}print(v); //输出v信息进行逆拓扑排序if_visiting[v] = false;}
在visit一个顶点v之后，将其if_visiting也设为true，这样往下遍历时如果有顶点的下一个顶点为v，就会检测到v正在被访问，于是存在环路。可以输出提示我们一下。
print完v之后，if_visiting重新设为false，代表v顶点彻底被遍历完了，这样从其他路径遇到v时也不会有任何影响。
如果觉得《图——深度优先遍历(DFS)实现有向无环图的逆拓扑排序》对你有帮助，请点赞、收藏，并留下你的观点哦！
