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

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

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

Re[5]: 再帰によるスタックオーバーフロー?


(過去ログ 39 を表示中)

[トピック内 12 記事 (1 - 12 表示)]  << 0 >>

■20074 / inTopicNo.1)  再帰によるスタックオーバーフロー?
  
□投稿者/ ヤナックス (1回)-(2008/06/05(Thu) 11:11:18)

分類:[C#] 

以下のようなテーブルがあります。(実際は数万件程度)

<親コード> <子コード> <年> <月>
 AAA    BBB    2008  6
 BBB    CCC    2008  6
 CCC    AAA    2008  6
 AAA    DDD    2008  6
 EEE    AAA    2008  6
 EEE    CCC    2008  6
 EEE    DDD    2008  6

上記表から上の3行のように親コードと子コードの関係がループするような
行を抜き出したいのでとりあえず処理を作ったのですが、
再帰処理の部分なのかスタックオーバーフローで落ちてしまいます。

落ちないようにする方法としてはどういう方法があるのでしょうか?
ご存知でしたらおおまかにでも構いませんので教えていただけないでしょうか?


以下ソースです。


    protected DataSet dtSet = new DataSet("XXX");
    protected string SerchTarget;

    private void button1_Click(object sender, EventArgs e)
    {


      OracleConnection OraConn = new OracleConnection();
      OracleDataAdapter OraDA;
      
      DataView dtView = new DataView();
      dtSet.Clear();
      dataGridView3.Rows.Clear();

      //〜DB接続やらなんやかんや〜

      for (int i = 0; i <= dtSet.Tables[0].Rows.Count - 1; i++)
      {

        SerchTarget = dtSet.Tables[0].Rows[i].ItemArray[1].ToString();

        if (checkloop(SerchTarget, dtSet.Tables[0].Rows[i].ItemArray[2].ToString(), int.Parse(dtSet.Tables[0].Rows[i].ItemArray[3].ToString())) == true)
        {
          //抜き出した行をグリッドに入れる
          wktable.ImportRow(dtSet.Tables[0].Rows[i]);
        }

      }
    }


    //再帰処理部分。
    private bool checkloop(string grp, string ffiscalyr, int fperiod)
    {

      int Row;
      string wkKOgrp;

      //パラメタで渡されたコードが親コードとしてもつ行の行数を取得。ない場合は-1
      Row = Find(dtSet, grp, ffiscalyr, fperiod, 0,int.Parse(dtSet.Tables[0].Rows.Count.ToString())-1);

      while (Row > -1)
      {
        wkKOgrp = dtSet.Tables[0].Rows[Row].ItemArray[1].ToString();

        //一番おおもとの比較値と比較
        if (SerchTarget == wkKOgrp)
        {
          return true;
        }
        else
        {
          //自身を再度呼び出す
          if(checkloop(wkKOgrp,ffiscalyr,fperiod) == false)
          {
            //現在の行数以降で、パラメタで渡されたコードが親コードとしてもつ行の行数を取得。ない場合は-1
            Row = Find(dtSet, grp, ffiscalyr, fperiod, Row + 1, dtSet.Tables[0].Rows.Count - 1);
          }
          else
          {
            return true;
          }
        }
      }

      return false;
    }

    //子コードが一致したデータの行数を返す関数
    private int Find(DataSet ds, string GRP, string ffiscalyr, int fperiod, int startrow, int endrow)
    {
      int i;

      for (i = startrow ; i <= endrow ; i++)
      {
        if ((ds.Tables[0].Rows[i].ItemArray[0].ToString() == GRP) && (ds.Tables[0].Rows[i].ItemArray[2].ToString() == ffiscalyr) && (int.Parse( ds.Tables[0].Rows[i].ItemArray[3].ToString()) == fperiod))
        {
          return i;
        }
      }

      return -1;
    }
引用返信 編集キー/
■20078 / inTopicNo.2)  Re[1]: 再帰によるスタックオーバーフロー?
□投稿者/ も (22回)-(2008/06/05(Thu) 12:01:30)
No20074 (ヤナックス さん) に返信
なんやらボトム関数っぽい感じがします.
boolean hoge(object piyo){
if(hoge(piyo)==false) return true;
return false;
}
みたいな.

