拓扑排序+有向无环图(DAG)的检测

本文主要是介绍拓扑排序+有向无环图(DAG)的检测，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考: 算法导论第三版 p356, 数据结构与算法分析p218, 算法入门经典p110

拓扑排序的两张方法:

1.dfs搜索
2.模拟人工的拓扑
两种方法的效率都是O(V + E)

$$拓扑排序的方法也是有向无环图检测的方法

/*
拓扑排序 dfs搜索 - 邻接表
可以判断一个图是否有环
*/#include <cstdio>
#include <vector>
#include <stack>
using std::vector;
using std::stack;const int MAXN = 10;
const int INIT = 0;
const int GRAY = 1; //参考算法导论的染色, GRAY表示一条后向边
const int BLACK = 2;int visit[MAXN];
int time = 0;
vector<vector<int>>g(MAXN);
stack<int> ans;bool dfs(int p) // recursion递归
{visit[p] = GRAY; //表示正被访问(正在访问它或者它的子孙)的结点for (int i = 0; i < g[p].size(); ++i){int temp = g[p][i];if (visit[temp] == INIT){if (dfs(temp) == false)return false;}else if (visit[temp] == GRAY){//GRAY表示一条后向边,代表子孙

这篇关于拓扑排序+有向无环图(DAG)的检测的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---