データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3

473 名前：デフォルトの名無しさん [2017/07/01(土) 20:40:17.40 ID:OLSj8alI.net] 浅野孝夫著『グラフ・ネットワークアルゴリズムの基礎』（近代科学社） ホップクロフト - カープのアルゴリズムのところを読んでいます。 プログラムに、非常に非効率な部分を発見しました。 深さ優先探索で最短パスを探す部分があるのですが、一つの最短パスを 発見した後も、うろうろと探索を続けています。 return 文で呼び出し元へと 遡って戻るべき箇所です。 具体的にいうと、p.95の void bipartite_dfs(int) 関数内の bipartite_dfs(w1); は、 bipartite_dfs(w1); if(pathfound) return; とすべきです。

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef