經(jīng)常有讀者問我「圖」這種數(shù)據(jù)結(jié)構(gòu)，因為我們公眾號什么數(shù)據(jù)結(jié)構(gòu)和算法都寫過了，唯獨(dú)沒有專門介紹「圖」。

其實在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的框架思維中說過，雖然圖可以玩出更多的算法，解決更復(fù)雜的問題，但本質(zhì)上圖可以認(rèn)為是多叉樹的延伸。

面試筆試很少出現(xiàn)圖相關(guān)的問題，就算有，大多也是簡單的遍歷問題，基本上可以完全照搬多叉樹的遍歷。

至于最小生成樹，Dijkstra，網(wǎng)絡(luò)流這些算法問題，他們當(dāng)然很牛逼，但是，就算法筆試來說，學(xué)習(xí)的成本高但收益低，沒什么性價比，不如多刷幾道動態(tài)規(guī)劃，真的。

那么，本文依然秉持我們號的風(fēng)格，只講「圖」最實用的，離我們最近的部分，讓你心里對圖有個直觀的認(rèn)識。

圖的邏輯結(jié)構(gòu)和具體實現(xiàn)

一幅圖是由節(jié)點(diǎn)和邊構(gòu)成的，邏輯結(jié)構(gòu)如下：

什么叫「邏輯結(jié)構(gòu)」？就是說為了方便研究，我們把圖抽象成這個樣子。

根據(jù)這個邏輯結(jié)構(gòu)，我們可以認(rèn)為每個節(jié)點(diǎn)的實現(xiàn)如下：

/* 圖節(jié)點(diǎn)的邏輯結(jié)構(gòu) */class Vertex {

int id;

Vertex［］ neighbors;

}

看到這個實現(xiàn)，你有沒有很熟悉？它和我們之前說的多叉樹節(jié)點(diǎn)幾乎完全一樣：

/* 基本的 N 叉樹節(jié)點(diǎn) */class TreeNode {

int val;

TreeNode［］ children;

}

所以說，圖真的沒啥高深的，就是高級點(diǎn)的多叉樹而已。

不過呢，上面的這種實現(xiàn)是「邏輯上的」，實際上我們很少用這個Vertex類實現(xiàn)圖，而是用常說的鄰接表和鄰接矩陣來實現(xiàn)。

比如還是剛才那幅圖：

用鄰接表和鄰接矩陣的存儲方式如下：

鄰接表很直觀，我把每個節(jié)點(diǎn)x的鄰居都存到一個列表里，然后把x和這個列表關(guān)聯(lián)起來，這樣就可以通過一個節(jié)點(diǎn)x找到它的所有相鄰節(jié)點(diǎn)。

鄰接矩陣則是一個二維布爾數(shù)組，我們權(quán)且成為matrix，如果節(jié)點(diǎn)x和y是相連的，那么就把matrix［x］［y］設(shè)為true。如果想找節(jié)點(diǎn)x的鄰居，去掃一圈matrix［x］［。。］就行了。

那么，為什么有這兩種存儲圖的方式呢？肯定是因為他們各有優(yōu)劣。

對于鄰接表，好處是占用的空間少。

你看鄰接矩陣?yán)锩婵罩敲炊辔恢?，肯定需要更多的存儲空間。

但是，鄰接表無法快速判斷兩個節(jié)點(diǎn)是否相鄰。

比如說我想判斷節(jié)點(diǎn)1是否和節(jié)點(diǎn)3相鄰，我要去鄰接表里1對應(yīng)的鄰居列表里查找3是否存在。但對于鄰接矩陣就簡單了，只要看看matrix［1］［3］就知道了，效率高。

所以說，使用哪一種方式實現(xiàn)圖，要看具體情況。

好了，對于「圖」這種數(shù)據(jù)結(jié)構(gòu)，能看懂上面這些就綽綽夠用了。

那你可能會問，我們這個圖的模型僅僅是「有向無權(quán)圖」，不是還有什么加權(quán)圖，無向圖，等等……

其實，這些更復(fù)雜的模型都是基于這個最簡單的圖衍生出來的。

有向加權(quán)圖怎么實現(xiàn)？很簡單呀：

如果是鄰接表，我們不僅僅存儲某個節(jié)點(diǎn)x的所有鄰居節(jié)點(diǎn)，還存儲x到每個鄰居的權(quán)重，不就實現(xiàn)加權(quán)有向圖了嗎？

如果是鄰接矩陣，matrix［x］［y］不再是布爾值，而是一個 int 值，0 表示沒有連接，其他值表示權(quán)重，不就變成加權(quán)有向圖了嗎？

無向圖怎么實現(xiàn)？也很簡單，所謂的「無向」，是不是等同于「雙向」？

如果連接無向圖中的節(jié)點(diǎn)x和y，把matrix［x］［y］和matrix［y］［x］都變成true不就行了；鄰接表也是類似的操作。

