python - 使用 Tarjan 算法枚举图中的循环

Question

我正在尝试使用 Tarjan 的算法确定有向图中的循环，该算法在他 1972 年 9 月的研究论文“有向图的基本电路的枚举”中提出。

我使用 Python 对算法进行编码，并使用邻接列表来跟踪节点之间的关系。

所以在下面的“G”中，节点 0 指向节点 1，节点 1 指向节点 4、6、7……等等。

G = [[1], [4, 6, 7], [4, 6, 7], [4, 6, 7], [2, 3], [2, 3], [5, 8], [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、6、5]

[2、4、3、7、5]

[2, 6, 5]

[2、6、5、3、4]

[2, 7, 5]

[2、7、5、3、4]

[3, 7, 5]

我也完成了 Tiernan 的算法，它（正确地）找到了 2 个额外的循环：

[3,4]

[3,6,5]

如果能帮助我找出 Tarjan 跳过这两个周期的原因，我将不胜感激。也许我的代码有问题？

Answer 1

在这些行中：

for w in G[v]:
    if w < s:            
        G[v].pop(G[v].index(w))

您正在遍历列表并从中弹出元素。这会阻止迭代按预期工作。

如果您更改代码以制作列表的副本，则会产生额外的循环：

for w in G[v][:]:

Answer 2

下面的代码运行没有错误并且具有预期的输出。

G = [[1], [4, 6, 7], [4, 6, 7], [4, 6, 7], [2, 3], [2, 3], [5, 8], [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:
            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

输出：

[2, 4]
[2, 4, 3, 6, 5]
[2, 4, 3, 7, 5]
[2, 6, 5]
[2, 6, 5, 3, 4]
[2, 7, 5]
[2, 7, 5, 3, 4]
[3, 4]
[3, 6, 5]
[3, 7, 5]