图的表示
- 邻接矩阵，空间效率低
- 邻接表
图的遍历
图的遍历需要访问所有顶点一次且仅一次，访问所有边一次且仅一次。与树遍历一样，作为图算法基石的图搜索，本身也必须能够高效地实现。诸如深度优先、广度优先、最佳优先等基本而典型的图搜索，都可以在线性时间内完成。准确地，若顶点数和边数分别为n和e，则这些算法自身仅需O(n + e)时间。既然图搜索需要访问所有的顶点和边，故这已经是我们所能期望的最优的结果。
- 广度优先搜索 Breadth-first search,BFS
越早被访问到的顶点，其邻居越优先被选用。BFS类似于树的层次遍历。
- 深度优先搜索Depth-first search,DFS