把上面的技巧合起來，就變成了無向加權(quán)圖……

好了，關(guān)于圖的基本介紹就到這里，現(xiàn)在不管來什么亂七八糟的圖，你心里應(yīng)該都有底了。

下面來看看所有數(shù)據(jù)結(jié)構(gòu)都逃不過的問題：遍歷。

圖的遍歷

圖怎么遍歷？還是那句話，參考多叉樹，多叉樹的遍歷框架如下：

/* 多叉樹遍歷框架 */void traverse（TreeNode root） {

if （root == null） return;

for （TreeNode child ： root.children）

traverse（child）;

}

圖和多叉樹最大的區(qū)別是，圖是可能包含環(huán)的，你從圖的某一個節(jié)點(diǎn)開始遍歷，有可能走了一圈又回到這個節(jié)點(diǎn)。

所以，如果圖包含環(huán)，遍歷框架就要一個visited數(shù)組進(jìn)行輔助：

Graph graph;

boolean［］ visited;

/* 圖遍歷框架 */void traverse（Graph graph， int s） {

if （visited［s］） return;

// 經(jīng)過節(jié)點(diǎn) s

visited［s］ = true;

for （TreeNode neighbor ： graph.neighbors（s））

traverse（neighbor）;

// 離開節(jié)點(diǎn) s

visited［s］ = false;

}

好吧，看到這個框架，你是不是又想到了 回溯算法核心套路 中的回溯算法框架？

這個visited數(shù)組的操作很像回溯算法做「做選擇」和「撤銷選擇」，區(qū)別在于位置，回溯算法的「做選擇」和「撤銷選擇」在 for 循環(huán)里面，而對visited數(shù)組的操作在 for 循環(huán)外面。

在 for 循環(huán)里面和外面唯一的區(qū)別就是對根節(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（“l(fā)eave： ” + 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（“l(fā)eave： ” + child.val）;

}

}

前者會正確打印所有節(jié)點(diǎn)的進(jìn)入和離開信息，而后者唯獨(dú)會少打印整棵樹根節(jié)點(diǎn)的進(jìn)入和離開信息。

為什么回溯算法框架會用后者？因為回溯算法關(guān)注的不是節(jié)點(diǎn)，而是樹枝，不信你看 回溯算法核心套路 里面的圖，它可以忽略根節(jié)點(diǎn)。

顯然，對于這里「圖」的遍歷，我們應(yīng)該把visited的操作放到 for 循環(huán)外面，否則會漏掉起始點(diǎn)的遍歷。

當(dāng)然，當(dāng)有向圖含有環(huán)的時候才需要visited數(shù)組輔助，如果不含環(huán)，連visited數(shù)組都省了，基本就是多叉樹的遍歷。

題目實踐

下面我們來看力扣第 797 題「所有可能路徑」，函數(shù)簽名如下：

List《List《Integer》》 allPathsSourceTarget（int［］［］ graph）;

題目輸入一幅有向無環(huán)圖，這個圖包含n個節(jié)點(diǎn)，標(biāo)號為0， 1， 2，。。。， n - 1，請你計算所有從節(jié)點(diǎn)0到節(jié)點(diǎn)n - 1的路徑。

輸入的這個graph其實就是「鄰接表」表示的一幅圖，graph［i］存儲這節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)。

比如輸入graph = ［［1，2］，［3］，［3］，［］］，就代表下面這幅圖：

算法應(yīng)該返回［［0，1，3］，［0，2，3］］，即0到3的所有路徑。

解法很簡單，以0為起點(diǎn)遍歷圖，同時記錄遍歷過的路徑，當(dāng)遍歷到終點(diǎn)時將路徑記錄下來即可。

既然輸入的圖是無環(huán)的，我們就不需要visited數(shù)組輔助了，直接套用圖的遍歷框架：

// 記錄所有路徑

List《List《Integer》》 res = new LinkedList《》（）;

public List《List《Integer》》 allPathsSourceTarget（int［］［］ graph） {

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;

}

// 遞歸每個相鄰節(jié)點(diǎn)

for （int v ： graph［s］） {

traverse（graph， v， path）;

}

// 從路徑移出節(jié)點(diǎn) s

path.removeLast（）;

}

這道題就這樣解決了。

最后總結(jié)一下，圖的存儲方式主要有鄰接表和鄰接矩陣，無論什么花里胡哨的圖，都可以用這兩種方式存儲。

在筆試中，最?？嫉乃惴ㄊ菆D的遍歷，和多叉樹的遍歷框架是非常類似的。

當(dāng)然，圖還會有很多其他的有趣算法，比如二分圖判定呀，環(huán)檢測呀（編譯器循環(huán)引用檢測就是類似的算法）等等，以后有機(jī)會再講吧，本文就到這了。

責(zé)任編輯：lq6