更改

The existence of a cycle in directed and undirected graphs can be determined by whether depth-first search (DFS) finds an edge that points to an ancestor of the current vertex (it contains a back edge).All the back edges which DFS skips over are part of cycles. In an undirected graph, the edge to the parent of a node should not be counted as a back edge, but finding any other already visited vertex will indicate a back edge. In the case of undirected graphs, only O(n) time is required to find a cycle in an n-vertex graph, since at most n − 1 edges can be tree edges.

The existence of a cycle in directed and undirected graphs can be determined by whether depth-first search (DFS) finds an edge that points to an ancestor of the current vertex (it contains a back edge).All the back edges which DFS skips over are part of cycles. In an undirected graph, the edge to the parent of a node should not be counted as a back edge, but finding any other already visited vertex will indicate a back edge. In the case of undirected graphs, only O(n) time is required to find a cycle in an n-vertex graph, since at most n − 1 edges can be tree edges.

关于环在有向（无向）图中的存在性，可以通过'''<font color="#ff8000"> 深度优先搜索（DFS）</font>'''来确定，具体方法是查找是否存在一条连边指向当前顶点的祖先点（包括回边）。DFS跳过的所有回边都是环的一部分。在无向图中，指向一个节点父级的连边不应算作后边，但是如果找到任何其他已访问的顶点可以视为后边。在无向图的情况下，只需要O（n）时间即可在n个顶点图中找到一个循环，因为最多n-1个边可以是树边。

关于环在有向或无向图中的存在，可以通过'''<font color="#ff8000"> 深度优先搜索（DFS）</font>'''来确定。具体方法是查找是否存在一条连边指向当前顶点的原始点（包括回边）。DFS跳过的所有回边都是环的一部分。在无向图中，指向一个节点上级的连边不应算作后边，但是如果找到任何其他已访问的顶点可以视为后边。在无向图的情况下，只需要O（n）时间即可在n个顶点图中找到一个循环，因为最多n-1个边可以是树边。

Many topological sorting algorithms will detect cycles too, since those are obstacles for topological order to exist.  Also, if a directed graph has been divided into strongly connected components, cycles only exist within the components and not between them, since cycles are strongly connected.

Many topological sorting algorithms will detect cycles too, since those are obstacles for topological order to exist.  Also, if a directed graph has been divided into strongly connected components, cycles only exist within the components and not between them, since cycles are strongly connected.

很多'''<font color="#ff8000"> 拓扑排序Topological sorting</font>'''算法也可以用于检测环，因为这些环阻碍了拓扑排序。另外，如果一个有向图被划分为具有强连接的不同组成部分，则环仅存在于这些组成部分内，而不是它们之间，因为环本身性质就是强连接的。

很多'''<font color="#ff8000"> 拓扑排序Topological sorting</font>'''算法也可以用于检测环，因为这些环阻碍了拓扑排序。另外，因为环本身性质是强连接的，所以如果一个有向图被划分为具有强连接的不同组成部分，则环仅存在于这些组成部分内，也并非它们之间。

 

For directed graphs, distributed message based algorithms can be used. These algorithms rely on the idea that a message sent by a vertex in a cycle will come back to itself. Distributed cycle detection algorithms are useful for processing large-scale graphs using a distributed graph processing system on a computer cluster (or supercomputer).

For directed graphs, distributed message based algorithms can be used. These algorithms rely on the idea that a message sent by a vertex in a cycle will come back to itself. Distributed cycle detection algorithms are useful for processing large-scale graphs using a distributed graph processing system on a computer cluster (or supercomputer).

对于有向图的环检测，可以使用基于分布式消息的算法。其概念是环中的某一个顶点发出了一条消息并最终返回，因此称为'''<font color="#ff8000"> 分布式环检测算法Distributed cycle detection algorithms</font>'''。通过在计算机集群（或超级计算机）上使用分布式图形处理系统，该方法非常适合大规模图的运算。

对于有向图的环检测，可以使用基于分布式消息的算法。其概念是环中的某一个顶点发出了一条消息并最终返回，因此被称为'''<font color="#ff8000"> 分布式环检测算法Distributed cycle detection algorithms</font>'''。通过在计算机集群（或超级计算机）上使用分布式图形处理系统，该方法非常适合大规模图的运算。