对下列图分别执行dfs(1)和dfs(5),写出遍历序列并构造出相应的dfs生成树
时间: 2024-05-04 08:18:41 浏览: 34
我们先看一下给出的图:
```
1---2---3
| | |
4---5---6
```
接下来分别执行dfs(1)和dfs(5)。
### dfs(1)
从1开始遍历,遍历的过程中记录下每个节点的遍历时间戳,并维护一个栈来记录当前的遍历路径。
1. 遍历1,时间戳为1,将1入栈
2. 遍历2,时间戳为2,将2入栈
3. 遍历4,时间戳为3,将4入栈
4. 4没有未遍历的邻居,将4出栈
5. 遍历5,时间戳为4,将5入栈
6. 遍历6,时间戳为5,将6入栈
7. 6没有未遍历的邻居,将6出栈
8. 5没有未遍历的邻居,将5出栈
9. 遍历3,时间戳为6,将3入栈
10. 3没有未遍历的邻居,将3出栈
11. 2没有未遍历的邻居,将2出栈
12. 1没有未遍历的邻居,将1出栈
遍历序列为:1 2 4 5 6 3
dfs生成树为:
```
1
/ \
2 3
/ \ / \
4 5 6 |
|
```
### dfs(5)
从5开始遍历,遍历的过程中记录下每个节点的遍历时间戳,并维护一个栈来记录当前的遍历路径。
1. 遍历5,时间戳为1,将5入栈
2. 遍历2,时间戳为2,将2入栈
3. 遍历1,时间戳为3,将1入栈
4. 1没有未遍历的邻居,将1出栈
5. 2没有未遍历的邻居,将2出栈
6. 遍历4,时间戳为4,将4入栈
7. 4没有未遍历的邻居,将4出栈
8. 遍历3,时间戳为5,将3入栈
9. 3没有未遍历的邻居,将3出栈
10. 5没有未遍历的邻居,将5出栈
遍历序列为:5 2 1 4 3
dfs生成树为:
```
5---2---1
| |
4 3
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)
![](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)