Прежде всего, я хотел бы уточнить, что я видел это: Нахождение «краев узкого места» на графике
И это не дубликат этого, а неудачное совпадение, которое человек по ошибке назвал мин-сокращением "узкое место".
Ребро узкого места - это ребро в сети потоков, которое при увеличении увеличивает максимальный поток в сети.
Так что это не обязательно минимальный срез, так как в случае графа типа o-1-> o-1-> o у нас нет ребер узкого места, но у нас есть минимальный срез.
(В этом примере o - это узлы, а ребро - * ->, где * - некоторое целое число.)
В любом случае, так что поиск всех узких мест, по-видимому, можно выполнить в O (V + E) (предполагается, что граф представлен в виде списка смежности), и я думаю, что способ сделать это - создать два массива размера V, который я назову INCOMING и OUTGOING, затем дважды перебираю каждый элемент списка смежности, первый раз увеличивая INCOMING [i] на значение ребер, идущих в каждый узел, и второй раз увеличивая OUTGOING [j] на значение, выходящее из каждого узла, где j - это узел, чей список смежности мы читаем, а i - это узел, ребро которого идет к нему в списке смежности.
Я думаю, что это работает в O (V + E) время, но я чувствую, что мое решение определенно более замысловато и трудно объяснить. Есть ли лучшее решение (не лучше, чем O (V + E), но просто более простое?)