更改

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

关于环在有向或无向图中的存在，可以通过'''深度优先搜索（DFS depth-first search）'''来确定。具体方法是查找是否存在一条连边指向当前顶点的原始点（包括回边）。<ref>{{cite book|last=Tucker|first=Alan|authorlink=Alan Tucker|title=Applied Combinatorics |year=2006|publisher=John Wiley & sons|location=Hoboken|isbn=978-0-471-73507-6|edition=5th|page=49|chapter=Chapter 2: Covering Circuits and Graph Colorings}}</ref>DFS跳过的所有回边都是环的一部分。<ref name="sedgewick">{{citation | first=Robert | last=Sedgewick | author-link=Robert Sedgewick (computer scientist) | title=Algorithms | chapter=Graph algorithms | year=1983 | publisher=Addison–Wesley | isbn=0-201-06672-6 | url-access=registration | url=https://archive.org/details/algorithms00sedg }}</ref>在无向图中，指向一个节点上级的连边不应算作后边，但是如果找到任何其他已访问的顶点可以视为后边。在无向图的情况下，只需要O（n）时间即可在n个顶点图中找到一个循环，因为最多n-1个边可以是树边。

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

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

环检测的应用还包括使用'''<font color="#ff8000"> 等待图Wait-for graphs</font>'''来检测并发系统中的'''<font color="#ff8000"> 死锁Deadlocks</font>'''。

环检测的应用还包括使用'''<font color="#ff8000"> 等待图Wait-for graphs</font>'''来检测并发系统中的'''<font color="#ff8000"> 死锁Deadlocks</font>'''。

==  环覆盖图 ==

==  环覆盖图 ==