前言

我覺(jué)得學(xué)習(xí)這些之前,一定要對(duì)圖的數(shù)據(jù)結(jié)構(gòu)和抽象模型有概念,并且圖構(gòu)建的代碼模版應(yīng)該手到擒來(lái),不然還是挺折磨的,不是這差一點(diǎn)就是那差一點(diǎn),寫道力扣卡卡的非常煩人.

復(fù)習(xí)模版

我覺(jué)得單拿出來(lái)再說(shuō)這個(gè)模版一點(diǎn)也不冗余,一定要背會(huì)死記住!并且要理解它們的數(shù)據(jù)結(jié)構(gòu)

• 鄰接表形式存儲(chǔ)圖
  返回值類型,參數(shù)有哪些,如何構(gòu)建邊的關(guān)系,非常重要.
  既然是構(gòu)建圖,那么我們的返回值一定是圖沒(méi)毛病吧,我們是用鄰接表的形式,所以返回值類型就是List [].
  對(duì)于參數(shù)而言:
  a. 我們要確認(rèn)這個(gè)圖有幾個(gè)節(jié)點(diǎn),不然沒(méi)辦法創(chuàng)建節(jié)點(diǎn).
  b. 我們要知道節(jié)點(diǎn)和邊的關(guān)系,一般給你的是二維的數(shù)據(jù),里面有節(jié)點(diǎn)和邊的關(guān)系
  如何構(gòu)建邊的關(guān)系呢?
  如果給你的是一個(gè)二維數(shù)組,你看題意是怎么說(shuō)的.
  我拿課程表這個(gè)題給你舉例子,[0,1]表示:想學(xué)習(xí)課程0,就要先完成課程1.
  指向由你自己選擇,我這邊選擇from是1,to是0.
  指向關(guān)系是from指向to.
  那如何添加到鄰接表里,就看你對(duì)鄰接表數(shù)據(jù)結(jié)構(gòu)的理解,角碼代表節(jié)點(diǎn),里面的值代表這個(gè)節(jié)點(diǎn)指向哪個(gè)節(jié)點(diǎn).
  代碼實(shí)現(xiàn)如下:

List<Integer> buildGraph(int numCourses, int[][] prerequisites){List<Integer>[] graph = new LinkedList[numCourses];for(int i=0;i<numCourses;i++){graph[i] = new LinkedList<>();}for(int[] edge: prerequisites){int from = edge[1],to = edge[0];graph[from].add(to);}
}

環(huán)檢測(cè)-DFS版本

構(gòu)建圖的模版我就不寫了,上面是有的.
上一章我們聊過(guò)圖論中和樹不一樣的地方在于圖可能是會(huì)有環(huán)的.
不做任何處理的話可能會(huì)造成死循環(huán).
處理的方式就是記錄下來(lái)我哪些節(jié)點(diǎn)已經(jīng)遍歷過(guò)了,如果已經(jīng)遍歷了就不能再遍歷,并標(biāo)記是有環(huán)了.
那么我們需要兩個(gè)小伙伴幫我們記錄:

• boolean[] onPath - 記錄遞歸遍歷過(guò)哪些節(jié)點(diǎn)了
• boolean hasCycle - 圖中是否有環(huán)
  應(yīng)該很好理解吧,代碼如下:

class Solution {// 記錄遞歸堆棧中的節(jié)點(diǎn)boolean[] onPath;// 記錄圖中是否有環(huán)boolean hasCycle = false;public boolean canFinish(int numCourses, int[][] prerequisites) {List<Integer>[] graph = buildGraph(numCourses, prerequisites);onPath = new boolean[numCourses];for (int i = 0; i < numCourses; i++) {// 遍歷圖中的所有節(jié)點(diǎn)traverse(graph, i);}// 只要沒(méi)有循環(huán)依賴可以完成所有課程return !hasCycle;}// 圖遍歷函數(shù)，遍歷所有路徑void traverse(List<Integer>[] graph, int s) {if (hasCycle) {// 如果已經(jīng)找到了環(huán)，也不用再遍歷了return;}if (onPath[s]) {// s 已經(jīng)在遞歸路徑上，說(shuō)明成環(huán)了hasCycle = true;return;}// 前序代碼位置onPath[s] = true;for (int t : graph[s]) {traverse(graph, t);}// 后序代碼位置onPath[s] = false;}List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {// 代碼見(jiàn)前文}
}

關(guān)于上面遍歷代碼我想補(bǔ)充幾點(diǎn):

