深度优先遍历&广度优先遍历

时间:2023-03-10 02:09:10
深度优先遍历&广度优先遍历

二叉树的前序遍历,中序遍历,后序遍历

树的遍历:

先根遍历——访问根结点,按照从左至右顺序先根遍历根结点的每一颗子树。

后根遍历——按照从左至右顺序后根遍历根结点的每一颗子树,访问根结点。

深度优先遍历&广度优先遍历

先根:ABEFCDG

后根:EFBCGDA

森林的遍历:

前序遍历——分树前根遍历

中序遍历——分树后根遍历

深度优先遍历&广度优先遍历

深度优先遍历:相似于树的前序遍历,首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。

路径:0->2->4->1->5->3->5->6->5->1->4->2->1

024156

广度优先遍历:相似于树的层次遍历,用队列的方法。

路径:0->2->1->3->4->5->6

0213456