とりあえずFindとcheckloop関数がちゃんと設計どおりに動いているか確認するのが先ですね.
設計どおりに動いていてスタックオーバーフローが発生するなら,スレッドのスタック領域を増やすとか,
再帰関数を下みたいに非再帰関数に展開するとか.
boolean hoge(object piyo){
for(;;);
}
引用返信 編集キー/
■20079 / inTopicNo.3)  Re[1]: 再帰によるスタックオーバーフロー?
□投稿者/ 魔界の仮面弁士 (759回)-(2008/06/05(Thu) 12:02:03)
No20074 (ヤナックス さん) に返信
> 以下のようなテーブルがあります。(実際は数万件程度)

当方だと、(ディレクトリのような)親子関係を持つ階層構造にする場合は、
《自分を表すID》と《親を表すID》を持たせ、親IDが NULL あるいは 親ID = 自己ID の物を
ルートとみなすテーブル構造にする事が多いです。

そうすると、Oracle 側で
 SELECT 〜 FROM 〜 START WITH 〜 CONNECT BY NOCYCLE ID = PARENT_ID
の構文を使いやすいので。


> <親コード> <子コード> <年> <月>
自己ID が無く、親ID と子ID がある状態…という事は、これは
リレーション情報だけを管理するテーブルなのでしょうか。

ループを許容しないというルールは分かりましたが、それ以外の階層条件についても
教えてください。たとえば、複数の親を持つ事は許容されますか? 具体的には、
 AA    …親=なし/子=BB,EE
 ├BB   …親=AA/子=CC,EE
 │├CC  …親=BB/子=DD
 ││└DD …親=CC/子=なし
 └┴EE  …親=AA,BB/子=なし
のようなリレーション構造を許容するかどうかです。

# その他の追加条件等があれば、予め提示しておいて頂けると話がしやすいです。

引用返信 編集キー/
■20080 / inTopicNo.4)  Re[1]: 再帰によるスタックオーバーフロー?
□投稿者/ 渋木宏明(ひどり) (773回)-(2008/06/05(Thu) 12:03:35)
渋木宏明(ひどり) さんの Web サイト
再帰が深すぎてクラッシュしているなら、再帰の使用をやめるしかないです。

再帰は、スタックの代わりになるバッファとループに還元可能です。

ただし、元のデータ量が数百万件ということは、ネストの深さの最大値が想定できないようなら、オンメモリでの探索はやはり厳しいように思います。

引用返信 編集キー/
■20110 / inTopicNo.5)  Re[1]: 再帰によるスタックオーバーフロー?
□投稿者/ Jitta (482回)-(2008/06/05(Thu) 21:54:10)
Jitta さんの Web サイト
No20074 (ヤナックス さん) に返信
まず、コメントを何とかしましょう。
呼び出し側は「パラメタで渡されたコードが親コードとしてもつ行の行数を取得。」とコメントしてあるのに、呼び出される側は「子コードが一致したデータの行数を返す関数」と、コメントしてあります。

呼び出し側では、パラメータは「親コード」であるとしてあります。
呼び出される側には、パラメータは「子コード」であるとしてあります。
どちらが本当でしょう?


でもって、どのように処理をしたいのでしょう?
どのような結果が得たいのでしょう?


一応、コードをすこーしだけ、読んでみました。
while (Row > -1) のループですけど。。。
> wkKOgrp = dtSet.Tables[0].Rows[Row].ItemArray[1].ToString();
これ、変じゃないですか?
ここで、Rows[Row] の Row は、Rows 配列の中の1レコードを指すための「行番号」を期待しています。
そして、それは、Find の戻り値から得ています。
で、この Find が返すのは、「子コードが一致したデータの行数」ですよね?
「行数」と、「行番号」は、一致しないですよね?

引用返信 編集キー/
■20172 / inTopicNo.6)  Re[2]: 再帰によるスタックオーバーフロー?
□投稿者/ Jitta (483回)-(2008/06/06(Fri) 23:50:36)
Jitta さんの Web サイト
No20110 (Jitta さん) に返信
> ■No20074 (ヤナックス さん) に返信
> まず、コメントを何とかしましょう。
 ん。。。やっぱり、まず、コメントの整理から始めましょう。
