这篇文章源自一个问题，系统中有如下的一些依赖关系 (A,B),(B,C),(A,C)...
其中每一项形如(X,Y)的形式， 表示 X依赖Y， 输入这样的数组， 要求判断这个系统中有无循环依赖关系
举例来说 ：(A,B),(B,C),(C,A) 就存在循环依赖 ，用X->Y表示X依赖Y的话， 有 A->B->C->A ,构成一个环，形成循环依赖；
显然这是一个和 graph theory 有关的问题，转换为图论的语言，就是
把A,B,C...看作图的节点 ， X依赖Y 则 从 X到Y做一条有向边 ， 这个问题转为判断 有向图中 有无有向环；
后文中将不区分以下描述的含义：
1，存在X到Y的一条有向边；
2，X指向Y
3, X依赖Y
这三者说的都是同一个意思，都是指图中有X指向Y的有向边;
为了解决这个问题，我们先引入拓扑排序的概念 ，拓扑排序和有向图有关；
给定一个有向图 ，如果 我们可以对图的节点做一个排序 ，使得排序后的节点中，
不存在索引号较高的节点 指向 索引号较低的节点，那么这个排序就称为 这个有向图的 拓扑排序；
一个有向图可能存在多个拓扑排序 ，举例来说，考虑:
下面给出 ，这个图的2个拓扑排序；
1,2,3,4,5 和 1,2,3,5,4
这2个排序中 ， 任何一个索引高的节点不会指向索引低的节点 ，举例来说 :4不会指向 1,2,3,5;
但是有向图 也可能不存在拓扑排序:
比如 : 1->2->3->1 (图的节点中只有1个1）
这个图存在环形结构不可能存在拓扑排序；
很显然 ，只要一个图中存在有向环，那么这个环上的节点不管以何种顺序排列，都会出现后面的指向前面的
证明：
设环中所有节点组成的集合为C ,其中索引最高的节点为k, 因为是环形结构，所以k必然指向 C{k}中某个节点，
而C{k}中节点的索引全都低于k的索引，证明完毕;
进一步，整个图就不存在拓扑排序；
所以，得到定理1：
存在有向环的图不存在拓扑排序；
现在考虑其反命题，如果一个图不存在拓扑排序，是否这个图一定存在有向环？
或者说， 如果一个图如果没有环，是否一定存在拓扑排序？
以下是我想出的一个构造性证明方法；
定理：一个有向图如果不存在有向环，则这个图一定存在拓扑排序
证明：
先给定一张无有向环的图G ,为了方便证明，我们先给出一个 节点的 出度 和 入度的概念
节点x的出度： x指向的节点个数；
节点x的入度： 指向x的节点的个数；
先证明一个引理： 如果一个图中没有出度为0 的节点，该图中一定存在环
引理证明如下：在图中任意取一个节点x0，因为其出度不为0，可以找到一个它指向的节点x1
,如果x1=x0，已存在环，否则，因为x1的出度不为0，所以可以找到x1指向的节点 x2, 如果x2属于
{x0,x1}，已存在环 ，否则 ，可以找到x3,...以此类推，因为图中节点数有限，必然最终会出现环，
否则这个序列可以不重复的无限延伸下去；证明完毕。
我们找到G中任意一个出度为0的节点x（如果不存在这样的节点，说明G中有环,与假设矛盾），
我们把节点x从图G中去除（去除的方法是把所有指向它的有向边全部去掉，再把这个节点去掉），
得到一张新的有向图 G{x} ,同时把x放到一个队列的末尾 [x];
在图G{x}中我们仍然可以找到出度为0 的节点y (否则G{x}中有环，则G中也有环);
进一步去掉y，我们得到 G{x,y},并且把y放到x前 ，得到 [y,x];
以此类推，显然我们可以继续这个过程直到 空图 ，并得到一个节点的排序:
[.... z,y,x];
下面我断言，这个排序，是这个图的拓扑排序；
假设 ，这个断言不成立，必然存在 某个后面的节点指向前面的节点 ，比如 b->a;
但是从我们构建这个排序的过程可以看出，当我们把b从图中移除时（此时a仍然在图中），b的度
为0，这意味着b不指向对应的图 中的任何节点（这个图包含a）,也就是b不指向a，从而在G中,b也不指向a,
矛盾；所以这个图是原图的一个拓扑排序
这样，我们构造性的证明了拓扑排序的存在性
证明完毕。
至此，得到一条定理，
有向图存在有向环 等价于 有向图不存在拓扑排序；
现在我们可以来分析原问题，原问题是判断一个 有向图是否存在有向环，
那么通过定理，我们可以通过判断这个图是否存在拓扑排序来判断其是否存在有向环；
问题被转化为研究如何对图进行拓扑排序，但是在上面证明过程中，我们已经看到了如何构造拓扑排序了
不过证明的前提是假定图无环，显然，当图有环时，我们在上述拓扑排序的构造过程中，必然会出现某一时刻
，对应的图没有度为0 的节点出现；这样就解决了这个问题；
不过，这只是从理论上解决了这个问题，从编程实现的角度来说，仍然没有，因为要考虑算法复杂度与实现细节问题，下面我们来做进一步的分析如何实现的问题：
其实，从上面的证明过程中稍加思考就可以提取出一种编码实现步骤：
1，把所有节点存入一个集合 （实际可以用map）
2，计算所有节点的出度 ,放在对应的节点key的value中；
3, 统计每个节点所有的父节点，存入另外一个map,键为节点，value是一个数组，里面放所有该节点的父节点；
4，遍历所有节点的出度，如果没有为0 的，说明有环,return true;
5, 取其中任意一个为0的节点 ，通过第二个map找到这个节点的所有父节点（就是指向这个节点的节点），
把这些节点的出度减去1；同时把这个节点从2个map中分别删去；
6，判断map是否为空，如果为空,返回false,否则回到4;
这个方法显然可行，但是存在一个问题 ，就是 步骤 4， 每次都有遍历所有节点出度，造成算法复杂度过高，
我们希望有个复杂度较低的算法；因此我们可以改进如下；
首先第一次计算出所有节点的出度 ，把为0的所有节点放入一个集合A，
之后对这个集合遍历 执行 步骤5，只不过把找到的父节点中出度减去1为 0的放入集合B;
显然，剩余节点中出度为0 的节点 只有集合B中的这些，之后swap(A,B)，再重复该过程即可;
该方法在leetcode的实现代码如下:
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
std::vector<int> res;
std::map<int,std::set<int>> pres;
std::map<int,int> sucs;
for(int i=0;i<numCourses;++i)
{
sucs.insert(make_pair(i,0));
pres.insert(make_pair(i,std::set<int>()));
}
if(prerequisites.empty()&&numCourses>0)
{
for(int i=0;i<numCourses;++i)
{
res.push_back(i);
}
return res;
}
for(auto& it:prerequisites)
{
int val=it[1];
int key=it[0];
pres[val].insert(key);
if(sucs.count(key)==0) sucs[key]=1;
else sucs[key]+=1;
}
//出度为0 的节点
std::set<int> zeros;
std::set<int> zeros2;
for(auto& it:sucs)
{
if(it.second==0)
{
zeros.insert(it.first);
}
}
if(zeros.empty()) return vector<int>();
while(!zeros.empty())
{
for(auto& it:zeros)
{
for(auto& it:pres[it])
{
sucs[it]-=1;
if(sucs[it]==0)
{
zeros2.insert(it);
}
}
res.push_back(it);
}
numCourses-=zeros.size();
std::swap(zeros,zeros2);
zeros2.clear();
}
if(numCourses==0) return res;
return std::vector<int>();
}
};
下面我们进一步分析，
考察引理:如果一个图中没有出度为0 的节点，该图中一定存在环
其实节点的出度和入度有“对称性”， 把这个引理中的“出度”改为“入度”，显然仍然成立，那么
上为面的证明过程实际也可以从入度0 的节点开始 ，编程实现方法也可以从入度开始；这是完全对称的
本文提供的方法通过每次更新出度为0的集合来实现，如果有更高效的方法，欢迎读者探讨；
