作者：labuladong
公眾號(hào)：labuladong
讀完本文，可以去力扣解決如下題目：
797. 所有可能的路徑（Medium）
經(jīng)常有讀者問(wèn)我「圖」這種數(shù)據(jù)結(jié)構(gòu)，其實(shí)我在 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的框架思維 中說(shuō)過(guò)，雖然圖可以玩出更多的算法，解決更復(fù)雜的問(wèn)題，但本質(zhì)上圖可以認(rèn)為是多叉樹的延伸。
面試筆試很少出現(xiàn)圖相關(guān)的問(wèn)題，就算有，大多也是簡(jiǎn)單的遍歷問(wèn)題，基本上可以完全照搬多叉樹的遍歷。
那么，本文依然秉持我們號(hào)的風(fēng)格，只講「圖」最實(shí)用的，離我們最近的部分，讓你心里對(duì)圖有個(gè)直觀的認(rèn)識(shí)，文末我給出了其他經(jīng)典圖論算法，理解本文后應(yīng)該都可以拿下的。
一幅圖是由節(jié)點(diǎn)和邊構(gòu)成的，邏輯結(jié)構(gòu)如下：
什么叫「邏輯結(jié)構(gòu)」？就是說(shuō)為了方便研究，我們把圖抽象成這個(gè)樣子。
根據(jù)這個(gè)邏輯結(jié)構(gòu)，我們可以認(rèn)為每個(gè)節(jié)點(diǎn)的實(shí)現(xiàn)如下：
/* 圖節(jié)點(diǎn)的邏輯結(jié)構(gòu) */
class Vertex {
int id;
Vertex[] neighbors;
}
看到這個(gè)實(shí)現(xiàn)，你有沒(méi)有很熟悉？它和我們之前說(shuō)的多叉樹節(jié)點(diǎn)幾乎完全一樣：
/* 基本的 N 叉樹節(jié)點(diǎn) */
class TreeNode {
int val;
TreeNode[] children;
}
所以說(shuō)，圖真的沒(méi)啥高深的，就是高級(jí)點(diǎn)的多叉樹而已。
不過(guò)呢，上面的這種實(shí)現(xiàn)是「邏輯上的」，實(shí)際上我們很少用這個(gè)Vertex類實(shí)現(xiàn)圖，而是用常說(shuō)的鄰接表和鄰接矩陣來(lái)實(shí)現(xiàn)。
比如還是剛才那幅圖：
用鄰接表和鄰接矩陣的存儲(chǔ)方式如下：
鄰接表很直觀，我把每個(gè)節(jié)點(diǎn)x的鄰居都存到一個(gè)列表里，然后把x和這個(gè)列表關(guān)聯(lián)起來(lái)，這樣就可以通過(guò)一個(gè)節(jié)點(diǎn)x找到它的所有相鄰節(jié)點(diǎn)。
鄰接矩陣則是一個(gè)二維布爾數(shù)組，我們權(quán)且稱為matrix，如果節(jié)點(diǎn)x和y是相連的，那么就把matrix[x][y]設(shè)為true（上圖中綠色的方格代表true）。如果想找節(jié)點(diǎn)x的鄰居，去掃一圈matrix[x][..]就行了。
如果用代碼的形式來(lái)表現(xiàn)，鄰接表和鄰接矩陣大概長(zhǎng)這樣：
// 鄰接矩陣
// graph[x] 存儲(chǔ) x 的所有鄰居節(jié)點(diǎn)
List<Integer>[] graph;
// 鄰接矩陣
// matrix[x][y] 記錄 x 是否有一條指向 y 的邊
boolean[][] matrix;
那么，為什么有這兩種存儲(chǔ)圖的方式呢？肯定是因?yàn)樗麄兏饔袃?yōu)劣。
對(duì)于鄰接表，好處是占用的空間少。
你看鄰接矩陣?yán)锩婵罩敲炊辔恢?，肯定需要更多的存?chǔ)空間。
但是，鄰接表無(wú)法快速判斷兩個(gè)節(jié)點(diǎn)是否相鄰。
比如說(shuō)我想判斷節(jié)點(diǎn)1是否和節(jié)點(diǎn)3相鄰，我要去鄰接表里1對(duì)應(yīng)的鄰居列表里查找3是否存在。但對(duì)于鄰接矩陣就簡(jiǎn)單了，只要看看matrix[1][3]就知道了，效率高。
所以說(shuō)，使用哪一種方式實(shí)現(xiàn)圖，要看具體情況。
好了，對(duì)于「圖」這種數(shù)據(jù)結(jié)構(gòu)，能看懂上面這些就綽綽夠用了。
那你可能會(huì)問(wèn)，我們這個(gè)圖的模型僅僅是「有向無(wú)權(quán)圖」，不是還有什么加權(quán)圖，無(wú)向圖，等等……
其實(shí)，這些更復(fù)雜的模型都是基于這個(gè)最簡(jiǎn)單的圖衍生出來(lái)的。
有向加權(quán)圖怎么實(shí)現(xiàn)？很簡(jiǎn)單呀：
如果是鄰接表，我們不僅僅存儲(chǔ)某個(gè)節(jié)點(diǎn)x的所有鄰居節(jié)點(diǎn)，還存儲(chǔ)x到每個(gè)鄰居的權(quán)重，不就實(shí)現(xiàn)加權(quán)有向圖了嗎？
如果是鄰接矩陣，matrix[x][y]不再是布爾值，而是一個(gè) int 值，0 表示沒(méi)有連接，其他值表示權(quán)重，不就變成加權(quán)有向圖了嗎？
如果用代碼的形式來(lái)表現(xiàn)，大概長(zhǎng)這樣：
// 鄰接矩陣
// graph[x] 存儲(chǔ) x 的所有鄰居節(jié)點(diǎn)以及對(duì)應(yīng)的權(quán)重
List<int[]>[] graph;
// 鄰接矩陣
// matrix[x][y] 記錄 x 指向 y 的邊的權(quán)重，0 表示不相鄰
int[][] matrix;
無(wú)向圖怎么實(shí)現(xiàn)？也很簡(jiǎn)單，所謂的「無(wú)向」，是不是等同于「雙向」？
如果連接無(wú)向圖中的節(jié)點(diǎn)x和y，把matrix[x][y]和matrix[y][x]都變成true不就行了；鄰接表也是類似的操作，在x的鄰居列表里添加y，同時(shí)在y的鄰居列表里添加x。
把上面的技巧合起來(lái)，就變成了無(wú)向加權(quán)圖……
好了，關(guān)于圖的基本介紹就到這里，現(xiàn)在不管來(lái)什么亂七八糟的圖，你心里應(yīng)該都有底了。
下面來(lái)看看所有數(shù)據(jù)結(jié)構(gòu)都逃不過(guò)的問(wèn)題：遍歷。
學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的框架思維 說(shuō)過(guò)，各種數(shù)據(jù)結(jié)構(gòu)被發(fā)明出來(lái)無(wú)非就是為了遍歷和訪問(wèn)，所以「遍歷」是所有數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。
圖怎么遍歷？還是那句話，參考多叉樹，多叉樹的遍歷框架如下：
/* 多叉樹遍歷框架 */
void traverse(TreeNode root) {
if (root == null) return;
for (TreeNode child : root.children) {
traverse(child);
}
}
圖和多叉樹最大的區(qū)別是，圖是可能包含環(huán)的，你從圖的某一個(gè)節(jié)點(diǎn)開(kāi)始遍歷，有可能走了一圈又回到這個(gè)節(jié)點(diǎn)。
所以，如果圖包含環(huán)，遍歷框架就要一個(gè)visited數(shù)組進(jìn)行輔助：
// 記錄被遍歷過(guò)的節(jié)點(diǎn)
boolean[] visited;
// 記錄從起點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑
boolean[] onPath;
/* 圖遍歷框架 */
void traverse(Graph graph, int s) {
if (visited[s]) return;
// 經(jīng)過(guò)節(jié)點(diǎn) s，標(biāo)記為已遍歷
visited[s] = true;
// 做選擇：標(biāo)記節(jié)點(diǎn) s 在路徑上
onPath[s] = true;
for (int neighbor : graph.neighbors(s)) {
traverse(graph, neighbor);
}
// 撤銷選擇：節(jié)點(diǎn) s 離開(kāi)路徑
onPath[s] = false;
}
注意visited數(shù)組和onPath數(shù)組的區(qū)別，因?yàn)槎鏄渌闶翘厥獾膱D，所以用遍歷二叉樹的過(guò)程來(lái)理解下這兩個(gè)數(shù)組的區(qū)別：
上述 GIF 描述了遞歸遍歷二叉樹的過(guò)程，在visited中被標(biāo)記為 true 的節(jié)點(diǎn)用灰色表示，在onPath中被標(biāo)記為 true 的節(jié)點(diǎn)用綠色表示，這下你可以理解它們二者的區(qū)別了吧。
如果讓你處理路徑相關(guān)的問(wèn)題，這個(gè)onPath變量是肯定會(huì)被用到的，比如 拓?fù)渑判?/a> 中就有運(yùn)用。
另外，你應(yīng)該注意到了，這個(gè)onPath數(shù)組的操作很像 回溯算法核心套路 中做「做選擇」和「撤銷選擇」，區(qū)別在于位置：回溯算法的「做選擇」和「撤銷選擇」在 for 循環(huán)里面，而對(duì)onPath數(shù)組的操作在 for 循環(huán)外面。
在 for 循環(huán)里面和外面唯一的區(qū)別就是對(duì)根節(jié)點(diǎn)的處理。
比如下面兩種多叉樹的遍歷：
void traverse(TreeNode root) {
if (root == null) return;
System.out.println('enter: ' + root.val);
for (TreeNode child : root.children) {
traverse(child);
}
System.out.println('leave: ' + root.val);
}
void traverse(TreeNode root) {
if (root == null) return;
for (TreeNode child : root.children) {
System.out.println('enter: ' + child.val);
traverse(child);
System.out.println('leave: ' + child.val);
}
}
前者會(huì)正確打印所有節(jié)點(diǎn)的進(jìn)入和離開(kāi)信息，而后者唯獨(dú)會(huì)少打印整棵樹根節(jié)點(diǎn)的進(jìn)入和離開(kāi)信息。
為什么回溯算法框架會(huì)用后者？因?yàn)榛厮菟惴P(guān)注的不是節(jié)點(diǎn)，而是樹枝，不信你看 回溯算法核心套路 里面的圖。
顯然，對(duì)于這里「圖」的遍歷，我們應(yīng)該把onPath的操作放到 for 循環(huán)外面，否則會(huì)漏掉記錄起始點(diǎn)的遍歷。
說(shuō)了這么多onPath數(shù)組，再說(shuō)下visited數(shù)組，其目的很明顯了，由于圖可能含有環(huán)，visited數(shù)組就是防止遞歸重復(fù)遍歷同一個(gè)節(jié)點(diǎn)進(jìn)入死循環(huán)的。
當(dāng)然，如果題目告訴你圖中不含環(huán)，可以把visited數(shù)組都省掉，基本就是多叉樹的遍歷。
下面我們來(lái)看力扣第 797 題「所有可能路徑」，函數(shù)簽名如下：
List<List<Integer>> allPathsSourceTarget(int[][] graph);
題目輸入一幅有向無(wú)環(huán)圖，這個(gè)圖包含n個(gè)節(jié)點(diǎn)，標(biāo)號(hào)為0, 1, 2,..., n - 1，請(qǐng)你計(jì)算所有從節(jié)點(diǎn)0到節(jié)點(diǎn)n - 1的路徑。
輸入的這個(gè)graph其實(shí)就是「鄰接表」表示的一幅圖，graph[i]存儲(chǔ)這節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)。
比如輸入graph = [[1,2],[3],[3],[]]，就代表下面這幅圖：
算法應(yīng)該返回[[0,1,3],[0,2,3]]，即0到3的所有路徑。
解法很簡(jiǎn)單，以0為起點(diǎn)遍歷圖，同時(shí)記錄遍歷過(guò)的路徑，當(dāng)遍歷到終點(diǎn)時(shí)將路徑記錄下來(lái)即可。
既然輸入的圖是無(wú)環(huán)的，我們就不需要visited數(shù)組輔助了，直接套用圖的遍歷框架：
// 記錄所有路徑
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
// 維護(hù)遞歸過(guò)程中經(jīng)過(guò)的路徑
LinkedList<Integer> path = new LinkedList<>();
traverse(graph, 0, path);
return res;
}
/* 圖的遍歷框架 */
void traverse(int[][] graph, int s, LinkedList<Integer> path) {
// 添加節(jié)點(diǎn) s 到路徑
path.addLast(s);
int n = graph.length;
if (s == n - 1) {
// 到達(dá)終點(diǎn)
res.add(new LinkedList<>(path));
path.removeLast();
return;
}
// 遞歸每個(gè)相鄰節(jié)點(diǎn)
for (int v : graph[s]) {
traverse(graph, v, path);
}
// 從路徑移出節(jié)點(diǎn) s
path.removeLast();
}
這道題就這樣解決了，注意 Java 的語(yǔ)言特性，向res中添加path時(shí)需要拷貝一個(gè)新的列表，否則最終res中的列表都是空的。
最后總結(jié)一下，圖的存儲(chǔ)方式主要有鄰接表和鄰接矩陣，無(wú)論什么花里胡哨的圖，都可以用這兩種方式存儲(chǔ)。
在筆試中，最?？嫉乃惴ㄊ菆D的遍歷，和多叉樹的遍歷框架是非常類似的。
當(dāng)然，圖還會(huì)有很多其他的有趣算法，比如 二分圖判定，環(huán)檢測(cè)和拓?fù)渑判?/a>（編譯器循環(huán)引用檢測(cè)就是類似的算法），最小生成樹，Dijkstra 最短路徑算法 等等，有興趣的讀者可以去看看，本文就到這了。
聯(lián)系客服
