和树一样，图也是由带子集的结点组成的，但和树不一样的地方在于，这些结点可以有多个父结点，所以可能会形成**自环**（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），那就更好了。