C# と VB.NET の質問掲示板

わんくま同盟

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト


(過去ログ 39 を表示中)
■20188 / )  Re[5]: 再帰によるスタックオーバーフロー?
□投稿者/ れい (604回)-(2008/06/07(Sat) 11:46:38)
No20183 (siokoshou さん) に返信
> コードを書いてみました。細かいところまで再現できないので、理解して改造してください。LINQ使ってます。

のコードだと計算量的にもったいないように思えます。

任意のグラフからサイクルを抽出したい場合、
「端点」を削除していくのが一般的方法かと。
RDBとは少し相性が悪いですが…。

データベースを全コピーして、「端」であるノードを削除していき、
一個も削除できなくなったときに、ノードが残っていればそれが最大のサイクルです。

全コピーを避けたいなら、
CycleCheckとか言う名称でBooleanのカラムを一つ追加します。
最初に全てのノードについてCycleCheck=Trueとします。
親、もしくは子のCycleCheckがFalseになっているノードを、CycleCheck=Falseと変更していき、
一つも変更できなくなったときに「CycleCheck=True」なノードがサイクルになります。

この方法だとサイクルのサイズやグラフの構造によって速度が全く変わってしまうという欠点がありますが、
コードが簡単です。

もっと速い方法もありますが、
前処理などが多くてちょっとややこしいです。
返信 編集キー/


管理者用

- Child Tree -