アルゴリズムクイックリファレンス 第2版

252

■

8

章 ネットワークフローアルゴリズム

8.2.1

 入出力

フローネットワークは、ソース節点

s

とシンク節点

t

を持つグラフ

G

＝

(V, E)

に

よって定義される。

E

の有向辺

e

＝

(u, v)

は、定義された整数容量

c(u, v)

と実フロー

f(u, v)

を持つ。

フォード

-

ファルカーソン法

は、

E

の各辺

(u, v)

に対して、辺

(u, v)

を流れるユニッ

ト数を表す整数フロー

f(u, v)

を計算する。停止時の副産物として、

フォード

-

ファ

ルカーソン法

は、最小カットも計算する。すなわち、これ以上の

s

から

t

への流れを

妨げる、ボトルネックを形成する辺の集合である。

8.2.2

 解

ここで述べる

フォード

-

ファルカーソン法

は、リンク付きリストを用いて辺を貯え

る。各節点

u

は、

u

から出る前方辺と

u

に来る後方辺の

2

つのリストを別々に保持す

る。これにより、各辺が、

2

つのリストに現れる。本書のコードリポジトリには、密

なフローネットワークグラフに適した

2

次元行列を用いて辺を貯える実装がある

＊

1

。

フォード

-

ファルカーソン法

は、次のようなクラスに依存する。

FlowNetwork

ネットワークフロー問題を表す。この抽象クラスには、隣接リストに

基づくものと配列を用いるものとの

2

つのサブクラスがある。メソッド

getEdgeStructure()

は、辺を表すデータ構造を返す。

VertexStructure

節点に入る辺と、節点から出る辺とに対応する

2

つのリンク付きリスト

（前方および後方）を保持する。

EdgeInfo

ネットワークフローにおける辺の情報を記録する。 ...