我试图使用Tarjan算法确定有向图中的周期,该算法在1972年Septermber的研究论文“有向图的基本电路的枚举”中提出.
我正在使用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跳过这两个周期.我的代码中可能存在问题吗？