Определение, является ли ребро самым тяжелым ребром в цикле

Question

Таким образом, кажется, что определение того, находится ли ребро в минимальном остовном дереве, может быть сведено к вопросу о том, является ли ребро самым тяжелым ребром в некотором цикле. Я знаю, как определить, находится ли ребро в цикле, используя DFS, но как определить, является ли оно самым тяжелым ребром в этом цикле? Это просто найти цикл и выбрать самый тяжелый край в нем?

Answer 1

Предполагая, что все ребра имеют разные веса, простым и довольно элегантным алгоритмом для этого будет создание модифицированной DFS. Обратите внимание, что если этот край является самым тяжелым краем в некотором цикле, то, если вы посмотрите на график, образованный удалением всех ребер, которые тяжелее текущего ребра, должен быть некоторый путь от конечной точки ребра до начала ребро, потому что этот путь в сочетании с самим ребром образует цикл с заданным ребром, являющимся самым тяжелым таким ребром. И наоборот, если нет цикла, содержащего ребро, для которого данное ребро является самым тяжелым, то если бы вы провели поиск в этом графике от конца ребра до источника, вы не смогли бы вернуться к источнику края, так как в противном случае вы могли бы завершить его в цикл. Это дает следующий простой алгоритм: создать DFS в исходном графе от конечной точки ребра до источника, но всякий раз, когда вы сталкиваетесь с ребром, которое тяжелее исходного ребра, не обрабатывайте его (это имитирует удаление его из график). Если ваша DFS переносит вас от конца ребра обратно к источнику, то вы знаете, что должен быть некоторый цикл, для которого ребро является самым тяжелым ребром, и если такого цикла нет, вы не сможете получить вернуться к истоку края.

В случае, если ребра не различимы, вы выполняете тот же поиск, что и выше, но вы удаляете все ребра, вес которых был больше или равен весу текущего ребра. Причина этого заключается в том, что если в этом преобразованном графе есть путь от конца ребра до начала ребра, вы наверняка знаете, что мы не использовали ни одно ребро, стоимость которого равна исходное ребро, поэтому любой найденный путь может быть завершен в цикл, где заданное ребро является самым тяжелым. Если пути нет, то либо

1. Каждый цикл, содержащий данное ребро, имеет какое-то строго тяжелое ребро, или
2. Каждый цикл, содержащий данное ребро, имеет некоторое ребро, стоимость которого равна стоимости.

В любом случае это не самое тяжелое ребро в цикле.

Время выполнения этого алгоритма составляет O (m + n), время, необходимое для выполнения стандартной DFS.

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