这就是我所尝试的:
VISITED = 1
UNVISITED = -1
VISITING = 0
def dfs(g, start, num):
state = {}
for i in range(num):
state[i] = UNVISITED
stack = [start]
while(stack != []):
node = stack.pop()
if(state[node] == VISITED):
continue
state[node] = VISITING
if(node in g):
for i in g[node]:
stack.append(i)
if(state[i] == VISITED):
return True
state[node] = VISITED
def detect_cycle(n, edges):
g = {}
# adjacency list
for (x, y) in edges:
g[x] = g.get(x, []) + [y]
for i in range(n):
if(i in g):
if(dfs(g, i, n) == True):
return True
return False
print(detect_cycle(5, [[1,4],[2,4],[3,1],[3,2]])) # outputs True (should be false)
图表的图像:
上面的示例中edges = [[1,4],[2,4],[3,1],[3,2]]
不包含循环,但返回True
。所以我的算法不适用于这种情况
我试图使用着色图检测循环算法,但我不确定如何在没有递归的情况下做到这一点
我试图遵循的算法是迭代的:Detecting a cycle in a directed graph using DFS?
如果一个访问节点(灰色)遇到另一个访问节点的边,则检测循环。我在初始代码中遇到的问题是,无法以回溯方式设置已访问的节点(黑色)。新代码现在有ENTER=0和EXIT=1。Enter=0表示这是我第一次访问该节点,我将其设置为灰色(访问),第二次访问该节点时,出口将为1,这样我就可以将其设置为黑色(完全访问)
相关问题 更多 >
编程相关推荐