和樹一樣，圖也是由帶子集的結點組成的，但和樹不一樣的地方在于，這些結點可以有多個父結點，所以可能會形成**自環**（loop）或者**圈**（cycle）。除了鏈接——也被稱作邊（edges）——之外，兩個結點之間可能地有比指針更多的信息，而且可能會有值和**權重**。邊有方向的圖被稱為有向圖，而只有雙向指針的圖被稱為無向圖。邊上有權重的圖被稱為加權圖。 有三種方法來表示圖，但你只要搞清楚鄰接矩陣（[**adjacency matrices**](http://en.wikipedia.org/wiki/Adjacency_matrix)）和鄰接表（[**adjacency lists**](http://en.wikipedia.org/wiki/Adjacency_list)）就行了。你應該了解它們計算的復雜程度、它們需要折衷的地方，以及如何在現實的代碼中實現它們。用哪種方法取決于你有的圖的類型，比如連接完整的簡單圖可能用鄰接矩陣來實現更好，而稀疏一些的圖則可能用鄰接表來表示更好。 請注意，如果你是在實現加權圖，很可能需要定義一個**Edge**類。 圖論是一個非常寬泛的話題，所以很難知道一個人應該為一場面試去熟悉多少種圖論算法，所以我只是列出了我認為可以覆蓋90%圖論問題的內容：你絕對必須知道該如何遍歷一個圖（深度優先或者廣度優先），以及如何做拓撲排序（[**topological sorting**](http://en.wikipedia.org/wiki/Topological_sorting)），你應該知道如何實現迪杰斯特拉（[**Dijkstra**](http://e/)）的最短路徑算法（這里有一個制作精巧的視頻解釋了這一算法），同時也要知道如何實現普里姆（[**Prim**’**s**](http://en.wikipedia.org/wiki/Prim%27s_algorithm)）算法。最后，如果你還知道如何實現A*搜索算法（[**A***](http://en.wikipedia.org/wiki/A*_search_algorithm)**search**algorithm），那就更好了。