如何判断一个有向图中是否存在一个环，并求出这个环？
RT
[解决办法]
判断是否有环：用DFS（深度优先遍历）,判断是否有后退边，若有，则存在环。
[解决办法]
c - 顶点颜色表 c[u]
0 白色，未被访问过的节点标白色
-1 灰色，已经被访问过一次的节点标灰色
1 黑色，当该节点的所有后代都被访问过标黑色
反向边：
如果第一次访问(u,v)时v为灰色，则(u,v)为反向边。在对图的深度优先搜索中没有发现
反向边，则该图没有回路。
[解决办法]
按照3楼的思想：
用DFS或BFS的遍历图。
如果用DFS的方法：遍历图的每一个结点，不过判断入栈的依据不是结点是否已被访问，而是
当前的边是否已被访问过（遍历过程标记当前被访问的边和结点）。
这样的话，如果遍历过程出现访问已被访问过的结点，就存在环。
不知我这样理解怎么样？
[解决办法]
图的遍历，应该是指遍历图的结点，而不是边吧。
那么遍历图的边的算法，又应该叫做什么算法？
[解决办法]
7楼，你的算法有点问题
比如A-〉C-〉D
A-〉D
这样一个有向图，显然是没有环的。
但是按你的算法，第2次访问到D时，因为D已经被访问过，由此就得出该图存在环的错误结论。
[解决办法]
再补充下，无向图的深度遍历中，访问到已访问过的节点，可以得出 “存在环” 的结论；但在有向图中并不是这样。
我把我的算法详细说下，先建立一个顶点颜色表C[N]
0 白色，未被访问过的节点标白色
-1 灰色，已经被访问过一次的节点标灰色
1 黑色，当该节点的所有后代都被访问过标黑色
仍然是按图的节点深度遍历，访问到V时，V若被访问过，那么有2种状态：
C[V]=-1，程序跳出，存在环
C[V]=1，程序继续，这不是环
时间复杂度O(n+e)
[解决办法]
找出这个环很好办。
typedef struct arcnode{
int adjvex;
struct arcnode *next;
}arcnode;
typedef struct vnode{
int data;
arcnode *firstarc;
}vnode,adjlist[max_vertex_num];
找到构成环的V后，从找出的V出发，
//输出以V开始的环
cout<<adjlist[v].data;
arcnode *p=adjlist[v].firstarc
while(p->adjvex!=v){
while(c[p->adjvex]!=-1){
p=p->next;
}
cout<<adjlist[p->adjvex].data;
p=adjlist[p->adjvex].firstarc;
}
[解决办法]
找出这个环很好办。
typedef struct arcnode{
int adjvex;
struct arcnode *next;
}arcnode;
typedef struct vnode{
int data;
arcnode *firstarc;
}vnode,adjlist[max_vertex_num];
找到构成环的V后，从找出的V出发，
//输出以V开始的环
cout<<adjlist[v].data;
arcnode *p=adjlist[v].firstarc
while(p->adjvex!=v){
while(c[p->adjvex]!=-1){
p=p->next;
}
cout<<adjlist[p->adjvex].data;
p=adjlist[p->adjvex].firstarc;
}
[解决办法]
找出这个环很好办。
typedef struct arcnode{
int adjvex;
struct arcnode *next;
}arcnode;
typedef struct vnode{
int data;
arcnode *firstarc;
}vnode,adjlist[max_vertex_num];
找到构成环的V后，从找出的V出发，
//输出以V开始的环
cout<<adjlist[v].data;
arcnode *p=adjlist[v].firstarc
while(p->adjvex!=v){
while(c[p->adjvex]!=-1){
p=p->next;
}
cout<<adjlist[p->adjvex].data;
p=adjlist[p->adjvex].firstarc;
}
[解决办法]
网络比较卡，连击了，楼主帮我把重复的删了吧
[解决办法]
为什么不用拓扑排序呢。每次找一个入度为0的节点，把它删掉，同时把以它为起点的边都去掉。直到删除所有的定点为止，此时表示图中没有环；或者找不到入度为0的点，此时存在环，就是图中剩下的部分。
[解决办法]
to 14楼：
7楼的意思是，深度优先遍历邻接表，找到曾访问过的节点则说明存在环
看下我8楼举的例子就知道这个算法是不对的。访问到某个曾经访问过的节点时，若该节点的所有后代都被访问过，不能说明存在环。正确的算法我9楼说了。
把图方面的算法好好看下，这个东西其实很基本的。
15楼说的拓扑排序也是判断“是否存在环”的一种方法，但觉得用拓扑排序想“找出这个环”比较困难。
[解决办法]
to 8楼：
反例不对，a->b->c当回溯到a时，再a->c时，c不算重新访问的，因为不在同一深度路径上。
在回溯时之前访问的节点应当擦除。
[解决办法]
拓扑排序的过程中,要不停的删掉结点阿.
如果有环的话,最后剩下的就是环.
如果没有环的话,所有的节点都回被删掉.
[解决办法]
补充个例子吧.
一个图是 a->b->c->d->b
这个图中的环是 b->c->d->b
先找入度为0的节点 ,找到a, 删掉a, 把以a为起点的所有边删掉，这里是a->b.
现在剩下的图就是b->c->d->b.
继续找入度为0的点，此时查找失败，而节点又没有删完，因此存在环。
就是图中剩下的部分b->c->d->b。
[解决办法]
拓扑排序算法本来就是同计算强连通分支算法基本相同，都是线性时间复杂度问题。
深度优先遍历一个图时，是依次将一个个顶点压入一个堆栈，知道它们所有邻居都处理了才能够出栈。
只要在这个过程中，遇到一个已经在栈中的点，就找到了一个回路（或强连通分支)
[解决办法]
深度优先遍历的时间复杂度是线性的。
一般来说，通过递规调用就可以实现。如果你想性能好一些，那可能需要自己实现堆栈。不过性能区别不会很大
