1

Ford Fulkerson アルゴリズムを Java で実装しようとしています。これまでのところ、ノードとエッジを含むグラフがあります。ノードには、ID 文字列とエッジの adjacencyList が含まれています。エッジには、容量とそれが導くノードが含まれます。

ウィキペディアのページにある疑似コードとその実装方法を理解しようとしています (私は Java を使用しています)。これは私がこれまでに理解していることです：

  1. 最初に、グラフ内のすべてのエッジの流れをゼロに設定します。

  2. 2 番目のステップは、エッジが残余容量を持つネットワークである残差グラフを作成することです: 容量 - フロー (「通常のグラフ」の対応するエッジの)。次に、この残差グラフを使用してソースからシンクへのパスを見つけ、このパスに沿って最小容量を見つけます。(これは本当にトリッキーになるところです。残差グラフ用にまったく新しいグラフを作成する必要がありますか、それとも元のグラフで何らかの方法で表現する必要がありますか?最善の方法は何ですか?)

ステップ 2 はパスが見つからなくなるまで繰り返されますが、パスが見つかるたびにステップ 3 と 4 を実行します。

  1. パスに沿ったエッジごとに、ステップ 2 で見つけた最小値を追加します。

  2. パスの反対方向のエッジごとに、ステップ 2 で見つけた最小値を引きます。

ステップ 3 と 4 は私を困惑させます。なぜなら、一方の方向に加算することと、反対方向に減算することは同じことだと思うからです。これらの加算と減算は、残差グラフではなく、グラフで行われますか?

助けていただければ幸いです。数時間この問題に頭を悩ませようとしていますが、理解できないようです。

4

2 に答える 2

3

おそらく、密なグラフでこれを最初に実装する必要があります。そうすれば、異なる頂点のすべてのペアの間に各方向にエッジがあると想定できます。エッジ上の関数を |V| として表すことができます。x |V| 行列。特に、容量とフローの宣言は非常に単純です。

int[][] cap = new int[numverts][numverts];
int[][] flow = new int[numverts][numverts];

便利なトリックの 1 つは、kエッジに沿ったユニットの流れをfromの流れとfrom からのvw流れとして表すことです。このように、オーグメント パスの各エッジがより多くのフローを前方に押し出しているか、またはフローを後方に押し下げていないかを心配する必要はありません。これを行うと、簡単に残余容量を計算できます。avw-awvvwcap[v][w] - flow[v][w]

vこの表現を使用すると、拡張パスを見つけることは、 からまでのエッジがある密なグラフの幅優先探索にwなりますcap[v][w] > flow[v][w]。これはかなり簡単に実装されます。

Java を使用しているため、オブジェクトごとのオーバーヘッドに注意する必要があります。あなたが説明した Edge 構造には、2 つの int (またはポインター) と 2 つの double だけでなく、GC 情報、クラス ポインター、モニターなども含まれています。これは数十バイトの余分なバイトであり、オブジェクトのサイズを簡単に 2 倍または 3 倍にすることができます。

コードをスパース グラフで動作させる場合、静的なスパース グラフをより適切に表現するには、次のようにします。

int[] from = new int[numverts+1];
int[] to = new int[numedges];

「from」頂点でエッジを並べ替えます。配列のith エントリは、from「from」頂点がith 頂点以降である最初のエッジのインデックスです。最後に 1 つの余分なエントリがあり、それをnumedges;に設定する必要があります。特定の頂点を離れるすべてのエッジをループしたい場合に便利です。

フローを行っているため、後方エッジも保存する必要があるため、

int[] rev = new int[numedges];

各エッジの逆のエッジ インデックスを格納します。これで、次のようにエッジで任意の関数、たとえばcapおよびを表すことができます。flow

int[] cap = new int[numedges];
int[] flow = new int[numedges];

したがって、これらの属性を構造体に格納するかどうかは、構造体がなくなったEdgeため、議論の余地があります。Edge

于 2013-05-20T22:14:48.320 に答える