做LC新出的題：先行課課程表，看到了Topological Sorting.
回想起去年有次在群里跟同學(xué)討論一道類似的題。當(dāng)時(shí)還不知道Topological，就自顧自地做了一番，后來別人來一個(gè)提一次，都說用Topological。連解釋都沒有。我就郁悶了。后來也沒看。今天總結(jié)性一次搞定。
魚C的帖子?精簡
從AOV網(wǎng)中選擇一個(gè)沒有前趨的頂點(diǎn)（該頂點(diǎn)的入度為0）并且輸出它；
從網(wǎng)中刪去該頂點(diǎn)，并且刪去從該頂點(diǎn)發(fā)出的全部有向邊；
重復(fù)上述兩步，直到剩余網(wǎng)中不再存在沒有前趨的頂點(diǎn)為止。
算法時(shí)間復(fù)雜度：
對(duì)一個(gè)具有n個(gè)頂點(diǎn)，e條邊的網(wǎng)來說，初始建立入度為零的頂點(diǎn)棧，要檢查所有頂點(diǎn)一次，執(zhí)行時(shí)間為O(n)。
排序中，若AOV網(wǎng)無回路，則每個(gè)頂點(diǎn)入、出棧各一次，每個(gè)表結(jié)點(diǎn)被檢查一次，因而執(zhí)行時(shí)間是 O(n+e)。
所以，整個(gè)算法的時(shí)間復(fù)雜度是 O(n+e)。
CSDN拓?fù)渑判虻脑砑捌鋵?shí)現(xiàn) （詳細(xì)）
最后是LC上的代碼：
public int[] findOrder(int numCourses, int[][] prerequisites){
－－// nextVertex中的每個(gè)entry，int指課程，set指此課程的所有先行課
－－Map<Integer, Set<Integer>> nextVertex = new HashMap<>();
－－// preVertex[i] 記錄課程“i”是先行課的次數(shù)
－－int[] preVertex = new int[numCourses];
－－// 掃描所有先行課限制
－－for(int i = 0; i < prerequisites.length; i++){
－－－－if(!nextVertex.containsKey(prerequisites[i][0]))?
－－－－－－nextVertex.put(prerequisites[i][0], new HashSet<>());
－－－－// boolean add(E e),? 如果e已經(jīng)存在，Set的add方法返回false。
－－－－// 每門課只記錄其第一個(gè)先行課！從第二個(gè)起add返回false，避免dup。
－－－－if (nextVertex.get(prerequisites[i][0]).add(prerequisites[i][1]))
－－－－－－preVertex[prerequisites[i][1]]++;
－－}
－－// BFS Queue,?
－－Deque<Integer> queue = new ArrayDeque<>();? ?
－－for(int i = 0; i < preVertex.length; i++)?
－－－－if(preVertex[i] == 0) queue.offerLast(i); // 記錄所有沒被當(dāng)作先行課的課程
－－//把不是先行課的課程依次倒著插入。
－－int[] res = new int[numCourses]; // 最終輸出
－－int index = res.length - 1; //倒著來
－－while(!queue.isEmpty()){
－－－－int key = queue.pollFirst();
－－－－res[index--] == key;
－－－－// 更新此課的所有后行課
－－－－if(nextVertex.containsKey(key)){
－－－－for(int i:nextVertex.get(key)) // 便利set
－－－－－－if(--preVertex[i] == 0) // 如果此后行課沒有別的先行課了
－－－－－－－－queue.offerLast(i); //存入queue
－－－－}
－－--numCourses; // 更新所剩課程數(shù)
－－}
－－// 如果課程都被包了，返回結(jié)果，不然返回新array
－－return numCourses == 0 ? res
}
