Как пройти только цикл в графе?

Question

Я пытаюсь выполнить ch23 в CLRS на MST, вот вопрос:

Учитывая граф G и минимальное остовное дерево T, предположим, что мы уменьшим вес одного из ребер, не находящихся вT.Дайте алгоритм для поиска минимального остовного дерева в модифицированном графе.

Решение, которое я нашел, состояло в том, чтобы добавить это новое измененное ребро в T, тогда в T будет создан ровно один простой цикл.этот цикл и удалите край максимального веса в этом цикле, вуаля , найден новый обновленный MST!

У меня вопрос, как мне только пройти узлына этом простом цикле?Поскольку обходы DFS / BFS могут выйти из цикла, если я, скажем, начну обход в T с одной конечной точки этого вновь добавленного ребра в T.

Одним из решений, которое я мог придумать, былонайдите biconnected components в T после добавления нового ребра.Будет найден только один BCC, который является новым сформированным простым циклом, тогда я могу добавить в мой код DFS специальное условие, говорящее только о прохождении ребер / узлов в этом BCC, и как только задний край найден,прекратить прохождение.

Редактировать: граф G подключен и ненаправлен между прочим

Answer 1

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

Этот алгоритм находит границы (или мосты) на графике за линейное время.Считайте E' набором срезов.Легко доказать, что каждое ребро в E' может не находиться на окружности.Таким образом, E / E' должны быть циклами на графике.

Вы можете использовать хэш-карту или функцию построения массива, чтобы найти разницу между вашим E и cut-edges set

Отсюда вы можете запустить простой цикл for, чтобы найти край максимального веса, который вы хотите удалить.

Надеюсь, это поможет!