概述
我正在使用Python来编写算法代码,并使用邻接列表来跟踪节点之间的关系.
所以在下面的“G”中,节点0指向节点1,节点1指向节点4,6,7 …等.
G = [[1],[4,7],[2,3],[5,8],[],[]] N = len(G) points = [] marked_stack = [] marked = [False for x in xrange(0,N)] g = None def tarjan(s,v,f): global g points.append(v) marked_stack.append(v) marked[v] = True for w in G[v]: if w < s: G[v].pop(G[v].index(w)) elif w == s: print points f = True elif marked[w] == False: if f == g and f == False: f = False else: f = True tarjan(s,w,g) g = f if f == True: u = marked_stack.pop() while (u != v): marked[u] = False u = marked_stack.pop() #v is Now deleted from mark stacked,and has been called u #unmark v marked[u] = False points.pop(points.index(v)) for i in xrange(0,N): marked[i] = False for i in xrange(0,N): points = [] tarjan(i,i,False) while (len(marked_stack) > 0): u = marked_stack.pop() marked[u] = False
Tarjan的算法检测以下周期:
[2,4]
[2,4,3,5]
[2,7,5,4]
[3,5]
我也完成了Tiernan的算法,它(正确地)找到了2个额外的周期:
[3,5]
我很感激任何帮助,找出为什么Tarjan跳过这两个周期.我的代码中可能存在问题吗?
for w in G[v]: if w < s: G[v].pop(G[v].index(w))
您正在遍历列表并从中弹出元素.这会使迭代停止按预期工作.
for w in G[v][:]:
总结
以上是编程之家为你收集整理的python – 使用Tarjan算法在图中枚举循环全部内容,希望文章能够帮你解决python – 使用Tarjan算法在图中枚举循环所遇到的程序开发问题。
如果您也喜欢它,动动您的小指点个赞吧