使用Tarjan算法枚举图中的环

Question

我正在尝试使用Tarjan算法确定有向图中的循环。此算法详细介绍于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算法，它（正确地）找到了额外的两个环：

[3,4]

[3,6,5]

我想知道为什么Tarjan会忽略这两个环。也许是我的代码有问题？

- janvdl

---

这是与图形区间分析相同的东西吗？ - paulm

嗨，保罗，我不是完全确定，但在查看图区间的维基百科页面后，我认为答案是否定的。可能（我想）图中的循环可以被视为图的区间，但循环只是图的区间的子集。我应该指出这段代码有一个错误，更新后的代码可在以下网址找到：https://github.com/janvdl/python_tarjan/blob/master/tarjan.py - janvdl

对于那些有兴趣实现这个算法的人，上面的代码包含一个错误。我在我的 Github 页面上提供了 Tarjan 算法的 Python（https://github.com/janvdl/python_tarjan/blob/master/tarjan.py）和 Golang（https://github.com/janvdl/go_tarjan/blob/master/tarjan.go）实现，以及 Tiernan 算法的 Python 实现（https://github.com/janvdl/python_tiernan/blob/master/tiernan.py）。 - janvdl

Answer 1

在这些代码行中：

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

你正在遍历一个列表并从中弹出元素。这会导致迭代无法按预期工作。

如果你改变代码，复制列表，就可以产生额外的循环。

for w in G[v][:]:

- Peter de Rivaz

---

StackOverflow从来不会让人失望。非常感谢，你帮我省去了很多麻烦！ - janvdl

嗨，我想问一个问题：'g'标志有什么用？ - Bruno Peixoto

在Tarjan的论文中，g用于保存回溯的递归调用的返回值，该值指示是否找到了继续堆栈上部分路径的基本电路（在这种情况下，需要取消标记顶点，因为可能存在更多的循环）。如果您想要更多详细信息，最好提出一个新问题。 - Peter de Rivaz

@PeterdeRivaz - 有关这个问题和低链接值算法版本以及即时分配索引的问题，您似乎拥有深入的专业知识，所以我想标记您 :) - aksg87

Answer 2

我有点好奇，因为我没有看到低链接值的使用或即时分配索引，我认为这是用于查找强连通分量的Tarjan算法的情况。这是不同的算法还是修改过的算法？

我重命名了一些变量，试图使其更易于理解：

G = [
    [1],
    [4, 6, 7],
    [4, 6, 7],
    [4, 6, 7],
    [2, 3],
    [2, 3],
    [5, 8],
    [5, 8],
    [],
    [],
]
# %%


def entry_tarjan(G_):

    G = G_.copy()

    marked = [False] * len(G_)
    cycles = []
    point_stack = []
    marked_stack = []

    def tarjan(src, v):
        nonlocal cycles, marked, G
        cycle_found = False
        point_stack.append(v)
        marked_stack.append(v)
        marked[v] = True

        for nei in G[v]:
            if nei < src:
                # prevent prior traversals
                G[nei] = []

            elif nei == src:
                # neighbor is source => cycle
                cycles.append(point_stack.copy())
                cycle_found = True

            elif marked[nei] == False:
                # dfs continues
                cycle_in_nei = tarjan(src, nei)
                cycle_found = cycle_found or cycle_in_nei

        if cycle_found == True:
            # adjust marked to current vertex
            while marked_stack[len(marked_stack) - 1] != v:
                u = marked_stack.pop()
                marked[u] = False
            marked_stack.pop()
            marked[v] = False

        point_stack.pop()
        return cycle_found

    for i in range(len(G)):
        # start at each vertex
        tarjan(i, i)

        while marked_stack:
            u = marked_stack.pop()
            marked[u] = False

    return cycles


print(entry_tarjan(G))

- aksg87

Answer 3

以下代码可以正常运行且输出结果符合预期。

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]

- Bruno Peixoto