前言
图是比树结构更复杂的一种数据结构。在线性结构中，除首结点没有前驱、末尾结点没有后继外，一个结点只有唯一的一个直接前驱和唯一的一个直接后继。在树结构中，除根结点没有前驱结点外，其余的每个结点只有唯一的一个前驱（双亲）结点和多个后继（子树）结点。而在图中，任意两个结点之间都可能有直接的关系，所以图中一个结点的前驱结点和后继结点的数目是没有限制的。
正文
1. 图的遍历
- 图的遍历是指从某个顶点出发，沿着某条搜索路径对图中的所有顶点进行访问且只访问一次的过程。图的遍历算法是求解图的连通性问题、拓扑排序及求关键路径等算法的基础。
- 图的遍历要比树的遍历复杂得多。因为图的任一个结点都可能与其余顶点相邻接，所以在访问了某个顶点之后，可能沿着某路径，又回到该结点，为了避免对顶点进行重复访问，在图的遍历过程中必须记下每个已访问过的顶点。深度优先搜索和广度优先搜索是两种遍历图的基本方法。
2. 深度优先搜索（Depth First Search，DFS）
此种方法类似于树的先根遍历，在第一次经过一个顶点就进行访问操作。从图 G 中任一结点 v 出发按深度优先搜索法进行遍历的步骤如下：
- 设置搜索指针 p，使 p 指向顶点 v。
- 访问 p 所指顶点，并使 p 指向与其相邻接的且尚未被访问过的顶点。
- 若 p 所指顶点存在，则重复步骤 2，否则执行步骤 4。
- 沿着刚才访问的次序和方向回溯到一个尚有邻接顶点且未被访问过的顶点，并使 p 指向这个未被访问的顶点，然后重复步骤 2，直到所有的顶点均被访问为止。
3. 生成树
- 对于有 n 个顶点的连通图，至少有 n - 1 条边，而生成树中切好有 n - 1 条边，所以连通图的生成树是该图的极小连通子图。
- 图的生成树不是唯一的。从不同的顶点出发，选择不同的存储方式，用不同的求解方法，可以得到不同的生成树。对于非连通图而言，每个连通分量中的顶点集合遍历时走过的边集一起构成若干棵生成树，分别称为非连通图的生成树森林。按深度和广度优先搜索进行遍历将得到不同的生成树，分别称为深度优先生成树和广度优先生成树。
