Как построить массив, чтобы представить отношения узлов в сильно связанном компоненте?
Для ориентированного графа G(V, E) с n узлами я хочу создать целочисленный массив a, а его длина равна n. Если есть путь от узла 1 до 2, то a[1] <= a[2], если они находятся в одном и том же сильно связанном компоненте a[1] = a[2], если нет пути от узла 2 до 3, мы имеем a[2] > a[3],
Я думаю, что временная сложность должна быть O(n + m), потому что временная сложность поиска сильно связанного компонента такова. Но я не уверен, как вывести массив для него, кто-нибудь может помочь? Благодарю.
2 ответа
Как только вы нашли все сильно связанные компоненты (SCC) графа, вы можете построить конденсацию графа, заключив каждый SCC в одну вершину. Конденсация представляет собой ориентированный ациклический граф, в котором вы можете нумеровать вершины, используя топологическую сортировку. Каждый шаг имеет линейную сложность.
Алгоритм Тарьяна SCC уже делает почти то, что вы хотите, вам нужно только один дополнительный шаг бухгалтерии.
Напомним, что SCC Тарьяна выводит сильно связанные компоненты один за другим уже в топологически отсортированном порядке. То есть все, что вам нужно сделать, это сохранить индекс SCC во всех ячейках, которые соответствуют узлам текущего SCC. Это уже тот массив, который вам нужен.
В зависимости от представления графика и реализации, вы можете сохранить N - idx в ячейках массива, где N общее количество найденных кластеров. Это потому, что по сути не имеет значения, в каком направлении вы пересекаете график: сильно связанные компоненты графика с перевернутыми стрелками одинаковы. Это зависит от того, что проще и быстрее получить доступ к вашей конкретной реализации.
Алгоритм Тарьяна дважды пересекает граф и имеет время выполнения O(|V| + |E|). Сохранение дополнительного массива ничего не добавляет к уравнению.