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

スタックオーバーフローが起きるのは、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 );
        }
    }

    // データベースの１項目相当
    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 );
        }
    }
}