Алгоритм Косараю для 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) выше x (который принадлежит S1) в стеке.

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

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