Как получить срез с помощью алгоритма Эдмондса – Карпа? - PullRequest
Новая
       75

Как получить срез с помощью алгоритма Эдмондса – Карпа?

8 голосов
/ 21 марта 2011

Я реализовал алгоритм Эдмондса-Карпа, используя псевдокод, который я нашел на вики-странице алгоритма Эдмондса-Карпа: http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm

Отлично работает, но вывод алгоритма - это максимальное значение потока (минимальное значение среза), мне нужен список ребер, которые этот срез содержит

Я пытался изменить алгоритм, но безуспешно, ребята, вы можете помочь?

Спасибо

Ответы [ 3 ]

3 голосов
/ 21 марта 2011

Если у вас уже есть поток, то рассчитайте остаточный график. Затем выполните поиск в глубину из источника (или поиск в ширину, я не думаю, что это имеет значение), чтобы вычислить вершины в одной половине разреза (S). Остальные вершины находятся в другой половине вашего разреза, T.

Это дает вам ваш разрез (S, T). Если вам конкретно нужны ребра между S и T, вы можете перебрать все ребра, выбирая те, которые соединяют S и T. (Хотя может быть более элегантный способ сделать эту последнюю часть.)

2 голосов
/ 21 марта 2011

Если вы уже знаете максимальный поток, то минимальный разрез равен (S, T), где S - множество вершин, достижимых из источника в остаточной сети, T - дополнительный набор.Края, соединяющие вершину из S и вершину из T, принадлежат разрезу.

1 голос
/ 01 августа 2012

Вот несколько указателей, которые помогут уточнить, как это сделать для кого-либо в будущем.

  1. Чтобы найти S-вершины, выполните поиск BFS (или DFS) только из исходной вершины.следующие ребра, в которых сохраняется некоторая емкость для потока.(Другими словами, ненасыщенные ребра).Эти по определению не могут быть в mincut.

  2. Чтобы найти T вершин, выполните поиск BFS (или DFS) из вершины sink , соединяясь только с вершинами.которые еще не были добавлены в набор S.Они могут иметь остаточный поток или могут быть полностью насыщенными, это не имеет значения.Поскольку вы выполняете BFS из приемника, вам нужно убедиться, что вы следуете в противоположном направлении, на которое указывает ребро, если график направлен.ПРИМЕЧАНИЕ. Важно включать в свой набор T только вершины, к которым можно добраться из раковины , в противном случае вы в конечном итоге включите в свой ребро минимальный разрез, которые не принадлежат ему.(Это то, что бросало меня в течение долгого времени.)

  3. После того, как у вас есть эти два набора вершин, вы можете выполнять итерацию по всем ребрам графа.Любой, у кого есть исходный узел в S и целевой узел в T, является частью вашего минимального разреза.Однако важно отметить, что это всего лишь один из множества возможных минимальных сокращений.Намного больше времени занимает поиск всех возможных минимальных сокращений ST на графике.

Надеюсь, это поможет любым будущим интернет-людям, пытающимся это выяснить!Удачи!

...