Алгоритм Косараджу - вычисление SCC

Question

Для данного ориентированного графа G мне нужно вычислить его сильно связные компоненты (SCC), используя алгоритм Косараджу. Насколько я понял, шаги алгоритма следующие:

1. Пусть Grev = G, все дуги перевернуты.
2. Запустите DFS (поиск в глубину) на Grev, чтобы вычислить время окончания узлов
3. Запустите DFS на G, чтобы обнаружить SCC

Мне удалось найти правильное время отделки всех узлов. Я частично понимаю, что мне следует назначить время окончания для его соответствующих значений узлов, перевернуть график Grev и снова запустить DFS на перевернутом графе (теперь G) с временем окончания, поскольку узлы обработки значений узлов в порядке убывания времени окончания. Я правильно понимаю? Если да, то как я могу это закодировать?

Вот до чего я дошел:

# Number of elements in graph + 1
graph_elem = 10

def dfs_iterative(graph):
    # variable initialization

    for i in range(graph_elem - 1, 0, -1):
        stack.append(i)

        while stack:
            v = ... # Get top of stack

            # If the top of the stack is not explored, or if any of the children of 
            # the node on the top of the stack are unexplored, then continue the traversal
            if ...:
                #Mark explored

                for head in graph[v]:
                    if head not in explored:
                        stack.append(head)
                    # Prevent the loop iterating through all of the children like BFS

            else:
                # Get finishing time for v

    return finishing_times

# Graph represented in a list through edges
# index represents the tail node of the edge, and g[index] is the head node
# Example edges of g: (1, 4), (2, 8), (3, 6), etc.
g = [[], [4], [8], [6], [7], [2], [9], [1], [5, 6], [7, 3]]
rev_g = [[], [7], [5], [9], [1], [8], [3, 8], [4, 9], [2], [6]]
fin_times = dfs_iterative(rev_g)

В fin_times должно быть {3: 1, 5: 2, 2: 3, 8: 4, 6: 5, 9: 6, 1: 7, 4: 8, 7: 9}, и, как упоминалось ранее, это правильно. Что мне на самом деле делать сfin_times сейчас?

Кроме того, причина, по которой я делаю это итеративно, а не рекурсивно, заключается в том, что входной файл для назначения слишком велик, и программа может достичь рекурсивных ограничений.

Изменить: ответив на вопрос, я понял, что вопрос не соответствует Кодексу чести курса. Я отредактировал вопрос, чтобы исключить части кода, которые могут выдать решение задания.

Answer 1

Поскольку мой вопрос был только:

Что делать с fin_times толковый словарь?

Я предлагаю решение только этого вопроса, чтобы не предлагать полное решение задания.

Так что ответ, казалось, обращал вспять fin_times словарь, чтобы ключи стали значениями, и наоборот:

order = dict((v, k) for k, v in finishing_times.items())

{1: 3, 2: 5, 3: 2, 4: 8, 5: 6, 6: 9, 7: 1, 8: 4, 9: 7}

Затем мы запускаем DFS на узлах обработки G в порядке убывания времени завершения (в данном случае вершина 7 со временем завершения 9). Соответствует коду в вопросе вместо:

for i in range(graph_elem - 1, 0, -1):
        stack.append(i)

Мы пишем:

order = dict((v, k) for k, v in finishing_times.items())

for i in range(graph_elem - 1, 0, -1):
        vertex = order[i]
        if vertex not in explored:
            stack.append(vertex)
            explored.add(vertex)

            // DFS code and SCC size computation...