A 回答 (1件)
- 最新から表示
- 回答順に表示
No.1
- 回答日時:
アルゴリズムが分からないのかJavaでのコーディングが分からないのかが分かりませんが、
もし、アルゴリズムが分からないということなら、
いろいろアルゴリズムはあると思うのですが、
自分は最大流を学んだ時に知ったアルゴリズムが分かり易かったです
(有向グラフの)Depth First Search(DFS、深さ優先探索)のプログラムが書ければ、プログラム出来ると思います
1.左側の頂点群のさらに左に開始点Sを用意し、左の頂点全てと辺で結ぶ
2.右側の頂点群のさらに右に終了点Tを用意し、右の頂点全てと辺で結ぶ
3.全ての辺を左から右へ向きづける
4.次をSからTへのパスが存在する限り繰り返す
4-1.DFSなどの探索アルゴリズムを用い、SからTへのパスを見つける
4-2.パスで使われた辺の向きを逆向きにする
(すでに逆向きになっている辺を使ったら、元の向きに戻す)
5.左の頂点群と右の頂点群を結ぶ辺のうち左向きになっている辺が
マッチングとして選択された辺なので、それを結果とする。
# 上のは重みなしですが、
# 2部グラフの最大マッチングっていうのは、
# 点に重みがついていて、重みありで最大を求める奴でしたっけ?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 グラフ理論の数学の問題です。このタイプの問題は初めて見たので、どうやって解けばいいかわからないです。 1 2023/05/27 19:09
- Excel(エクセル) エクセルの大きなシートでグラフを見つける 4 2022/07/28 10:07
- 数学 グラフ理論の用語について 1 2022/09/16 19:50
- 数学 数1 二次関数 関数 y=x^2-2x-1について、定義域が-1<x<2のとき、最大値最小値を求めよ 5 2023/06/06 12:00
- 数学 数A 整数の性質 x.yを整数とする。 2x-3y=7-①をみたす(x,y)に対して、x^2-y^2 2 2023/06/01 15:39
- 物理学 測定データの読み方について教えて下さい 6 2023/07/09 16:43
- 数学 「f(x)とg(x)のグラフで囲まれた面積を求めよ」 という積分の面積を求める典型問題がありますが、 7 2023/06/09 01:16
- 物理学 無限に長い導体円筒の問題です。 (1)この導体円筒の単位あたりの静電容量を求めよ。 (2)内外の導体 1 2023/05/30 23:49
- 数学 微分の問題です。 3 2022/07/30 16:43
- 数学 三角関数の和 4 2023/06/17 18:33
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
Stuck
-
正しい五十音順について
-
Dijkstraて
-
m個の数字をn個のグループに分...
-
アルゴリズムの将来性について
-
[ EXCEL VBA ] 図形を読み込む...
-
ASPでのオークション
-
ルービックキューブの解法プロ...
-
リーグ戦日程表作成アルゴリズ...
-
迷路プログラム
-
確率論的な麻雀の勝ち方を教え...
-
VB2010にて分数表示(約...
-
【VisualBasic】ユークリッドの...
-
初心者がディープラーニングの...
-
5人のテストの点数を入力すると...
-
ガウス・ジョルダン法のプログ...
-
複数の点を最短距離で全て繋ぐ...
-
アルゴリズムとプロトコールの違い
-
A*アルゴリズム
-
最大公約数を求めたい!
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正しい五十音順について
-
Dijkstraて
-
Stuck
-
[ EXCEL VBA ] 図形を読み込む...
-
BCDについて
-
アルゴリズムとプロトコールの違い
-
期間重複チェックがわかりません
-
グループを均等に分けるには?...
-
三次元形状曲面の導出法
-
あいまい検索(文字列一致率)
-
Visual studio2019 C#で生まれ...
-
gooという検索エンジンの後にGo...
-
フリーセルの難易度について
-
CRC-CCITT16の算出法
-
経路探索について
-
C♯で電卓を作成しています。演...
-
理系の高校生です。大学で情報...
-
OpenCVのライセンスについて
-
偏りのある乱数のアルゴリズム
-
詰め将棋をとくのは、アルゴリ...
おすすめ情報