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

2024-12-16 11:06:34
推荐回答(2个)
回答1:

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

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

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

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

扩展资料:

遍历种类:

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

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

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

注意:

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

参考资料来源:百度百科-先序遍历

回答2:

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