#algorithm #data-structures #max-flow #ford-fulkerson
Вопрос:
Мне было интересно, как бы прямые и обратные границы остаточных мощностей из алгоритма Форда-Фулкерсона были переведены в матрицу? Будет ли верхняя треугольная матрица иметь передние края, а нижняя часть-задние края?
Ответ №1:
Существует несколько различных способов кодирования графика в виде матрицы, поэтому я не думаю, что мы могли бы говорить конкретно о «способе» этого.
Наиболее распространенный способ кодирования графа с весами / емкостями на его ребрах в виде матрицы-это матрица смежности. Чтобы сформировать его, пронумеруйте узлы на графике 1, 2, 3, …, n. Затем запись в строке i, столбце j соответствует емкости на границе, идущей от узла i к узлу j. Если емкость положительна, то эта запись будет положительной. Если это остаточное ребро, значение будет отрицательным. И если нет ребра от первого узла до второго, или если ребро насыщено, значение в матрице будет равно нулю.