ゆるふわ競プロ

Javaでゆるゆる競プロしています.忘れっぽいのでメモ用,復習用

トポロジカルソート

トポロジカルソートを書いてみたので記録しておく.


ToplogocalSortとは.

edgeをソートする方法の一種である。並び替えをします.ソートされた後の配列をみた時に配列の左から右向きのpathは存在するが右から左むきのpathは存在しないようにするということです。文字はわかりにくいので図にしてみます。

edge数 : 4 (1 , 2 , 3 , 4)
path : 1 → 3 , 3 → 2 , 4 → 2

f:id:topaz1-3:20190223214331p:plain 良い例の場合矢印(path)が全て左から右向きに伸びています。逆に悪い例の場合右から左向きの矢印が存在します。ソートが完了しているのは上の二つとなります.今回は4つの例しか紹介しませんでしたが他にも良い例,悪い例が存在します.


考え方

左むきの矢印が存在しなけれ良い。これは言い換えると入ってくる矢印が存在しなければ良い事になる.pathの行き先に設定されていないedgeから順に取っていけばソートは完成します.

  1. 各edgeに入ってくるpathの数を数える
  2. 入ってくるpathが0のedgeに注目してそのedgeからスタートするpathの行き先のedgeの数を減らす
  3. 2を繰り返す
  4. edge数繰り返したら終了

書いたコード

使い方 :

    from     : pathの出発点
    to       : pathの終着点
    datasize : edge数 
    public static int[] topologicalSort(int[] from, int[] to, int datasize) {
        int[] ans = new int[datasize + 1];
        int[] inCount = new int[datasize + 1]; // [0] は使わない
        inCount[0] = -1;
        // それぞれedgeに入ってくるpathの数を数える
        for (int i = 0; i < datasize; i++) {
            inCount[to[i]]++;
        }
        int ansPos = 0;
        while (true) {
            int finCount = 0;
            int tarpos = 0;
            // inCount == -1 は調べ終わった場所
            for (int i = 0; i < datasize + 1; i++) {
                if (inCount[i] == -1) {
                    finCount++;
                } else if (inCount[i] == 0) {
                    tarpos = i;
                    break;
                }
            }
           // 全て調べ終わった
            if (finCount == datasize + 1) {
                break;
            }
            for (int i = 0; i < from.length; i++) {
                if (from[i] == tarpos) {
                    inCount[to[i]]--;
                }
            }
            inCount[tarpos] = -1;
            ans[ansPos] = tarpos;
            ansPos++;
        }

        return ans;
    }

書いたはいいものの別の方法があったのでそれも記録しておく

参考にしたコード 実装方法としてはdfsを用いて適当な点から終点まで走らせて終点に達したらStackにに入れるという手法だ。簡略化したコードで書く。

    boolean visited[n];
    int from[m] , int to[m];

    for( int i = 0 ; i < n; i ++) {
         if( ! visited[i] ) {
            dfs( i );
         }
    }

    dfs(int pos){
        visited[pos] = true;
        for(int i = 0;i < m;i ++){
            if( from[i] == pos && visited[to[i]] ){
                dfs(to[i]);
             }
        }
    stack.push(pos);
    }

このようにすると終着点から順にstackに入れられるようになる。

関連

AOJトポロジカルソート