2,443
个编辑
更改
跳到导航
跳到搜索
第47行：
第47行： − 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 [[Depth-first search#Output of a depth-first search|back edge]]). 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. − + − 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 component]]s, 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>'''算法也可以用于检测环，因为这些环阻碍了拓扑排序。另外，因为环本身性质是强连接的，所以如果一个有向图被划分为具有强连接的不同组成部分，则环仅存在于这些组成部分内，也并非它们之间。 − − − 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). − − − Applications of cycle detection include the use of [[wait-for graph]]s to detect [[deadlock]]s in concurrent systems. − − Applications of cycle detection include the use of wait-for graphs to detect deadlocks in concurrent systems.
→环检测
== 环检测 ==
== 环检测 ==
关于环在有向或无向图中的存在，可以通过'''<font color="#ff8000"> 深度优先搜索（DFS）</font>'''来确定。具体方法是查找是否存在一条连边指向当前顶点的原始点（包括回边）。DFS跳过的所有回边都是环的一部分。在无向图中，指向一个节点上级的连边不应算作后边，但是如果找到任何其他已访问的顶点可以视为后边。在无向图的情况下，只需要O（n）时间即可在n个顶点图中找到一个循环，因为最多n-1个边可以是树边。
关于环在有向或无向图中的存在，可以通过'''深度优先搜索（DFS depth-first search）'''来确定。具体方法是查找是否存在一条连边指向当前顶点的原始点（包括回边）。DFS跳过的所有回边都是环的一部分。在无向图中，指向一个节点上级的连边不应算作后边，但是如果找到任何其他已访问的顶点可以视为后边。在无向图的情况下，只需要O（n）时间即可在n个顶点图中找到一个循环，因为最多n-1个边可以是树边。
很多'''拓扑排序Topological sorting'''算法也可以用于检测环，因为这些环阻碍了拓扑排序。另外，因为环本身性质是强连接的，所以如果一个有向图被划分为具有强连接的不同组成部分，则环仅存在于这些组成部分内，也并非它们之间。
对于有向图的环检测，可以使用基于分布式消息的算法。其概念是环中的某一个顶点发出了一条消息并最终返回，因此被称为'''<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>'''。