寫在前：拓?fù)渑判?strong>本質(zhì)是BFS和貪心算法，是這兩種算法在有向圖應(yīng)用的專有名詞，即拓?fù)渑判蜥槍?duì)有向圖問題。參考這里。
拓?fù)渑判驅(qū)嶋H上應(yīng)用的是貪心算法。貪心算法簡(jiǎn)而言之：每一步最優(yōu)，全局就最優(yōu)。
具體到拓?fù)渑判?，每一次都從圖中刪除沒有前驅(qū)的頂點(diǎn)，這里并不需要真正的做刪除操作，我們可以設(shè)置一個(gè)入度數(shù)組，每一輪都輸出入度為 0 的結(jié)點(diǎn)，并移除它、修改它指向的結(jié)點(diǎn)的入度（?1即可），依次得到的結(jié)點(diǎn)序列就是拓?fù)渑判虻慕Y(jié)點(diǎn)序列。如果圖中還有結(jié)點(diǎn)沒有被移除，則說明“不能完成所有課程的學(xué)習(xí)”。
拓?fù)渑判虮ＷC了每個(gè)活動(dòng)（在這題中是“課程”）的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前面，并且可以完成所有活動(dòng)。拓?fù)渑判虻慕Y(jié)果不唯一。拓?fù)渑判蜻€可以用于檢測(cè)一個(gè)有向圖是否有環(huán)。相關(guān)的概念還有 AOV 網(wǎng)，這里就不展開了。
ps：入度：指向當(dāng)前節(jié)點(diǎn)的節(jié)點(diǎn)個(gè)數(shù)；后繼節(jié)點(diǎn)：當(dāng)前節(jié)點(diǎn)指向的節(jié)點(diǎn)
拓?fù)渑判蜃⒁恻c(diǎn)：
- 拓?fù)渑判虻?strong>結(jié)果不唯一
- 可以檢測(cè)有向圖是否有環(huán)（對(duì)于無向圖是否有環(huán)使用并查集這種數(shù)據(jù)結(jié)構(gòu)）
- 貪心點(diǎn)：讓入度為1的點(diǎn)入隊(duì)
- 刪除節(jié)點(diǎn)的操作，通過入度數(shù)組體現(xiàn)！
算法的基本流程：
- 在開始排序前，掃描對(duì)應(yīng)的存儲(chǔ)空間（使用鄰接表），將入度為 0 的結(jié)點(diǎn)放入隊(duì)列。
- 只要隊(duì)列非空，就從隊(duì)首取出入度為 0 的結(jié)點(diǎn)，將這個(gè)結(jié)點(diǎn)輸出到結(jié)果集中，并且將這個(gè)結(jié)點(diǎn)的所有鄰接結(jié)點(diǎn)（它指向的結(jié)點(diǎn)）的入度減 1，在減 1 以后，如果這個(gè)被減 1的結(jié)點(diǎn)的入度為 0 ，就繼續(xù)入隊(duì)。
- 當(dāng)隊(duì)列為空的時(shí)候，檢查結(jié)果集中的頂點(diǎn)個(gè)數(shù)是否和課程數(shù)相等即可。
在代碼具體實(shí)現(xiàn)的時(shí)候，除了保存入度為 0 的隊(duì)列，我們還需要兩個(gè)輔助的數(shù)據(jù)結(jié)構(gòu)（本質(zhì)都是數(shù)組結(jié)構(gòu)）：
- 鄰接表：通過結(jié)點(diǎn)的索引，我們能夠得到這個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)，注：為了避免重復(fù)加入，鄰接表元素為hashset類型
- 入度數(shù)組：通過結(jié)點(diǎn)的索引，我們能夠得到指向這個(gè)結(jié)點(diǎn)的結(jié)點(diǎn)個(gè)數(shù)。
這個(gè)兩個(gè)數(shù)據(jù)結(jié)構(gòu)在遍歷題目給出的鄰邊以后就可以很方便地得到。
應(yīng)用場(chǎng)景：任務(wù)調(diào)度計(jì)劃、課程安排
1.課程表（207 - 中）
題目描述：你這個(gè)學(xué)期必須選修 numCourses 門課程，記為 0 到 numCourses - 1 。
在選修某些課程之前需要一些先修課程。 先修課程按數(shù)組 prerequisites 給出，其中 prerequisites[i] = [ai, bi] ，表示如果要學(xué)習(xí)課程 ai 則 必須 先學(xué)習(xí)課程 bi 。例如，先修課程對(duì) [0, 1] 表示：想要學(xué)習(xí)課程 0 ，你需要先完成課程 1 。
請(qǐng)你判斷是否可能完成所有課程的學(xué)習(xí)？如果可以，返回 true ；否則，返回 false 。
示例：
輸入：numCourses = 2, prerequisites = [[1,0]]
輸出：true
解釋：總共有 2 門課程。學(xué)習(xí)課程 1 之前，你需要完成課程 0 。這是可能的。
輸入：numCourses = 2, prerequisites = [[1,0],[0,1]]
輸出：false
解釋：總共有 2 門課程。學(xué)習(xí)課程 1 之前，你需要先完成課程 0 ；并且學(xué)習(xí)課程 0 之前，你還應(yīng)先完成課程 1 。這是不可能的
代碼實(shí)現(xiàn)：
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses <= 0) return false;
// 不需要先修課程
if (prerequisites.length == 0) return true;
int[] inDegree = new int[numCourses];
HashSet<Integer>[] adj = new HashSet[numCourses];
for (int i = 0; i < numCourses; i++) {
adj[i] = new HashSet<>();
}
// 遍歷鄰邊，得到入度數(shù)組和鄰接表
for (int[] p : prerequisites) {
inDegree[p[0]]++;
adj[p[1]].add(p[0]);
}
Queue<Integer> queue = new LinkedList<>();
// 加入入度為0的節(jié)點(diǎn)
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.add(i);
}
}
// 記錄已經(jīng)出隊(duì)的課程數(shù)量（選修的課程數(shù)）
int cnt = 0;
while (!queue.isEmpty()) {
Integer top = queue.poll();
cnt++;
// 遍歷當(dāng)前節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)
for (int successor : adj[top]) {
// ps：通過重置后繼幾點(diǎn)的入度數(shù)組，“刪除”top節(jié)點(diǎn)
inDegree[successor]--;
if (inDegree[successor] == 0) {
queue.add(successor);
}
}
}
return cnt == numCourses;
}
2.課程表II（210 - 中）
題目描述：現(xiàn)在你總共有 n 門課需要選，記為 0 到 n-1。在選修某些課程之前需要一些先修課程。 例如，想要學(xué)習(xí)課程 0 ，你需要先完成課程 1 ，我們用一個(gè)匹配來表示他們: [0,1]
給定課程總量以及它們的先決條件，返回你為了學(xué)完所有課程所安排的學(xué)習(xí)順序。
可能會(huì)有多個(gè)正確的順序，你只要返回一種就可以了。如果不可能完成所有課程，返回一個(gè)空數(shù)組。
示例：
輸入：numCourses = 2, prerequisites = [[1,0]]
輸出：true
解釋：總共有 2 門課程。學(xué)習(xí)課程 1 之前，你需要完成課程 0 。這是可能的。
輸入：numCourses = 2, prerequisites = [[1,0],[0,1]]
輸出：false
解釋：總共有 2 門課程。學(xué)習(xí)課程 1 之前，你需要先完成課程 0 ；并且學(xué)習(xí)課程 0 之前，你還應(yīng)先完成課程 1 。這是不可能的
代碼實(shí)現(xiàn)：
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (numCourses <= 0) return new int[0];
int[] inDegree = new int[numCourses];
HashSet<Integer>[] adj = new HashSet[numCourses];
for (int i = 0; i < numCourses; i++) {
adj[i] = new HashSet<>();
}
for (int[] p : prerequisites) {
inDegree[p[0]]++;
adj[p[1]].add(p[0]);
}
int cnt = 0;
int[] ans = new int[numCourses];
Queue<Integer> queue = new LinkedList<>();
// 入度為0的節(jié)點(diǎn)入隊(duì)列
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.add(i);
}
}
// 當(dāng)前課程修完，并加入結(jié)果集
while (!queue.isEmpty()) {
Integer top = queue.poll();
ans[cnt] = top;
cnt++;
for (int successor : adj[top]) {
inDegree[successor]--;
if (inDegree[successor] == 0) {
queue.add(successor);
}
}
}
if (cnt == numCourses) return ans;
return new int[0];
}