1. 我們是要對(duì)每個(gè)節(jié)點(diǎn)都進(jìn)行遞歸遍歷,而不是只遍歷一次,我剛開始學(xué)圖的時(shí)候老是忘記處理這點(diǎn).因?yàn)楹蜆洳灰粯?樹只有一個(gè)起點(diǎn),但是圖可能有多個(gè)連通分量,而樹只有一個(gè)!
2. onPath數(shù)組的處理要理解代表的含義,在onPath的角碼就是代表哪個(gè)節(jié)點(diǎn).onPath[i]的意思就是i節(jié)點(diǎn)是否成環(huán).

但是上面是有冗余計(jì)算的,假如我以3節(jié)點(diǎn)為起點(diǎn)遍歷了所有可達(dá)路徑,沒(méi)有發(fā)現(xiàn)環(huán),那么我又以5為起點(diǎn),遍歷到3節(jié)點(diǎn),我還是要再去遍歷一遍3節(jié)點(diǎn).這就非常難受了.
所以我們不妨再找一個(gè)小伙伴幫忙記一下,讓我們知道已經(jīng)遍歷過(guò)哪些節(jié)點(diǎn),就不需要再遍歷了
boolean[] visited 就是干這個(gè)的.
visited[i] 的意義是i節(jié)點(diǎn)是否被遍歷過(guò).
很簡(jiǎn)單吧,代碼如下:

class Solution {// 記錄一次遞歸堆棧中的節(jié)點(diǎn)boolean[] onPath;// 記錄節(jié)點(diǎn)是否被遍歷過(guò)boolean[] visited;// 記錄圖中是否有環(huán)boolean hasCycle = false;public boolean canFinish(int numCourses, int[][] prerequisites) {List<Integer>[] graph = buildGraph(numCourses, prerequisites);onPath = new boolean[numCourses];visited = new boolean[numCourses];for (int i = 0; i < numCourses; i++) {// 遍歷圖中的所有節(jié)點(diǎn)traverse(graph, i);}// 只要沒(méi)有循環(huán)依賴可以完成所有課程return !hasCycle;}// 圖遍歷函數(shù)，遍歷所有路徑void traverse(List<Integer>[] graph, int s) {if (hasCycle) {// 如果已經(jīng)找到了環(huán)，也不用再遍歷了return;}if (onPath[s]) {// s 已經(jīng)在遞歸路徑上，說(shuō)明成環(huán)了hasCycle = true;return;}if (visited[s]) {// 不用再重復(fù)遍歷已遍歷過(guò)的節(jié)點(diǎn)return;}// 前序代碼位置visited[s] = true;onPath[s] = true;for (int t : graph[s]) {traverse(graph, t);}// 后序代碼位置onPath[s] = false;}List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {// 代碼見(jiàn)前文}
}

環(huán)檢測(cè)- BFS版本

DFS是通過(guò)數(shù)組來(lái)判定是否成環(huán),但是BFS不能這樣了,因?yàn)樗鼪](méi)辦法撤回,只能往下走.
那我們可以通過(guò)每個(gè)節(jié)點(diǎn)的入度來(lái)實(shí)現(xiàn).
所謂「出度」和「入度」是「有向圖」中的概念，很直觀：如果一個(gè)節(jié)點(diǎn) x 有 a 條邊指向別的節(jié)點(diǎn)，同時(shí)被 b 條邊所指，則稱節(jié)點(diǎn) x 的出度為 a，入度為 b。
那既然說(shuō)我們依賴節(jié)點(diǎn)的入度,它一定是被事先構(gòu)建好的,所以我們除了要寫一個(gè)構(gòu)建圖的代碼,還要再寫一段構(gòu)建入度的代碼.
上面也說(shuō)了,判定入度是根據(jù)邊的指向.
那么我們肯定是要循環(huán)一遍我們構(gòu)建的圖,然后根據(jù)節(jié)點(diǎn)的邊去設(shè)置每個(gè)節(jié)點(diǎn)的入度.
代碼如下:

 int[] indegree = new int[numCourses];for(int[] edge: prerequisites){int from = edge[1], to = edge[0];//注意這里計(jì)算的是入度,所以腳碼是toindegree[to]++;
}

