這一期是我打算做的安卓算法面試系列的最后一期了，一來是自從來了美國之后，每天的工作實在太忙了，除了周末之外很少時間能完完整整的總結一些東西。不過第二個原因，也是最重要的原因，就是在這之后我打算好好沉淀積累一下，等有更多的心得體會再分享出來。
這期我打算聊一聊拓撲排序這個算法。在Java里面具體的實現和一些細節(jié)。這里我盡量不用太多的專業(yè)術語，用比較通俗的講法來解釋一些概念。（其實是我的狗嘴也吐不出啥象牙。。。以前學的算法知識早就還給老師了）
其實拓撲排序和廣度優(yōu)先搜索算法在代碼上真的很像，說穿了其實就是圖的遍歷，只不過遍歷的順序和規(guī)則有些少許不同。
相信各位學習計算機科學專業(yè)的同學應該都對高等數學或者大學物理有深刻的陰影。。。我還記得我當時考完大學物理2已經覺得自己要掛了，沒忍住給老師打了一個電話求情，雖然最后老師說我離掛科還遠，但是69分的大學物理2也讓我與那個學期的獎學金無緣了。
可能有人問為什么計算機專業(yè)不直接學Java，C++或者web開發(fā)？一定要先上大學物理或者高等數學？說了這么多廢話，我想說的重點是，每個學科都有一個自己的課程安排，學習一門專業(yè)課之前必須要有一些基礎課程的支撐才行。我們不能不學高等數學和線性代數直接跳去學機器學習，我們也不能不學Java或者python直接上手web項目。這也引申出了這一期的內容，拓撲排序， 怎么樣在已知某些節(jié)點的前序(prerequisites) 節(jié)點的情況下，把這些節(jié)點的順序排列出來。就好比，我知道一定課程的前后順序的情況下，把我這四年大學的課程時間安排排列出來，最后打印成課程表。
比如上面這幅圖，我們怎么可以將其課程的依賴關系，按照先后順利排列起來，這就是拓撲排序可以解決的其中一種，也是最經典的問題。
1.怎么定義數據結構
首先對于圖來說，我們要知道每個節(jié)點有多少子節(jié)點，也就是后繼節(jié)點，在課程安排例子里面可以理解為，學了A課程之后可以學的課程B。那么A就是B的前驅節(jié)點，B就是A的后繼節(jié)點。
在Java中我們可以使用HashMap來實現，根據題目的不同，有時候也可以使用別的數據結構比如二維數組。不過我個人比較喜歡HashMap。
那么節(jié)點的關系可以用一個HashMap來表達，課程使用String 來表示
//節(jié)點的后繼節(jié)點
HashMap<String, HashSet<String>> courses = new HashMap();
同時，在拓撲排序中，我們還需要記錄某個節(jié)點的前驅節(jié)點的數量，因為只有當某個節(jié)點的前驅節(jié)點為0的時候，我們才能處理該節(jié)點。對應到課程學習中，就是只有當我們學習完畢了某個課程的所有前驅課程，我們才能學習該課程。比如圖中的計算機網絡課程，需要先學習組成原理和通信原理一樣。
//記錄每個點的前驅節(jié)點數量
HashMap<String,Integer> preCount = new HashMap<String,Integer>
2.拓撲排序
假設我們已經有了這兩個數據結構并且數據已經填充好了。我們就可以開始進行拓撲排序了。算法很簡單，把前驅節(jié)點數量為0的節(jié)點先放入隊列，每次從隊列彈出的時候把自己的后繼節(jié)點的preCount數量減少1，假如此時后繼節(jié)點的preCount數量減少到0了，就把節(jié)點加入到隊列中。在這個例子里面，彈出一個節(jié)點的意義就是學習一門課程。
這個很好理解，比如我們學習完組成原理,距離學習計算機網絡還差一門課。
當我們把通信原理學習完畢之后，計算機網絡的前驅節(jié)點數量從1減少為0，我們才可以學習計算機網絡。
用代碼來表示的話，如下
//課程調度隊列
Queue<String> queue = new LinkedList<>();
//最后課程的順序
List<String> sequence = new ArrayList<>();
while (!queue.isEmpty()) {
//獲取當前隊列中的第一個課程，將其加入到最后的課程順序列表中
String currentCourse = queue.poll();
sequence.add(currentCourse);
//每當一個課程結束學習之后，找到它的后繼課程
for (String course : courses.get(currentCourse)) {
//加入后繼課程的前驅節(jié)點數量還是大于0 的，說明該課程還沒被學習
if (preCount.get(course) > 0) {
//減少該后繼課程的前驅節(jié)點數量
preCount.put(course, preCount.get(course) - 1);
//如果前去梳理減到0，說明我們已經可以開始學習該課程了，
//加到隊列里面
if (preCount.get(course) == 0) {
queue.add(course);
}
}
}
}
return sequence;
3.和廣度優(yōu)先的不同
其實看代碼大家也可以知道，拓撲排序其實就是廣度優(yōu)先搜索的一種，只不過拓撲排序在插入子節(jié)點到隊列的時候，有一些限制。就是在這里:
if (preCount.get(course) == 0) {
queue.add(course);
}
一般的廣度優(yōu)先只要遍歷了當前節(jié)點，就要把當前節(jié)點的所有自己點都一股腦的插入到隊列中。在拓撲排序里面，因為每個節(jié)點的前驅節(jié)點數量可能會大于1，所以，不能簡單的插入子節(jié)點(或者說后繼節(jié)點)，而是需要額外的數據結構，preCount這個HashMap來決定是否可以把后繼節(jié)點插入。
4.有環(huán)？
圖搜索的一個經典問題是，如果有環(huán)怎么辦？同樣的，在拓撲排序里面，也可能出現存在環(huán)的情況。比如
在下圖這種情況，學生就沒辦法學了。。。。
但是在拓撲排序下面，判斷是否有環(huán)的方法還不太一樣，比如寬度優(yōu)先搜索的情況下，我們可以用一個叫visited的HashSet來記錄已經訪問過的節(jié)點。但是拓撲排序不行。
比如下圖這種情況
當我們學習完A之后，其實我們是不能遍歷完全所有節(jié)點的，因為B和C的前驅節(jié)點數量都為1，程序在跑完第一個循環(huán)
while (!queue.isEmpty()) {
//獲取到A
String currentCourse = queue.poll();
sequence.add(currentCourse);
之后，就會直接結束了。
所以其實我們判斷環(huán)的方法要換成->判斷我們是否能學習完所有課程。
HashMap<String, HashSet<String>> courses = new HashMap();
//假如最后我們能學習完所有課程
if(result.size() == course.keySet().size()){
return true;
}else{
return false;
}
5.應用的范圍
拓撲排序的題目可以出現很多種，但是都是萬變不離其宗，掌握好我們需要的數據結構，熟練的寫出廣度優(yōu)先算法的模板代碼， 其實就萬事大吉了。以后比如還有類似的問題，像安裝軟件，比如要安裝A，要先安裝依賴C，等等之類的問題，相信大家都可以迎刃而解了?？偨Y的來講，一旦我們發(fā)現需要進行對依賴之間進行排序的，用拓撲排序都沒毛病。
6.題目代碼
Leetcode 里面的Course Schedule, 大家可以自己練習一下。
我沒有講的部分就是數據初始化的部分，不過很簡單，大家自己摸索。
我的答案
public int[] findOrder(int numCourses, int[][] prerequisites) {
// record dependecy counts
HashMap<Integer, Integer> dependeciesCount = new HashMap<>();
HashMap<Integer, HashSet<Integer>> dependeciesRelation = new HashMap<>();
for (int i = 0; i < numCourses; i++) {
dependeciesCount.put(i, 0);
dependeciesRelation.put(i, new HashSet<>());
}
for (int i = 0; i < prerequisites.length; i++) {
int pre = prerequisites[i][1];
int suf = prerequisites[i][0];
dependeciesCount.put(suf, dependeciesCount.get(suf) + 1);
dependeciesRelation.get(pre).add(suf);
}
Queue<Integer> queue = new LinkedList<>();
for (Map.Entry<Integer, Integer> entry : dependeciesCount.entrySet()) {
if (entry.getValue() == 0) {
queue.add(entry.getKey());
}
}
int[] index = new int[numCourses];
int currentIndex = 0;
while (!queue.isEmpty()) {
Integer currentCourse = queue.poll();
index[currentIndex] = currentCourse;
currentIndex++;
for (Integer nei : dependeciesRelation.get(currentCourse)) {
if (dependeciesCount.get(nei) > 0) {
dependeciesCount.put(nei, dependeciesCount.get(nei) - 1);
if (dependeciesCount.get(nei) == 0) {
queue.add(nei);
}
}
}
}
int[] empty = {};
return currentIndex == numCourses ? index : empty;
}
后記
最后一期算法教程寫完了，其實感覺如果大家能把這7個大塊給充分理解，面對大部分的公司的算法面試其實也沒多大問題了。這也是我2017年-2018年初面試各個公司的算法題的一些心得體會。
雖然我的標題一直都是以面試 開頭，但是我覺得最重要的還是學習，或者說是復習算法的這個過程。去理解去學習的這個過程才是精髓。當然，這些內容也是上學就應該學好的，現在重新復習，也算是還債(technical debt)。。。。
回頭看這個系列的初衷，也是希望大家在面對面試的同時，能回顧一些以前上學時候的知識,做到溫故而知新。只要讀者看了我的文章，能發(fā)出一種“挖槽這個以前好像學過啊”的感嘆，我也就滿足了~
2019年對我來說是一個新的起點，我也要不停的督促自己好好工作，多反思多學習，以后爭取能分享更多高質量的文章和知識。希望自己永遠不要忘掉當初雄心壯志面試硅谷公司的那顆赤子之心。
