拓扑排序、使用拓扑排序解决实际问题

拓扑排序介绍

http://www.cnblogs.com/dolphin0520/archive/2011/04/16/2017737.html

算法题

假设有些任务需要执行，任务之间有依赖，给出一个满足条件的执行顺序。
输入：
b, a(表示b依赖于a，需要a先执行，才能执行b，其他类似)
c, b
d, a
输出：a, b, c, d

使用拓扑排序；

package com.tao;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by Michael on 2017/9/5.
 */

/**
 * 拓扑排序
 */
public class Q1 {

    public static void main(String[] args) {

        String str = "bacbda";
        int n = str.length()/2; //n行输入

        int[][] map = new int[128][128];    //邻接矩阵
        int[] outDegree = new int[128];     //出度数组


        //初始化邻接矩阵和出度数组
        for(int i = 0; i < str.length(); i = i + 2) {

            char x = str.charAt(i);
            char y = str.charAt(i+1);

            //x --> y
            if(map[x][y] == 0) {
                map[x][y] = 1;
                outDegree[x]++;
            }
        }


        //拓扑排序
        List<Character> result = topoSort(map, outDegree, str);
        System.out.println(result);

    }


    //拓扑排序
    public static List<Character> topoSort(int[][] map, int[] outDegree, String str) {

        List<Character> result = new ArrayList<>();

        int len = outDegree.length;

        //n趟表示针对n行输入
        for(int i = 0; i < str.length(); i++) {

            for(int j = 0; j < len; j++) {
                //找出出度为0的节点
                if(outDegree[j] == 0 && inString((char)j, str)) {
                    result.add((char) j);
                    outDegree[j]--;

                    //将与之关联的边去掉
                    for(int k = 0; k < map.length; k++) {
                        if(map[k][j] == 1) {
                            map[k][j] = 0;
                            outDegree[k]--;
                        }
                    }

                    break;
                }
            }
        }

        return result;
    }


    //判断字符是否在字符串中
    public static boolean inString(char ch, String str) {

        for(int i = 0; i < str.length(); i++) {
            if(ch == str.charAt(i)) {
                return true;
            }
        }
        return false;
    }

}