C++でフローネットワークの最小s-tカットを求める方法

最小s-tカットとは

フローネットワークが与えられたとき、s-tカットとは、始点(ソース)ノード s と終点(シンク)ノード t が必ず異なる部分集合に振り分けられるような頂点の分割を指します。カットには、ソース側の集合からシンク側の集合へ向かう辺が含まれ、その容量はカット集合に含まれる各辺の容量の総和で表されます。

この記事では、与えられたネットワークの中から容量が最小となるs-tカット(最小カット)を見つけ、それを構成するすべての辺を出力する方法を解説します。

たとえば、次のようなネットワークが入力されたとします。

このときの出力は [(1,3), (4,3), (4,5)] となります。

アルゴリズムの考え方

最大流最小カット定理により、「ネットワークの最大フロー値」と「最小カットの容量」は常に一致することが知られています。そこで本手法では、まずBFSを用いたフォード・ファルカーソン法(エドモンズ・カープ法)で最大フローを求め、フロー計算終了後の残余グラフ上で、ソースから到達できる頂点集合をDFSによって特定します。最後に、「到達可能な頂点 i から到達不可能な頂点 j へ伸びる、元のグラフ上の辺」をすべて列挙すれば、それがまさに最小カットとなります。

手順の詳細

• ノード数を表す定数 NODES を 6 とします。

• bfs() 関数を定義します。引数はグラフ、始点 src、終点 sink、親頂点を記録する配列 par です。

  • サイズ NODES の訪問済みフラグ配列 vis を用意し、0 で初期化します。

  • キュー que を作成し、src を追加します。

  • vis[src] := true、par[src] := -1 と設定します。

  • que が空になるまで次を繰り返します。

    • que の先頭要素を u1 として取り出します。

    • v1 を 0 から NODES - 1 まで動かしながら、vis[v1] が false かつ graph[u1][v1] > 0 である場合、v1 を que に追加し、par[v1] := u1、vis[v1] := true とします。

  • vis[sink] が true であれば true を返します(sinkへ至るパスが存在することを意味します)。

• dfs() 関数を定義します。引数はグラフ、src、配列 vis です。

  • vis[src] := true とします。

  • i を 0 から NODES - 1 まで動かし、graph[src][i] が非ゼロかつ vis[i] が false であれば、dfs(graph, i, vis) を再帰的に呼び出します。

• メイン処理では以下を実行します。

  • 配列 temp_graph を用意し、元のグラフをコピーします。

  • サイズ NODES の配列 par を宣言します。

  • bfs(temp_graph, src, sink, par) が true を返す間、次を繰り返します。

    • path_flow := 無限大 と初期化します。

    • v を sink から src に向かって par をたどりながら、u := par[v] として path_flow := min(path_flow, temp_graph[u][v]) を更新します(経路上の最小残容量を求めます)。

    • 再び v を sink から src へたどりながら、temp_graph[u][v] -= path_flow、temp_graph[v][u] += path_flow として残余グラフを更新します。

  • サイズ NODES の配列 vis を false で初期化します。

  • dfs(temp_graph, src, vis) を実行し、ソースから到達可能な頂点をマークします。

  • i と j の二重ループにおいて、vis[i] が true、vis[j] が false、かつ元の graph[i][j] が非ゼロである場合、辺 (i, j) を表示します。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
#define NODES 6
int bfs(int graph[NODES][NODES], int src, int sink, int par[]) {
   bool vis[NODES];
   memset(vis, 0, sizeof(vis));
   queue <int> que;
   que.push(src);
   vis[src] = true;
   par[src] = -1;
   while (!que.empty()) {
      int u1 = que.front();
      que.pop();
      for (int v1=0; v1<NODES; v1++){
         if (vis[v1]==false && graph[u1][v1] > 0) {
            que.push(v1);
            par[v1] = u1;
            vis[v1] = true;
         }
      }
   }
   return (vis[sink] == true);
}
void dfs(int graph[NODES][NODES], int src, bool vis[]) {
   vis[src] = true;
   for (int i = 0; i < NODES; i++)
   if (graph[src][i] && !vis[i])
   dfs(graph, i, vis);
}
void minCut(int graph[NODES][NODES], int src, int sink) {
   int u, v;
   int temp_graph[NODES][NODES];
   for (u = 0; u < NODES; u++)
      for (v = 0; v < NODES; v++)
         temp_graph[u][v] = graph[u][v];
   int par[NODES];
   while (bfs(temp_graph, src, sink, par)){
      int path_flow = INT_MAX;
      for (v=sink; v!=src; v=par[v]) {
         u = par[v];
         path_flow = min(path_flow, temp_graph[u][v]);
      }
      for (v=sink; v != src; v=par[v]) {
         u = par[v];
         temp_graph[u][v] -= path_flow;
         temp_graph[v][u] += path_flow;
      }
   }
   bool vis[NODES];
   memset(vis, false, sizeof(vis));
   dfs(temp_graph, src, vis);
   for (int i = 0; i < NODES; i++)
      for (int j = 0; j < NODES; j++)
         if (vis[i] && !vis[j] && graph[i][j])
            cout << "("<< i << ", " << j << ")" << endl;
   return;
}
int main() {
   int graph1[NODES][NODES] = {
      {0, 17, 14, 0, 0, 0},
      {0, 0, 11, 13, 0, 0},
      {0, 5, 0, 0, 15, 0},
      {0, 0, 9, 0, 0, 21},
      {0, 0, 0, 8, 0, 5},
      {0, 0, 0, 0, 0, 0}
   };
   minCut(graph1, 0, 5);
}

入力

{{0, 17, 14, 0, 0, 0},
{0, 0, 11, 13, 0, 0},
{0, 5, 0, 0, 15, 0},
{0, 0, 9, 0, 0, 21},
{0, 0, 0, 8, 0, 5},
{0, 0, 0, 0, 0, 0}};

出力

(1, 3)
(4, 3)
(4, 5)

このように、最大フロー計算後に残余グラフ上でソースから到達可能な領域と到達不可能な領域を分離することで、最小カットを構成する辺を効率的に特定できます。