Ich versuche, die Zyklen in einem gerichteten Graphen mithilfe von Tarjans Algorithmus zu bestimmen, der in seiner Forschungsarbeit "Aufzählung der Elementarschaltungen eines gerichteten Graphen" vom September 1972 vorgestellt wurde.

Ich benutze Python, um den Algorithmus zu codieren, und eine Adjazenzliste, um die Beziehungen zwischen Knoten zu verfolgen.

In "G" unten zeigt Knoten 0 auf Knoten 1, Knoten 1 auf Knoten 4, 6, 7 ... usw.

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

Tarjans Algorithmus erkennt die folgenden Zyklen:

[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]

Ich habe auch Tiernans Algorithmus ausgeführt und er findet (richtig) 2extr Fahrräder

[3,4]

[3,6,5]

Ich würde mich über jede Hilfe freuen, wenn ich herausfinden könnte, warum Tarjan diese beiden Zyklen überspringt. Ein Problem in meinem Code vielleicht?