Edmonds–Karpアルゴリズムのwikiページで見つけた擬似コードを使用してEdmonds–Karpアルゴリズムを実装しました：http：//en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm
それはうまく機能しますが、アルゴリズムの出力は最大フロー値（最小カット値）です。このカットに含まれるエッジのリストを作成する必要があります
アルゴリズムを変更しようとしましたが、成功しませんでした。
ありがとうございました
4976 次
3 に答える
4
すでにフローがある場合は、残差グラフを計算します。次に、ソースから深さ優先探索（または幅優先探索、重要ではないと思います）を実行して、カットの半分（S）の頂点を計算します。残りの頂点は、カットの残りの半分Tにあります。
これにより、カット（S、T）が得られます。特にSとTの間のエッジが必要な場合は、すべてのエッジを反復処理して、SとTを接続するエッジを選択できます（ただし、この最後の部分を実行するためのよりエレガントな方法がある場合があります）。
于 2011-03-21T17:04:31.420 に答える
2
最大フローがすでにわかっている場合、最小カットは（S、T）です。ここで、Sは残差ネットワークのソースから到達可能な頂点のセットであり、Tは相補的なセットです。Sの頂点とTの頂点を結ぶエッジはカットに属します。
于 2011-03-21T16:48:00.107 に答える
2
これは、将来誰かのためにこれを行う方法を明確にするのに役立ついくつかの指針です。
S頂点を見つけるには、ソース頂点からBFS（またはDFS）検索を実行し、フローの容量が残っているエッジのみを追跡します。（言い換えると、飽和していないエッジ）。これらのものは、定義上、最小カットに含めることはできません。
T頂点を見つけるには、シンク頂点からBFS（またはDFS）検索を実行し、Sセットにまだ追加されていない頂点にのみ接続します。これらには残留流がある場合もあれば、完全に飽和している場合もありますが、問題ではありません。シンクからBFSを実行しているため、グラフが方向付けられている場合は、エッジが指している方向とは反対の方向に沿っていることを確認する必要があります。注：シンクから到達できる頂点のみをTセットに含めることが重要です。そうしないと、そこに属していないエッジが最小カットに含まれることになります。（これは私を長い間投げたものです。）
これらの2セットの頂点を取得したら、グラフのすべてのエッジを反復処理できます。Sにソースノードがあり、Tにターゲットノードがある人は誰でも、最小カットの一部です。ただし、これは考えられる多くの最小カットの1つにすぎないことに注意することが重要です。グラフで可能なすべてのST最小カットを見つけるのははるかに時間がかかります。
これがこれを理解しようとしている将来のインターネットの人々に役立つことを願っています！幸運を！
于 2012-07-31T23:01:32.390 に答える