首页 > 试题广场 >

假设这个无向图G=（V,E）代表了一个社区中居民之间的社交关

[单选题]

假设这个无向图G=（V,E）代表了一个社区中居民之间的社交关系，每个节点代表一个居民，每条边代表两个居民之间的社交关系，其中V={1, 2, 3, 4, 5, 6, 7}，E={(3, 7), (3, 6), (3, 4), (2, 3), (1, 2), (2, 4), (4, 5), (4, 6)}。现在对这个社区的居民社交关系进行深度优先遍历，不能得到的序列是（）

```
4, 3, 7, 6, 2, 1, 5
```
```
5, 4, 3, 2, 6, 7, 1
```
```
1, 2, 3, 7, 6, 4, 5
```
```
6, 3, 7, 4, 2, 1, 5
```

查看答案及解析

一笑而过2222

解析深度优先遍历（DFS）是从图的某个顶点开始，沿着一条路径尽可能深地探索，直到无法继续，然后回溯，继续探索其他路径。 - 选项A：从节点4开始，4可以到达3，3可以到达7，7没有其他未访问邻居，回溯到3，3到达6，6没有其他未访问邻居，回溯到3，3到达2，2到达1，1没有其他未访问邻居，回溯到2，2没有其他未访问邻居，回溯到4，4到达5 ，可以得到该序列。 - 选项B：从节点5开始，5只能到达4，4可以到达3，3到达2，2到达1，1没有其他未访问邻居，回溯到2，2没有其他未访问邻居，回溯到3，3到达6，6到达7 ，无法得到该序列，因为按照深度优先遍历规则，在到达2之后会先把与2相关联的1访问完，而不是先去访问6。 - 选项C：从节点1开始，1到达2，2到达3，3到达7，7没有其他未访问邻居，回溯到3，3到达6，6没有其他未访问邻居，回溯到3，3到达4，4到达5 ，可以得到该序列。 - 选项D：从节点6开始，6到达3，3到达7，7没有其他未访问邻居，回溯到3，3到达4，4到达2，2到达1，1没有其他未访问邻居，回溯到2，2没有其他未访问邻居，回溯到4，4到达5 ，可以得到该序列。正确答案 B

发表于 2025-03-22 09:20:11 回复(0)