Алгоритм Форда-Фалкерсона для поиска максимального паросочетания

Идея алгоритма

Пусть дан двудольный граф [math]G(V, E)[/math] и требуется найти максимальное паросочетание в нём. Обозначим доли исходного графа как [math]L[/math] и [math]R[/math]. Построим граф [math]G'(V', E')[/math] следующим образом:

[math]V' = V \cup \{s, t\}[/math] (т.е. добавим две новые вершины [math]s[/math] и [math]t[/math])

[math]E' = \{(s,u): u \in L\} \cup \{(u, v): u \in L, v \in R\} \cup \{(v, t): v \in R\} [/math] (проведем ребра из [math]s[/math] в каждую вершину [math]L[/math], и из каждой вершины [math]R[/math] в [math]t[/math]).

Изначально максимальное паросочетание пусто.

1. Будем искать в графе [math]G'[/math] путь из [math]s[/math] в [math]t[/math] поиском в глубину.
2. Если путь найден, инвертируем все рёбра на пути.
3. Если путь не был найден, значит текущее паросочетание является максимальным, и алгоритм завершает работу. Иначе переходим к пункту 1.

В любой момент времени текущим паросочетанием будет множество рёбер, направленных из [math]R[/math] в [math]L[/math].

Псевдокод

 bool  dfs(x)
   if vis[x]
     return false
   vis[x] = true
   for [math]xy \in E[/math]
     if py[y] = -1
       py[y] = x
       px[x] = y
       return true
     else if dfs(py[y])
       py[y] = x
       px[x] = y
       return true
   return false

 px[] = -1
 py[] = -1
 while (changed)
   changed = false
   vis[] = false
   for [math]x \in L[/math]
     if (px[x] == -1) 
         if dfs(x)
             changed = true