Алгоритм Косараю для SCC

Question

Может ли кто-нибудь объяснить мне логику алгоритма Косараджу для поиска подключенного компонента?

Я прочитал описание , хотя я не могу понять, как DFS на обращенном графике может обнаружитьколичество сильно связанных компонентов.

def dfs(visited, stack, adj, x):
    visited[x] = 1

    for neighbor in adj[x]:
        if (visited[neighbor]==0):
            dfs(visited, stack, adj, neighbor)

    stack.insert(0, x)
    return stack, visited

def reverse_dfs(visited, adj, x, cc):
    visited[x] = 1

    for neighbor in adj[x]:
        if (visited[neighbor]==0):
            cc += 1
            reverse_dfs(visited, adj, neighbor,cc)
    print(x)
    return cc


def reverse_graph(adj):
    vertex_num = len(adj)
    new_adj = [ [] for _ in range(vertex_num)]
    for i in range(vertex_num):
        for j in adj[i]:
            new_adj[j].append(i)
    return new_adj


def find_post_order(adj):
    vertex_num = len(adj)
    visited = [0] * vertex_num
    stack = []

    for vertex in range(vertex_num):
        if visited[vertex] == 0:
            stack, visited = dfs(visited, stack, adj, vertex)

    return stack


def number_of_strongly_connected_components(adj):
    vertex_num = len(adj)
    new_adj = reverse_graph(adj)
    stack = find_post_order(adj)

    visited = [0] * vertex_num
    cc_num = 0
    while (stack):
        vertex = stack.pop(0)
        print(vertex)
        print('------')
        if visited[vertex] == 0:
            cc_num = reverse_dfs(visited, new_adj, vertex, cc_num)
    return cc_num

if __name__ == '__main__':
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    n, m = data[0:2]
    data = data[2:]
    edges = list(zip(data[0:(2 * m):2], data[1:(2 * m):2]))
    adj = [[] for _ in range(n)]
    for (a, b) in edges:
        adj[a - 1].append(b - 1)
    print(number_of_strongly_connected_components(adj))

Выше вы можете найти мою реализацию.Я предполагаю, что начальный DFS и обратная операция выполнены правильно, но я не могу понять, как правильно выполнить второй DFS.Заранее спасибо.

Answer 1

Первое, что вы должны заметить, это то, что набор сильно связанных компонентов одинаков для графа и его реверса.Фактически, алгоритм фактически находит набор сильно связанных компонентов в обращенном графе, а не оригинал (но это нормально, потому что оба графика имеют одинаковый SCC).

Первое выполнение DFS приводит к стеку, которыйсодержит вершины в определенном порядке, так что, когда вторая DFS выполняется над вершинами в этом порядке (на обращенном графе), она правильно вычисляет SCC.Таким образом, вся цель запуска первой DFS - найти порядок вершин графа, который служит для выполнения алгоритма DFS на обращенном графе.Теперь я объясню, каково свойство порядка вершин в стеке и как оно служит для выполнения DFS на обращенном графе.

Итак, каково свойство стека?Представьте, что S1 и S2 являются двумя сильно связанными компонентами в графе, и что в перевернутом графе S2 достижим из S1.Очевидно, что S1 также не может быть достигнут из S2, потому что если бы это было так, S1 и S2 были бы объединены в один компонент.Пусть x - верхняя вершина среди вершин в S1 (то есть все остальные вершины в S1 находятся ниже x в стеке).Аналогично, пусть y будет верхней вершиной среди вершин в S2 (опять же, все остальные вершины в S2 находятся ниже y в стеке).Свойство состоит в том, что у (который принадлежит S2) находится в стеке выше х (который принадлежит S1).

Почему это свойство полезно?Когда мы выполняем DFS на обращенном графике, мы делаем это в соответствии с порядком стека.В частности, мы исследуем y, прежде чем исследуем x.Исследуя y, мы исследуем каждую вершину S2, и поскольку ни одна вершина S1 не достижима из S2, мы исследуем все вершины S2, прежде чем исследуем любую вершину S1.Но это верно для любой пары соединенных компонентов, так что один достижим от другого.В частности, вершина в верхней части стека принадлежит компоненту приемника, и после того, как мы закончили исследование этого компонента приемника, верхняя вершина снова принадлежит приемнику относительно графа, индуцированного еще не исследованными вершинами.

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