更改

关于环在有向或无向图中的存在，可以通过'''深度优先搜索（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 | 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个边可以是树边。

关于环在有向或无向图中的存在，可以通过'''深度优先搜索 depth-first search（DFS）'''来确定。具体方法是查找是否存在一条连边指向当前顶点的原始点（包括回边）。<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 | title=Algorithms | chapter=Graph algorithms | year=1983 | publisher=Addison–Wesley | url-access=registration | url=https://archive.org/details/algorithms00sedg }}</ref>在无向图中，指向一个节点上级的连边不应算作后边，但是如果找到任何其他已访问的顶点可以视为后边。在无向图的情况下，只需要<math>\mathcal{O}(n)</math>时间即可在<math>n</math>个顶点图中找到一个循环，因为最多<math>n-1</math>个边可以是树边。

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

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

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

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

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

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

<ref>{{cite book

<ref>{{cite book | last = Silberschatz | first = Abraham |author2=Peter Galvin |author3=Greg Gagne| title = Operating System Concepts | url = https://archive.org/details/operatingsystemc0006silb

  | last = Silberschatz

   | url-access = registration | publisher = John Wiley & Sons, INC. | year = 2003 | pages = [https://archive.org/details/operatingsystemc0006silb/page/260 260]}}</ref>

  | first = Abraham

 

  |author2=Peter Galvin |author3=Greg Gagne

<br>

  | title = Operating System Concepts

  | url = https://archive.org/details/operatingsystemc0006silb

   | url-access = registration

  | publisher = John Wiley & Sons, INC.

  | year = 2003

  | pages = [https://archive.org/details/operatingsystemc0006silb/page/260 260]

  | isbn = 0-471-25060-0}}</ref>

==  环覆盖图 ==

==  环覆盖图 ==