深度优先遍历举例说明
时间: 2023-11-19 15:54:35 浏览: 41
深度优先遍历是一种图的遍历算法,其基本思想是从初始访问结点出发,优先访问第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,继续访问它的第一个邻接结点,直到到达最深处,然后回溯到前一个结点,再访问它的下一个邻接结点,直到所有结点都被访问到为止。
举个例子,假设有如下图:
```
1--2--3
| | |
4--5--6
```
从结点1开始进行深度优先遍历,步骤如下:
1. 访问结点1,并标记为已访问。
2. 查找结点1的第一个邻接结点2,访问结点2,并标记为已访问。
3. 查找结点2的第一个邻接结点3,访问结点3,并标记为已访问。
4. 结点3没有未访问的邻接结点,回溯到结点2。
5. 查找结点2的下一个邻接结点5,访问结点5,并标记为已访问。
6. 查找结点5的第一个邻接结点6,访问结点6,并标记为已访问。
7. 结点6没有未访问的邻接结点,回溯到结点5。
8. 结点5没有未访问的邻接结点,回溯到结点2。
9. 结点2没有未访问的邻接结点,回溯到结点1。
10. 查找结点1的下一个邻接结点4,访问结点4,并标记为已访问。
11. 查找结点4的第一个邻接结点5,但结点5已经被访问过了,继续查找结点4的下一个邻接结点2。
12. 结点2已经被访问过了,继续查找结点4的下一个邻接结点1。
13. 结点1已经被访问过了,回溯到结点4。
14. 结点4没有未访问的邻接结点,回溯到结点1。
15. 所有结点都被访问过了,遍历结束。
相关问题
深度优先遍历和广度优先遍历如何做题,举例说明
深度优先遍历(DFS)和广度优先遍历(BFS)是图的两种基本遍历方式。在做题时,可以根据题目要求选择合适的遍历方式。
DFS 的基本思想是从起点开始,沿着一条路径一直走到底,如果此时还有其他路径,就返回上一个节点,继续走其他路径,直到遍历完整张图。DFS 通常使用递归实现,这样可以方便地处理回退问题。
举个例子,假设有一张无向图如下:
```
1
/ | \
2--3--4
/ \ /
5 6-7
```
如果要对这张图进行 DFS 遍历,可以从节点 1 开始,依次访问与其相邻的节点 2、3、5、6、4、7。具体实现可以使用递归方式,也可以使用栈模拟递归过程。
BFS 的基本思想是按照层次遍历图,从起点开始,先访问起点的所有邻居节点,然后依次访问这些邻居节点的邻居节点,直到遍历完整张图。BFS 通常使用队列实现,这样可以方便地处理层次遍历。
继续以上面的无向图为例,如果要对这张图进行 BFS 遍历,可以从节点 1 开始,先访问与其相邻的节点 2、3、4,然后访问节点 2 的邻居节点 5、6,访问节点 3 的邻居节点 6、7,直到遍历完整张图。具体实现可以使用队列,依次将每个节点的邻居节点加入队列中,并按照队列的先进先出原则进行访问。
二叉树的深度优先遍历可以分为先序、中序、后序遍历,请说明先序、中序、后序是如何遍历一棵二叉树的,请举例一颗二叉树,并给出后序遍历非递归的思想与实现代码。
二叉树的深度优先遍历包括先序遍历、中序遍历和后序遍历。其中,先序遍历的遍历顺序为先遍历根节点,再遍历左子树,最后遍历右子树;中序遍历的遍历顺序为先遍历左子树,再遍历根节点,最后遍历右子树;后序遍历的遍历顺序为先遍历左子树,再遍历右子树,最后遍历根节点。下面以一颗二叉树为例进行说明。
```
1
/ \
2 3
/ \ \
4 5 6
```
先序遍历:1 2 4 5 3 6
中序遍历:4 2 5 1 3 6
后序遍历:4 5 2 6 3 1
下面给出后序遍历的非递归实现代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def postorderTraversal(root: TreeNode) -> List[int]:
if not root:
return []
stack1, stack2 = [root], []
while stack1:
node = stack1.pop()
stack2.append(node)
if node.left:
stack1.append(node.left)
if node.right:
stack1.append(node.right)
res = []
while stack2:
res.append(stack2.pop().val)
return res
```
该算法使用了两个栈,第一个栈用于存储待处理节点,第二个栈用于存储已经处理过的节点。首先将根节点压入第一个栈中,然后对于每个弹出的节点,将其压入第二个栈中,并按照右子树、左子树的顺序依次将其左右子节点压入第一个栈中。最后,将第二个栈中的节点依次弹出并记录其值,即为后序遍历的结果。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)