Двусторонний граф с источником и раковиной приведен ниже. Емкость каждого ребра составляет 1 единица: Source : GeeksforGeeksОшибка при приближении к максимальному совпадению двух сторон
Я пытаюсь найти максимальный поток от источника до потолка. Один из подходов будет использовать алгоритм Форда-Фулкерсона для задачи максимального потока, который применим ко всем графикам. Я нашел простой подход, чтобы найти максимальный поток (слишком просто, чтобы быть правильным!), И я не могу найти ошибки в подходе.
подход:
c1 = Подсчитайте число вершин, имеющие ненулевое число ребер, исходящие из него, в списке вершин, имеющие исходящие ребра.
c2 = Рассчитать количество вершин, имеющих не равное нулю число ребер, сходящихся в нем, в списке вершин, имеющих входящие ребра.
Максимальный поток будет минимальным из обоих этих чисел, то есть, мин (с1, с2). [Так как любой путь нуждается в одну вершину из списка исходящих вершин, и другой из списка входящих вершин.]
Любая помощь будет оценена по достоинству.
Большое спасибо. Я искал именно это. – gautamk
Это был мой первый вопрос в Stack Overflow. Не знал об этом. Благодарю. – gautamk