Есть ли способ быстро найти все ребра, которые являются частью цикла (задние ребра) в неориентированном / ориентированном графе?
У меня есть минимальное остовное дерево. Я добавляю к этому преимущество. Конечно, цикл сформирован. Мне нужно найти все ребра, которые являются частью этого цикла, т. Е. Все задние ребра. Как быстро это можно сделать? Мое решение —
Например, если это edge (1,4), добавьте 4 к Adj (1) во всех местах и запускайте dfs каждый раз. Например. если у Adj (1) было 2,3,5, сначала добавьте 4 перед 2, запустите DFS. Я получу задний край. Затем добавьте 4 между 2 и 3 и запустите dfs. Я получаю еще один задний край. Затем между 3 и 5 и так далее. Есть ли более быстрый способ сделать это?
Решение
В дереве у вас есть один (простой) маршрут между любой парой вершин. Если вы добавляете ребро (i,j)сначала найдите маршрут в дереве между i и j, а затем у вас будет свой цикл — он состоит из всех вершин этого маршрута (и превращается в цикл после добавления (i,j) как край).
Другие решения
Вы ищете сильно связанные компоненты графа, которые можно найти с помощью Алгоритм Тарьяна (среди других).