Recursive and iterative implementation on Kosaraju algorithm

Question

Kosaraju algorithm is mainly phrased as two recursive subroutines running postorderDFS twice to mark SCCs with linear time complexity O(V+E) below,

1. For each vertex \$u\$ of the graph, mark \$u\$ as unvisited. Let \$L\$ be empty.

2. For each vertex \$u\$ of the graph do Visit(\$u\$), where Visit(\$u\$) is the recursive subroutine:
       If \$u\$ is unvisited then:
           1. Mark \$u\$ as visited.
           2. For each out-neighbour \$v\$ of \$u\$, do Visit(\$v\$).
           3. Prepend \$u\$ to \$L\$.
       Otherwise do nothing.

3. For each element \$u\$ of \$L\$ in order, do Assign(\$u\$,\$u\$) where Assign(\$u\$,\$root\$) is the recursive subroutine:
       If \$u\$ has not been assigned to a component then:
           1. Assign \$u\$ as belonging to the component whose root is \$root\$.
           2. For each in-neighbour \$v\$ of \$u\$, do Assign(\$v\$,\$root\$).
       Otherwise do nothing.

Here is the recursive implementation in Python according to the above recipe,

def kosaraju(G): # postorder DFS on G to transpose the graph and push root vertices to L N = len(G) T, L, U = [[] for _ in range(N)], [], [False] * N def visit(u): if not U[u]: U[u] = True for v in G[u]: visit(v) T[v].append(u) L.append(u) for u in range(N): visit(u) # postorder DFS on T to pop root vertices from L and mark SCCs C = [None] * N def assign(u, r): if U[u]: U[u] = False C[u] = r for v in T[u]: assign(v, r) while L: u = L.pop() assign(u, u) return C 

The following iterative implementation scales well against the stack overflow due to excessively deep recursion. I revised the inner loop of the first iterative DFS so the linear time complexity O(V+E) is guaranteed now, however it deserves to be shared for further improvement.
I'll be glad about all your opinions or alternative implementations.

def kosaraju(G): # postorder DFS on G to transpose the graph and push root vertices to L N = len(G) T, L, U = [[] for _ in range(N)], [], [False] * N for u in range(N): if not U[u]: U[u], S = True, [u] while S: u, done = S[-1], True for v in G[u]: T[v].append(u) if not U[v]: U[v], done = True, False S.append(v) break if done: S.pop() L.append(u) # postorder DFS on T to pop root vertices from L and mark SCCs C = [None] * N while L: r = L.pop() S = [r] if U[r]: U[r], C[r] = False, r while S: u, done = S[-1], True for v in T[u]: if U[v]: U[v] = done = False S.append(v) C[v] = r break if done: S.pop() return C 

Test example:

G = [[1], [0, 2], [0, 3, 4], [4], [5], [6], [4], [6]] print(kosaraju(G)) # => [0, 0, 0, 3, 4, 4, 4, 7] 

Answer 1

(Work in progress)
I find the recursive variant pleasant enough to read:
• It picks up the names from the description referred
• The meaning of additional single-letter names isn't hard to guess
• there are comments to what's what

Main gripe: What can I use kosaraju(G) for, does it return something useful?
Have your source code document (non-private) parts:
Use docstrings.

Using loop-else, you don't need a done flag

def kosaraju(G): """ For a graph G given as a list of lists of node numbers find the strongly connected components. Use Kosaraju's algorithm: for each unvisited node, traverse and mark visited its out-neighbours, then add it to a sequence L for each unassigned node taken from L in reverse order, assign it to the same new SCC as all nodes reached via in-neighbours """ # postorder DFT on G to transpose the graph and push root vertices to L N = len(G) T, L, visited = [[] for _ in range(N)], [], [False] * N for u in range(N): if visited[u]: continue visited[u], stack = True, [u] while stack: u = stack[-1] for v in G[u]: T[v].append(u) if not visited[v]: visited[v] = True stack.append(v) break else: stack.pop() L.append(u) # print("L:", L) # try and follow en.wikipedia's hint and have # visited indication share storage with the final assignment assigned = visited # postorder DFT on T to pop root vertices from L and mark SCCs assigned = visited # C = [None] * N while L: root = L.pop() if not visited[root] is True: continue assigned[root] = root stack = [root] while stack: # print("T[" + stack[-1] + "]: " + T[stack[-1]]) for v in T[stack[-1]]: if visited[v] is True: stack.append(v) assigned[v] = root break else: stack.pop() return assigned if __name__ == '__main__': G = [[], [5, 4], [3, 11, 6], [7], [2, 8, 10], [7, 5, 3], [8, 11], [9], [2, 8], [3], [1], [9, 6]] print(kosaraju(G))