行数を返すって、行の数を返してないじゃないですか。行番号返してますね。

で、checkloop の最初の find 呼び出しで、必ず 0 番目から検索していますね。
とすると、どうなります?
引用返信 編集キー/
■20178 / inTopicNo.7)  Re[3]: 再帰によるスタックオーバーフロー?
□投稿者/ siokoshou (1回)-(2008/06/07(Sat) 07:03:04)
No20074 (ヤナックス さん) に返信

ヤナックスさんこんにちは、siokoshouです。
この問題は有向グラフの一筆書き問題ですね。やっかいな問題に取り組んでいますねぇ。
コードがどうこうという前に問題を整理してみます。

このテーブルの項目が表しているのはグラフの辺であり、親コードを始点、子コードを終点とした向きを持った辺。
親コード、子コードを頂点として絵を描いてみると、よくわかると思います。

そして、ループと呼んでいるのはグラフ理論でサイクルと呼ばれるもの。
そう考えたときに、この問題は任意の点を始点として、始点に戻ってくる一筆書きの道があるかどうかを判定する問題になります。

そのうち問題にチャレンジしてみたいけど、とりあえず今は問題を整理したところまで(スミマセン)。

引用返信 編集キー/
■20183 / inTopicNo.8)  Re[4]: 再帰によるスタックオーバーフロー?
□投稿者/ siokoshou (2回)-(2008/06/07(Sat) 09:55:22)
スタックオーバーフローが起きるのは、checkloopで経路の最初の始点としか比較していないためと思います。
「EEE AAA, AAA BBB, BBB CCC, CCC AAA」のルートをたどり、次に「AAA BBB」の辺があるので、このルート内でサイクルになっていますが、最初の始点以外を記録して比較していないため、サイクルを検出できず、無限ループとなります。

また、一つ目のサイクルしか見つけれないという別の問題もあります。
たとえば、「AAA BBB, BBB CCC, CCC AAA」は見つけれるが、もう一つ「AAA BBB, BBB HHH, HHH CCC, CCC AAA」があったときにこれを見つけれません。

さらに、単にルートが長い時、やはりスタックオーバーフローが起きるかもしれません。でも、面倒なので再起は取り除いていない
コードを書いてみました。細かいところまで再現できないので、理解して改造してください。LINQ使ってます。

using System;
using System.Collections.Generic;
using System.Linq;

namespace DetectCycle
{
    class Program
    {
        static void Main()
        {
            var table = new[] {
                        new Field( "AAA", "BBB", 2008, 6 ),
                        new Field( "BBB", "CCC", 2008, 6 ),
                        new Field( "CCC", "AAA", 2008, 6 ),
                        new Field( "AAA", "DDD", 2008, 6 ),
                        new Field( "EEE", "AAA", 2008, 6 ),
                        new Field( "EEE", "CCC", 2008, 6 ),
                        new Field( "EEE", "DDD", 2008, 6 ),
                        new Field( "BBB", "HHH", 2008, 6 ), // new
                        new Field( "HHH", "CCC", 2008, 6 ), // new
                        new Field( "III", "III", 2008, 6 ), // new ループ
                        new Field( "JJJ", "KKK", 2008, 6 ), // new 多重辺
                        new Field( "KKK", "JJJ", 2008, 6 ), // new 多重辺
            };

            FindCycle( table );
            Console.ReadKey();
        }

        public static void FindCycle( Field[] f )
        {
            // 全ての点を調べる
            for ( int i = 0; i < f.Length; i++ )
            {
                List<Pair> list = new List<Pair>();

                var pair = new Pair( i, f[ i ] );
                list.Add( pair );
                InnerFindCycle( f, list );
            }
        }

