拓扑排序

拓扑排序

之前说过广度优先搜索，是按照度来进行排序的。这里来说一下另外一种图的算法。其中的节点有依赖关系，如果节点A依赖于节点B，则列表中的节点A就必须在节点B后，这就是拓扑排序。

使用拓扑排序来创建一个有序的任务列表

public class TuoPuSort {

    public static void main(String[] args) {
        // 先分出三组依赖的任务队列来
        Queue<String> q1 = new ArrayDeque<>();
        q1.add("锻炼");
        q1.add("洗澡");
        q1.add("穿衣服");

        Queue<String> q2 = new ArrayDeque<>();
        q2.add("刷牙");
        q2.add("吃早餐");

        Queue<String> q3 = new ArrayDeque<>();
        q3.add("打包午餐");

        List<String> taskExeList = new ArrayList<>();
        // 初始任务是起床
        taskExeList.add("起床");

        List<Queue<String>> queueList = new ArrayList<>();
        queueList.add(q1);
        queueList.add(q2);
        queueList.add(q3);
        Random random = new Random();
        while (!queueList.isEmpty()){
            int i = random.nextInt(queueList.size());
            Queue<String> taskQueue = queueList.get(i);
            taskExeList.add(taskQueue.poll());
            if(taskQueue.isEmpty()){
                queueList.remove(i);
            }
        }

        taskExeList.forEach(
                System.out::println
        );

    }
}