python – 使用Tarjan算法在图中枚举循环

5b51 2022/1/14 8:20:14 python 字数 2804 阅读 467 来源 www.jb51.cc/python

我试图使用Tarjan算法确定有向图中的周期,该算法在1972年Septermber的研究论文“有向图的基本电路的枚举”中提出. 我正在使用Python来编写算法代码,并使用邻接列表来跟踪节点之间的关系. 所以在下面的“G”中,节点0指向节点1,节点1指向节点4,6,7 …等. G = [[1], [4, 6, 7], [4, 6, 7], [4, 6, 7], [2, 3], [2, 3], [

概述

我正在使用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算法在图中枚举循环所遇到的程序开发问题。

如果您也喜欢它,动动您的小指点个赞吧

除非注明，文章均由 laddyq.com 整理发布，欢迎转载。

转载请注明：
链接：http://laddyq.com
来源：laddyq.com
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

python – 使用Tarjan算法在图中枚举循环

概述

总结

分类汇总

您的鼓励是对我最大的支持