        // 経路探索ループ
        public static void InnerFindCycle( Field[] f, List<Pair> list )
        {
            Pair last = list.Last();

            foreach ( var item in Find( f, last.Field.ChildCode, last.Index ) )
            {
                // 辺の終点が最初の始点と一致する?
                if ( item.Field.ChildCode == list[ 0 ].Field.ParentCode )
                {
                    // サイクルを見つけた
                    int n = list.Count;
                    list.Add( item );
                    FoundCycle( list );
                    list.RemoveAt( n );
                    continue;
                }

                // 辺の終点がリスト中の最初以外の始点と一致した場合、この道はサイクルに接続しているサイクルではない道
                if ( list.Skip( 1 ).Where( p => p.Field.ParentCode == item.Field.ChildCode ).Any() )
                    continue;

                // どちらでもない場合、続きの道を調べる
                int m = list.Count;
                list.Add( item );
                InnerFindCycle( f, list ); // 再帰
                list.RemoveAt( m );
            }
        }

        // データベースから次の辺を探す処理
        public static IEnumerable<Pair> Find( Field[] f, string code, int startIndex )
        {
            return f.Skip( startIndex ).Select( ( e, index ) => new Pair( index, e ) )
                .Where( p => p.Field.ParentCode == code );
        }

        // サイクルを見つけたときの処理
        public static void FoundCycle( List<Pair> list )
        {
            foreach ( var item in list )
            {
                Console.WriteLine( item );
            }
            Console.WriteLine();
        }
    }

    // 一時保存用のデータ構造
    public struct Pair
    {
        public int Index;
        public Field Field;

        public Pair( int i, Field f )
        {
            this.Index = i;
            this.Field = f;
        }

        public override string ToString()
        {
            return string.Format( "{0,2} {1}", this.Index, this.Field );
        }
    }

    // データベースの1項目相当
    public class Field
    {
        public string ParentCode { set; get; }
        public string ChildCode { set; get; }
        public int Year { set; get; }
        public int Month { set; get; }

        public Field( string p, string c, int y, int m )
        {
            this.ParentCode = p;
            this.ChildCode = c;
            this.Year = y;
            this.Month = m;
        }

        public override string ToString()
        {
            return string.Format( "{0} {1}", this.ParentCode, this.ChildCode );
        }
    }
}






引用返信 編集キー/
■20186 / inTopicNo.9)  Re[5]: 再帰によるスタックオーバーフロー?
□投稿者/ siokoshou (3回)-(2008/06/07(Sat) 11:35:53)
siokoshouです。だめだねぇ、バグってますねぇw
直してみました。今度こそ、一筆書きアルゴリズムのはずです。

using System;
using System.Collections.Generic;
using System.Linq;

namespace DetectCycle
{
    class Program
    {
        static void Main()
        {
            var table = new[] {
                        new Field( "AAA", "BBB", 2008, 6 ),
                        new Field( "BBB", "CCC", 2008, 6 ),
                        new Field( "CCC", "AAA", 2008, 6 ),
                        new Field( "AAA", "DDD", 2008, 6 ),
                        new Field( "EEE", "AAA", 2008, 6 ),
                        new Field( "EEE", "CCC", 2008, 6 ),
                        new Field( "EEE", "DDD", 2008, 6 ),
                        new Field( "BBB", "HHH", 2008, 6 ), // new
                        new Field( "HHH", "CCC", 2008, 6 ), // new
                        new Field( "III", "III", 2008, 6 ), // new ループ
                        new Field( "JJJ", "KKK", 2008, 6 ), // new 多重辺
                        new Field( "KKK", "JJJ", 2008, 6 ), // new 多重辺
                        new Field( "BBB", "BBB", 2008, 6 ), // new ループ

                        new Field( "z", "x", 2008, 6 ), // new
                        new Field( "x", "y", 2008, 6 ), // new
                        new Field( "y", "z", 2008, 6 ), // new
            };

            var x = new Graph( table );
            x.FindCycle();
            Console.WriteLine();

            foreach ( int i in x.GetCycle() )
            {
                Console.WriteLine( i );
            }
            Console.ReadKey();
        }
    }

    public class Graph
    {
        private List<int> cycle = new List<int>();
        private Field[] f;

        public Graph( Field[] f )
        {
            this.f = f;
        }

        public void FindCycle()
        {
            // 全ての点を調べる
            for ( int i = 0; i < f.Length; i++ )
            {
                List<Pair> list = new List<Pair>();

                var pair = new Pair( i, this.f[ i ] );
                list.Add( pair );

                // ループ?
                if ( pair.Field.ParentCode == pair.Field.ChildCode )
                {
                    // サイクルを見つけた
                    FoundCycle( list );
                    continue;
                }

                InnerFindCycle( list );
            }
        }

