前言

我覺得學習這些之前,一定要對圖的數(shù)據(jù)結構和抽象模型有概念,并且圖構建的代碼模版應該手到擒來,不然還是挺折磨的,不是這差一點就是那差一點,寫道力扣卡卡的非常煩人.

復習模版

我覺得單拿出來再說這個模版一點也不冗余,一定要背會死記住!并且要理解它們的數(shù)據(jù)結構

• 鄰接表形式存儲圖
  返回值類型,參數(shù)有哪些,如何構建邊的關系,非常重要.
  既然是構建圖,那么我們的返回值一定是圖沒毛病吧,我們是用鄰接表的形式,所以返回值類型就是List [].
  對于參數(shù)而言:
  a. 我們要確認這個圖有幾個節(jié)點,不然沒辦法創(chuàng)建節(jié)點.
  b. 我們要知道節(jié)點和邊的關系,一般給你的是二維的數(shù)據(jù),里面有節(jié)點和邊的關系
  如何構建邊的關系呢?
  如果給你的是一個二維數(shù)組,你看題意是怎么說的.
  我拿課程表這個題給你舉例子,[0,1]表示:想學習課程0,就要先完成課程1.
  指向由你自己選擇,我這邊選擇from是1,to是0.
  指向關系是from指向to.
  那如何添加到鄰接表里,就看你對鄰接表數(shù)據(jù)結構的理解,角碼代表節(jié)點,里面的值代表這個節(jié)點指向哪個節(jié)點.
  代碼實現(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)檢測-DFS版本

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

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

class Solution {// 記錄遞歸堆棧中的節(jié)點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é)點traverse(graph, 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)在遞歸路徑上，說明成環(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) {// 代碼見前文}
}

關于上面遍歷代碼我想補充幾點:

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

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

class Solution {// 記錄一次遞歸堆棧中的節(jié)點boolean[] onPath;// 記錄節(jié)點是否被遍歷過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é)點traverse(graph, 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)在遞歸路徑上，說明成環(huán)了hasCycle = true;return;}if (visited[s]) {// 不用再重復遍歷已遍歷過的節(jié)點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) {// 代碼見前文}
}

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

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

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

因為是BFS,所以我們用隊列去處理,那這個隊列的話我們?nèi)绾稳ス芾砟?
首先我們肯定要往隊列里面添加初始節(jié)點,我們怎么判斷哪個節(jié)點是初始節(jié)點?
記住我們的核心出裝: 根據(jù)入度來判定,入度>0,則代表它是中間節(jié)點;入度=0,代表是初始節(jié)點.所以我們選擇遍歷到入度為0 的節(jié)點添加到隊列里面.

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

遍歷如何處理呢?
? 終止條件： 隊列為空時，表示所有可以遍歷的節(jié)點都已經(jīng)處理完，循環(huán)結束。
? 遍歷方式： 每次從隊列中彈出一個入度為 0 的節(jié)點，遍歷它能指向的所有節(jié)點，并更新入度。
? 入度變?yōu)?0 時入隊： 說明當前節(jié)點的所有前置依賴都已被處理完，可以加入隊列，等待后續(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é)點,遍歷到有環(huán)的節(jié)點,有環(huán)的節(jié)點會被添加進去嗎?
答案是不會的,因為有環(huán)的話我們無法消除這個節(jié)點的入度呀.(不理解的簡單畫個圖就理解了,很簡單的道理)
我一個節(jié)點去遍歷到下一個節(jié)點,只能把下一個節(jié)點的度-1,但你想想這個-1減的是誰的1,是下一個環(huán)對上一個環(huán)的依賴,不是下一個環(huán)對下下一個環(huán)的依賴!
所以有環(huán)的節(jié)點不會被加入進去,那么我們在遍歷的時候就會少遍歷一個.
所以所以!
我們就記錄一下遍歷的節(jié)點個數(shù),和最后的節(jié)點比對一下,如果不相等,那么就代表有環(huán)!
ok,整個流程就是這樣,代碼如下,細細品味吧

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