graph-algorithm - 2部グラフの最大マッチング

Question

グラフは初めてです。2部グラフに2つのセットがあります。考えられるすべての組み合わせの一意の一致を見つける必要があります。だから私はホップクロフト・カープを使って最大の一致を見つけると思った。初心者なので、結果の一致するグラフが得られると思いましたが、それが示すのは42だけです。ああ、それは本当に役に立ちます。マッチングがいくつあるかを知る必要はありません。独自のマッチング自体を知る必要があります。

私は何かが足りないのですか？結果のマッチングを取得するにはどうすればよいですか？

Answer 1

Hopcroft-Karp 一致関数によって生成されたデータ構造はチェックせず、再実行値のみをチェックしました。戻り値は一致数です。ただし、python コードには self.pair 辞書もありました。ペア辞書には、「両側」からの一致が含まれており、私の質問に答えています。