        // 経路探索ループ
        private void InnerFindCycle( List<Pair> list )
        {
            Pair last = list.Last();

            foreach ( var item in Find( last.Field.ChildCode, list ) )
            {
                // ループ?
                if ( item.Field.ParentCode == item.Field.ChildCode )
                {
                    // 途中の経路でループを見つけた。この道は無視する。
                    continue;
                }

                // 辺の終点が最初の始点と一致する?
                if ( item.Field.ChildCode == list[ 0 ].Field.ParentCode )
                {
                    // サイクルを見つけた
                    list.Add( item );
                    FoundCycle( list );
                    list.RemoveAt( list.Count - 1 );
                    continue;
                }

                // 辺の終点がリスト中の最初以外の始点と一致した場合、この道はサイクルに接続しているサイクルではない道
                if ( list.Skip( 1 ).Where( p => p.Field.ParentCode == item.Field.ChildCode ).Any() )
                    continue;

                // どちらでもない場合、続きの道を調べる
                list.Add( item );
                InnerFindCycle( list ); // 再帰
                list.RemoveAt( list.Count - 1 );
            }
        }

        // データベースから次の辺を探す処理
        private IEnumerable<Pair> Find( string code, List<Pair> list )
        {
            return this.f.Select( ( e, index ) => new Pair( index, e ) )
                .Where( p => p.Field.ParentCode == code )
                .Where( p => !list.Any( l => l.Field.ParentCode == p.Field.ParentCode && l.Field.ChildCode == p.Field.ChildCode ) );
        }

        // サイクルを見つけたときの処理
        private void FoundCycle( List<Pair> list )
        {
            List<int> tmp = new List<int>();
            foreach ( var item in list )
            {
                int n = item.Index;
                if ( !this.cycle.Contains<int>( n ) )
                {
                    this.cycle.Add( n );
                }
                this.cycle.Sort();
            }

            foreach ( var item in list )
            {
                Console.WriteLine( item );
            }
            Console.WriteLine();
        }

        public int[] GetCycle()
        {
            return this.cycle.ToArray();
        }
    }

    // 一時保存用のデータ構造
    public struct Pair
    {
        public int Index;
        public Field Field;

        public Pair( int i, Field f )
        {
            this.Index = i;
            this.Field = f;
        }

        public override string ToString()
        {
            return string.Format( "{0,2} {1}", this.Index, this.Field );
        }
    }

    // データベースの1項目相当
    public class Field
    {
        public string ParentCode { set; get; }
        public string ChildCode { set; get; }
        public int Year { set; get; }
        public int Month { set; get; }

        public Field( string p, string c, int y, int m )
        {
            this.ParentCode = p;
            this.ChildCode = c;
            this.Year = y;
            this.Month = m;
        }

        public override string ToString()
        {
            return string.Format( "{0} {1}", this.ParentCode, this.ChildCode );
        }
    }
}

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

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

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

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

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

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

もっと速い方法もありますが、
前処理などが多くてちょっとややこしいです。
引用返信 編集キー/
■20229 / inTopicNo.11)  Re[6]: 再帰によるスタックオーバーフロー?
□投稿者/ siokoshou (4回)-(2008/06/07(Sat) 17:52:59)
No20188 (れい さん) に返信

なるほど!簡単ですね。コードにしてみました。

using System;
using System.Collections.Generic;

namespace DetectCycle
{
    class Program
    {
        static void Main()
        {
            var table = new[] {
                        new Field( "AAA", "BBB", 2008, 6 ),
                        new Field( "BBB", "CCC", 2008, 6 ),
                        new Field( "CCC", "AAA", 2008, 6 ),
                        new Field( "AAA", "DDD", 2008, 6 ),
                        new Field( "EEE", "AAA", 2008, 6 ),
                        new Field( "EEE", "CCC", 2008, 6 ),
                        new Field( "EEE", "DDD", 2008, 6 ),
                        new Field( "BBB", "HHH", 2008, 6 ), // new
                        new Field( "HHH", "CCC", 2008, 6 ), // new
                        new Field( "III", "III", 2008, 6 ), // new ループ
                        new Field( "JJJ", "KKK", 2008, 6 ), // new 多重辺
                        new Field( "KKK", "JJJ", 2008, 6 ), // new 多重辺
                        new Field( "BBB", "BBB", 2008, 6 ), // new ループ

                        new Field( "z", "x", 2008, 6 ), // new
                        new Field( "x", "y", 2008, 6 ), // new
                        new Field( "y", "z", 2008, 6 ), // new
            };

            var x = new Graph( table );
            x.FindCycle();

            foreach ( int i in x.GetCycle() )
            {
                Console.WriteLine( i );
            }
            Console.ReadKey();
        }
    }

