图的存储与遍历

① 采用邻接表存储的图的深度优先遍历算法类似于二叉树的先序遍历，为什么是先序呢

这是因为图的深度优先遍历算法先访问所在结点，再访问它的邻接点。与二叉树的先序遍历先访问子树的根结点，再访问它的孩子结点（邻接点）类似。图的广度优先遍历算法类似于二叉树的按层次遍历。

先序遍历也叫做先根遍历、前序遍历，可记做根左右（二叉树父结点向下先左后右）。

首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。

例如，下图所示二叉树的遍历结果是：ABDECF。

(1)图的存储与遍历扩展阅读：

遍历种类：

一、NLR：前序遍历(Preorder Traversal 亦称（先序遍历）），访问根结点的操作发生在遍历其左右子树之前。

二、LNR：中序遍历(Inorder Traversal)，访问根结点的操作发生在遍历其左右子树之中（间）。

三、LRN：后序遍历(Postorder Traversal)，访问根结点的操作发生在遍历其左右子树之后。

注意：

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为 先根遍历、中根遍历和后根遍历。