Может оказаться полезным использовать теорему о разложении потока (см. §6.2 из этого обсуждения максимального потока ), в которой говорится, что любой поток может быть разбит нанабор путей и циклов потока.Кроме того, на графике может быть не более m общих путей и циклов потока.Это означает, что одним простым алгоритмом исключения циклов потока было бы найти все пути потока в графе, а затем удалить весь оставшийся поток в графе, поскольку он должен соответствовать циклам потока.
Чтобы найти путь потокаили цикл, вы можете использовать простой поиск в глубину из исходного узла.Начиная с исходного узла, продолжайте следовать ребрам, пока вы не нажмете на терминальный узел или не посетите ранее посещенный узел.Если вы нажмете на конечный узел, то выбранный вами путь будет простым потоком.Если вы встречаетесь с каким-то узлом дважды, вы только что нашли цикл потока (образованный циклом, который вы только что нашли).Если вы затем удалите траекторию / цикл потока из графика и повторите, вы в конечном итоге обнаружите все траектории и циклы потока.Вы знаете, что все готово, когда нет потоков, несущих поток, из исходного кода.Если каждый раз, когда вы находите путь потока, вы записываете общий поток по всем его краям, вы можете устранить циклический поток, повторяя его до тех пор, пока пути потока не останутся, очистив поток в сети, а затем добавив обратно в пути потока.1007 *
Поскольку каждая DFS занимает время O (m + n) и существует не более O (m) путей потока, общее время выполнения этого шага составляет O (m 2 + mn), чтоявляется полиномом от размера графа.
Надеюсь, это поможет!