    public class Graph
    {
        private Field[] f;

        public Graph( Field[] f )
        {
            this.f = f;
        }

        public void FindCycle()
        {
            bool found = false;

            do
            {
                found = false;

                // 全ての点を調べる
                foreach ( var item in this.f )
                {
                    // 有効な辺か?
                    if ( !item.CycleCheck )
                        continue;

                    // 始点を指す有効な辺があるか? 終点から辺は出ているか?
                    if ( Contains1( item.ParentCode ) && Contains2( item.ChildCode ) )
                    {
                        continue;
                    }

                    // サイクルの一部ではないので、この辺を削除する
                    item.CycleCheck = false;
                    found = true;
                }
            } while ( found );
        }

        // code(頂点)を指す辺(項)があるかどうか判定する
        private bool Contains1( string code )
        {
            foreach ( var item in this.f )
            {
                if ( item.CycleCheck && item.ChildCode == code )
                    return true;
            }
            return false;
        }

        // code(頂点)に繋がる辺(項)があるかどうか判定する
        private bool Contains2( string code )
        {
            foreach ( var item in this.f )
            {
                if ( item.CycleCheck && item.ParentCode == code )
                    return true;
            }
            return false;
        }

        // 見つけたサイクルの辺番号(データベースのrowIndex)を返す
        public List<int> GetCycle()
        {
            List<int> list = new List<int>();

            for (int i = 0; i < this.f.Length; i++)
            {
                if ( this.f[ i ].CycleCheck )
                    list.Add( i );
            }
            return list;
        }
    }

    // データベースの1項目相当
    public class Field
    {
        public string ParentCode { set; get; }
        public string ChildCode { set; get; }
        public int Year { set; get; }
        public int Month { set; get; }
        public bool CycleCheck { set; get; }

        public Field( string p, string c, int y, int m )
        {
            this.ParentCode = p;
            this.ChildCode = c;
            this.Year = y;
            this.Month = m;
            this.CycleCheck = true;
        }

        public override string ToString()
        {
            return string.Format( "{0} {1}", this.ParentCode, this.ChildCode );
        }
    }
}

引用返信 編集キー/
■20232 / inTopicNo.12)  Re[7]: 再帰によるスタックオーバーフロー?
□投稿者/ れい (620回)-(2008/06/07(Sat) 18:50:10)
2008/06/07(Sat) 18:54:23 編集(投稿者)

No20229 (siokoshou さん) に返信
> なるほど!簡単ですね。コードにしてみました。

おつかれです。
でも、私の方法では「一つでも巡回が存在するノードの群」しか取得できません。

> 上記表から上の3行のように親コードと子コードの関係がループするような
> 行を抜き出したいのでとりあえず処理を作ったのですが、

ということなので、OKかもしれませんが、
もし「巡回」そのもの、つまり、
「どういう順でループしてるのか」とか、「何個ループがあるのか」とかを
抜き出したいとするならば不十分です。

ですが、それは結構めんどくさい方法しか見つかっていません。
実装コストも速度的なコストも大きいので、
やめておいたほうが無難です。

やったことはありませんが、RDBでは相当遅くなるでしょう。

#いい方法があるなら論文を書いたらいいかと。


追記。

siokoshouさんのコードだと、
ノードの並び方によってはちょっと時間がかかるかも知れません。

あるノードAが「端」であるとして削除した場合、
次はそのノードAから唯一接続されていたノードBを調査するとよいです。



引用返信 編集キー/


トピック内ページ移動 / << 0 >>

このトピックに書きこむ

過去ログには書き込み不可

管理者用

- Child Tree -