因?yàn)槭荁FS,所以我們用隊(duì)列去處理,那這個(gè)隊(duì)列的話我們?nèi)绾稳ス芾砟?
首先我們肯定要往隊(duì)列里面添加初始節(jié)點(diǎn),我們?cè)趺磁袛嗄膫€(gè)節(jié)點(diǎn)是初始節(jié)點(diǎn)?
記住我們的核心出裝: 根據(jù)入度來(lái)判定,入度>0,則代表它是中間節(jié)點(diǎn);入度=0,代表是初始節(jié)點(diǎn).所以我們選擇遍歷到入度為0 的節(jié)點(diǎn)添加到隊(duì)列里面.

Queue<Integer> q = new LinkedList<>();
for(int i =0; i<numCourses;i++){if(indegree[i] == 0){q.offer(i);}
}

遍歷如何處理呢?
? 終止條件： 隊(duì)列為空時(shí)，表示所有可以遍歷的節(jié)點(diǎn)都已經(jīng)處理完，循環(huán)結(jié)束。
? 遍歷方式： 每次從隊(duì)列中彈出一個(gè)入度為 0 的節(jié)點(diǎn)，遍歷它能指向的所有節(jié)點(diǎn)，并更新入度。
? 入度變?yōu)?0 時(shí)入隊(duì)： 說(shuō)明當(dāng)前節(jié)點(diǎn)的所有前置依賴都已被處理完，可以加入隊(duì)列，等待后續(xù)遍歷。

while(!q.isEmpty()){int cur = q.poll();for(int next: graph[cur]){indegree[next]--;if(indegree[next]==0{q.offer(next);}}
}

遍歷完后,那我怎么知道是不是有環(huán)呢?
我們思考一下,如果有環(huán)的話.在環(huán)中的入度可能為0嗎?
我們想一下,從正常的節(jié)點(diǎn),遍歷到有環(huán)的節(jié)點(diǎn),有環(huán)的節(jié)點(diǎn)會(huì)被添加進(jìn)去嗎?
答案是不會(huì)的,因?yàn)橛协h(huán)的話我們無(wú)法消除這個(gè)節(jié)點(diǎn)的入度呀.(不理解的簡(jiǎn)單畫個(gè)圖就理解了,很簡(jiǎn)單的道理)
我一個(gè)節(jié)點(diǎn)去遍歷到下一個(gè)節(jié)點(diǎn),只能把下一個(gè)節(jié)點(diǎn)的度-1,但你想想這個(gè)-1減的是誰(shuí)的1,是下一個(gè)環(huán)對(duì)上一個(gè)環(huán)的依賴,不是下一個(gè)環(huán)對(duì)下下一個(gè)環(huán)的依賴!
所以有環(huán)的節(jié)點(diǎn)不會(huì)被加入進(jìn)去,那么我們?cè)诒闅v的時(shí)候就會(huì)少遍歷一個(gè).
所以所以!
我們就記錄一下遍歷的節(jié)點(diǎn)個(gè)數(shù),和最后的節(jié)點(diǎn)比對(duì)一下,如果不相等,那么就代表有環(huán)!
ok,整個(gè)流程就是這樣,代碼如下,細(xì)細(xì)品味吧

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {// 建圖，有向邊代表「被依賴」關(guān)系List<Integer>[] graph = buildGraph(numCourses, prerequisites);// 構(gòu)建入度數(shù)組int[] indegree = new int[numCourses];for (int[] edge : prerequisites) {int from = edge[1], to = edge[0];// 節(jié)點(diǎn) to 的入度加一indegree[to]++;}// 根據(jù)入度初始化隊(duì)列中的節(jié)點(diǎn)Queue<Integer> q = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (indegree[i] == 0) {// 節(jié)點(diǎn) i 沒(méi)有入度，即沒(méi)有依賴的節(jié)點(diǎn)// 可以作為拓?fù)渑判虻钠瘘c(diǎn)，加入隊(duì)列q.offer(i);}}// 記錄遍歷的節(jié)點(diǎn)個(gè)數(shù)int count = 0;// 開始執(zhí)行 BFS 循環(huán)while (!q.isEmpty()) {// 彈出節(jié)點(diǎn) cur，并將它指向的節(jié)點(diǎn)的入度減一int cur = q.poll();count++;for (int next : graph[cur]) {indegree[next]--;if (indegree[next] == 0) {// 如果入度變?yōu)?0，說(shuō)明 next 依賴的節(jié)點(diǎn)都已被遍歷q.offer(next);}}}// 如果所有節(jié)點(diǎn)都被遍歷過(guò)，說(shuō)明不成環(huán)return count == numCourses;}// 建圖函數(shù)List<Integer>[] buildGraph(int n, int[][] edges) {// 見(jiàn)前文}
}