２部グラフの最大マッチングとフローチャート

質問

JAVAで２部グラフの最大マッチングを求めるプログラムを作るのですが、本やネットを使って調べているのですが、まったく理解ができません。
どなたか教えていただけないでしょうか？

回答No.1

seta_takahiro

アルゴリズムが分からないのかJavaでのコーディングが分からないのかが分かりませんが、
もし、アルゴリズムが分からないということなら、
いろいろアルゴリズムはあると思うのですが、
自分は最大流を学んだ時に知ったアルゴリズムが分かり易かったです

(有向グラフの)Depth First Search(DFS、深さ優先探索)のプログラムが書ければ、プログラム出来ると思います

1.左側の頂点群のさらに左に開始点Sを用意し、左の頂点全てと辺で結ぶ
2.右側の頂点群のさらに右に終了点Tを用意し、右の頂点全てと辺で結ぶ
3.全ての辺を左から右へ向きづける
4.次をSからTへのパスが存在する限り繰り返す
4-1.DFSなどの探索アルゴリズムを用い、SからTへのパスを見つける
4-2.パスで使われた辺の向きを逆向きにする
(すでに逆向きになっている辺を使ったら、元の向きに戻す)
5.左の頂点群と右の頂点群を結ぶ辺のうち左向きになっている辺が
マッチングとして選択された辺なので、それを結果とする。

# 上のは重みなしですが、
# 2部グラフの最大マッチングっていうのは、
# 点に重みがついていて、重みありで最大を求める奴でしたっけ？

お礼

ありがとうございました