Изменения

Перейти к: навигация, поиск

Алгоритм "поднять-в-начало"

9 байт добавлено, 23:01, 4 января 2016
Алгоритм
Инициализируем предпоток и высоты, с помощью операции [[Метод проталкивания предпотока#Схема алгоритма|<tex>\mathtt{initializePreflow}</tex>]]. Список <tex>L</tex> {{---}} список для хранения всех вершин графа, кроме стока и истока. Проинициализируем указатель <tex>current</tex> каждой вершины <tex>u</tex>, чтобы он указывал на первую вершину в списке <tex>u</tex>.
Пройдем по списку <tex>L</tex>, разгружая вершины, начиная с первой. И если операция <tex>\mathtt{discharge}</tex> изменила высоту вершины, то перемещаем ее в начало списка <tex>L</tex>. Передвинем указатель на следующую вершину списке <tex>L</tex>. Если после разгрузки была изменена высота, то берем следующую вершину в новом списке <tex>L</tex>.
'''function''' <tex>\mathtt{relabelToFront}(s, t): </tex>'''
Анонимный участник

Навигация