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