如何检查有向图是否是无环图?以及该算法是如何调用的?我希望能提供参考。
我会尝试对图进行拓扑排序,如果不能,那么它就有循环。
进行简单的深度优先搜索不足以找到循环。在 DFS 中可以多次访问一个节点而不存在循环。根据您开始的位置,您也可能无法访问整个图表。
您可以按如下方式检查图形的连接组件中的循环。找到一个只有出边的节点。如果不存在这样的节点,则存在环路。在该节点上启动 DFS。遍历每条边时,检查该边是否指向堆栈中已有的节点。这表明循环的存在。如果找不到这样的边,则该连接组件中不存在循环。
正如 Rutger Prins 指出的,如果你的图没有连通,你需要对每个连通分量重复搜索。
作为参考,Tarjan 的强连通分量算法密切相关。它还将帮助您找到循环,而不仅仅是报告它们是否存在。
Introduction to Algorithms
(第二版)的引理 22.11 指出:
有向图 G 是非循环的当且仅当 G 的深度优先搜索没有产生后边
解决方案1: Kahn算法检查循环。主要思想:维护一个队列,将入度为零的节点添加到队列中。然后将节点一一剥离,直到队列为空。检查是否存在任何节点的入边。
解决方案2:Tarjan算法检查强连通分量。
解决方案3:DFS。使用整数数组来标记节点的当前状态: 即 0——表示该节点之前未被访问过。 -1——表示该节点已被访问,并且其子节点正在被访问。 1——表示该节点已被访问,并且已完成。 所以如果一个节点在进行DFS时状态为-1,则说明一定存在环。
刚刚在 Google 面试中遇到了这个问题。
你可以尝试按拓扑排序,即 O(V + E),其中 V 是顶点数,E 是边数。当且仅当可以做到这一点时,有向图才是非循环的。
递归地删除叶节点,直到没有剩下,如果剩下多个节点,则有一个循环。除非我弄错了,否则这是 O(V^2 + VE)。
然而,一种高效的 DFS 式算法,最坏情况 O(V + E) 是:
function isAcyclic (root) {
const previous = new Set();
function DFS (node) {
previous.add(node);
let isAcyclic = true;
for (let child of children) {
if (previous.has(child) || DFS(child)) {
isAcyclic = false;
break;
}
}
previous.delete(node);
return isAcyclic;
}
return DFS(root);
}
ShuggyCoUk 给出的解决方案是不完整的,因为它可能没有检查所有节点。
def isDAG(nodes V):
while there is an unvisited node v in V:
bool cycleFound = dfs(v)
if cyclefound:
return false
return true
时间复杂度为 O(n+m) 或 O(n^2)
我知道这是一个老话题,但对于未来的搜索者,这里是我创建的 C# 实现(没有声称它是最有效的!)。这样做的目的是使用一个简单的整数来标识每个节点。您可以按照自己喜欢的方式装饰它,只要您的节点对象散列和等于正确。
对于非常深的图,这可能会产生很高的开销,因为它在深度的每个节点上创建一个哈希集(它们在广度上被破坏)。
您输入要搜索的节点以及到该节点的路径。
检查任何给定节点下方的循环时,只需将该节点与空哈希集一起传递
private bool FindCycle(int node, HashSet<int> path)
{
if (path.Contains(node))
return true;
var extendedPath = new HashSet<int>(path) {node};
foreach (var child in GetChildren(node))
{
if (FindCycle(child, extendedPath))
return true;
}
return false;
}
做DFS时不应该有任何后边。在做DFS时跟踪已经访问过的节点,如果在当前节点和现有节点之间遇到边,则图有环。
这里有一个快速代码来查找图表是否有循环:
func isCyclic(G : Dictionary<Int,Array<Int>>,root : Int , var visited : Array<Bool>,var breadCrumb : Array<Bool>)-> Bool
{
if(breadCrumb[root] == true)
{
return true;
}
if(visited[root] == true)
{
return false;
}
visited[root] = true;
breadCrumb[root] = true;
if(G[root] != nil)
{
for child : Int in G[root]!
{
if(isCyclic(G,root : child,visited : visited,breadCrumb : breadCrumb))
{
return true;
}
}
}
breadCrumb[root] = false;
return false;
}
let G = [0:[1,2,3],1:[4,5,6],2:[3,7,6],3:[5,7,8],5:[2]];
var visited = [false,false,false,false,false,false,false,false,false];
var breadCrumb = [false,false,false,false,false,false,false,false,false];
var isthereCycles = isCyclic(G,root : 0, visited : visited, breadCrumb : breadCrumb)
这个想法是这样的:一个普通的 dfs 算法,带有一个数组来跟踪访问过的节点,还有一个附加数组作为通向当前节点的节点的标记,这样每当我们为某个节点执行 dfs 时,节点我们将其在标记数组中的对应项设置为 true ,这样当遇到一个已经访问过的节点时,我们检查其在标记数组中的对应项是否为 true ,如果为 true 则它是允许其自身的节点之一 (因此是一个循环),诀窍是每当节点的 dfs 返回时,我们将其相应的标记设置回 false ,这样,如果我们从另一条路线再次访问它,我们就不会被愚弄。
这是我的 剥离叶节点算法 的 Ruby 实现。
def detect_cycles(initial_graph, number_of_iterations=-1)
# If we keep peeling off leaf nodes, one of two things will happen
# A) We will eventually peel off all nodes: The graph is acyclic.
# B) We will get to a point where there is no leaf, yet the graph is not empty: The graph is cyclic.
graph = initial_graph
iteration = 0
loop do
iteration += 1
if number_of_iterations > 0 && iteration > number_of_iterations
raise "prevented infinite loop"
end
if graph.nodes.empty?
#puts "the graph is without cycles"
return false
end
leaf_nodes = graph.nodes.select { |node| node.leaving_edges.empty? }
if leaf_nodes.empty?
#puts "the graph contain cycles"
return true
end
nodes2 = graph.nodes.reject { |node| leaf_nodes.member?(node) }
edges2 = graph.edges.reject { |edge| leaf_nodes.member?(edge.destination) }
graph = Graph.new(nodes2, edges2)
end
raise "should not happen"
end
这是我的伪代码实现:
bool Acyclacity_Test
InitColor() //Sets to WHITE every vertex
while there is a node v in V:
if (v.color == WHITE) then
tmp = Aux_Acy(v);
if ( not tmp ) return false
return true
END
bool Aux_Acy(u)
u.color = GREY
for each node v in Adj(u)
if(v.color == GREY) return false
else if(v.color == WHITE) tmp = Aux_Acy(v)
if(!tmp) return false;
u.color = BLACK
return true
END
您可以使用我的答案中的查找循环反转https://stackoverflow.com/a/60196714/1763149
def is_acyclic(graph):
return not has_cycle(graph)