8-18 トポロジカルソート

問題

下記の、閉路のない有向グラフ(Directed Acyclic Graph)(DAG)を
トポロジカルソートした解を列挙する。



ABCDEFGHIJや
ACBDHFEGIJが解となります。

再帰の技法の57ページを参考にさせていただきました。

ソース

using System;
using System.Collections.Generic;

class Program
{                                    //A  B  C  D  E  F  G  H  I  J
    static int[,] rinsetuGyouretu = {{ 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 }, //A
                                     { 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }, //B
                                     { 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }, //C
                                     { 0, 0, 0, 0, 1, 1, 0, 1, 0, 0 }, //D
                                     { 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 }, //E
                                     { 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 }, //F
                                     { 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 }, //G
                                     { 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 }, //H
                                     { 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, //I
                                     { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, //J
    };

    static void Main()
    {
        var stk = new Stack<List<int>>();
        List<int> WillPush;

        for (int I = 0; I <= rinsetuGyouretu.GetUpperBound(0); I++) {
            if (IsValid(I, null)) {
                WillPush = new List<int>();
                WillPush.Add(I);
                stk.Push(WillPush);
            }
        }

        int answerCnt = 0;
        while (stk.Count > 0) {
            List<int> WorkJyoutai = stk.Pop();
            if (WorkJyoutai.Count == rinsetuGyouretu.GetUpperBound(0) + 1) {
                string WillOut = "";
                foreach (int each in WorkJyoutai) {
                    WillOut += ((char)('A' + each)).ToString() + ',';
                }
                Console.WriteLine("answer{0:D2}={1}", ++answerCnt, WillOut);
                continue;
            }

            for (int I = 0; I <= rinsetuGyouretu.GetUpperBound(0); I++) {
                if (IsValid(I, WorkJyoutai)) {
                    WillPush = new List<int>();
                    WillPush.AddRange(WorkJyoutai);
                    WillPush.Add(I);
                    stk.Push(WillPush);
                }
            }
        }
    }

    static bool IsValid(int pNewPos, List<int> pIntList)
    {
        //チェック1 NewPosが訪問済でないこと
        if (pIntList != null && pIntList.Contains(pNewPos)) return false;

        //チェック2 NewPosに移動可能な未訪問ノードが存在しないこと
        for (int I = 0; I <= rinsetuGyouretu.GetUpperBound(0); I++) {
            if (rinsetuGyouretu[I, pNewPos] == 1) {
                if (pIntList == null || pIntList.Contains(I) == false) return false;
            }
        }

        return true;
    }
}

実行結果

answer01=C,A,B,D,H,F,G,E,I,J,
answer02=C,A,B,D,H,F,E,G,I,J,
answer03=C,A,B,D,H,E,F,G,I,J,
answer04=C,A,B,D,F,H,G,E,I,J,
answer05=C,A,B,D,F,H,E,G,I,J,
answer06=C,A,B,D,F,G,H,E,I,J,
answer07=C,A,B,D,F,G,E,H,I,J,
answer08=C,A,B,D,F,E,H,G,I,J,
answer09=C,A,B,D,F,E,G,H,I,J,
answer10=C,A,B,D,E,H,F,G,I,J,
answer11=C,A,B,D,E,F,H,G,I,J,
answer12=C,A,B,D,E,F,G,H,I,J,
answer13=A,C,B,D,H,F,G,E,I,J,
answer14=A,C,B,D,H,F,E,G,I,J,
answer15=A,C,B,D,H,E,F,G,I,J,
answer16=A,C,B,D,F,H,G,E,I,J,
answer17=A,C,B,D,F,H,E,G,I,J,
answer18=A,C,B,D,F,G,H,E,I,J,
answer19=A,C,B,D,F,G,E,H,I,J,
answer20=A,C,B,D,F,E,H,G,I,J,
answer21=A,C,B,D,F,E,G,H,I,J,
answer22=A,C,B,D,E,H,F,G,I,J,
answer23=A,C,B,D,E,F,H,G,I,J,
answer24=A,C,B,D,E,F,G,H,I,J,
answer25=A,B,C,D,H,F,G,E,I,J,
answer26=A,B,C,D,H,F,E,G,I,J,
answer27=A,B,C,D,H,E,F,G,I,J,
answer28=A,B,C,D,F,H,G,E,I,J,
answer29=A,B,C,D,F,H,E,G,I,J,
answer30=A,B,C,D,F,G,H,E,I,J,
answer31=A,B,C,D,F,G,E,H,I,J,
answer32=A,B,C,D,F,E,H,G,I,J,
answer33=A,B,C,D,F,E,G,H,I,J,
answer34=A,B,C,D,E,H,F,G,I,J,
answer35=A,B,C,D,E,F,H,G,I,J,
answer36=A,B,C,D,E,F,G,H,I,J,

解説

隣接行列で有向グラフを表現してます。

wikipedia --- トポロジカルソート
ALGORITHM NOTE 隣接行列