使用邻接矩阵或者邻接表创建一个图,并对这个图进行深度优先遍历和广度优先遍历。
时间: 2023-12-05 17:17:02 浏览: 77
建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历.doc
5星 · 资源好评率100%
好的,以下是一个使用邻接矩阵创建的无向图,并分别展示了深度优先遍历和广度优先遍历的过程。
邻接矩阵如下:
```
A B C D E F
A 0 1 0 1 0 0
B 1 0 1 0 1 0
C 0 1 0 1 0 1
D 1 0 1 0 0 1
E 0 1 0 0 0 1
F 0 0 1 1 1 0
```
其中,行和列分别代表节点,1 表示两个节点之间有边相连,0 表示没有边相连。
深度优先遍历过程:
1. 从节点 A 开始。
2. 把节点 A 标记为已访问。
3. 查找节点 A 的邻居节点,并选择其中一个未访问的节点进行访问。由于节点 B 未访问过,因此选择节点 B 进行访问。
4. 把节点 B 标记为已访问。
5. 查找节点 B 的邻居节点,并选择其中一个未访问的节点进行访问。由于节点 C 未访问过,因此选择节点 C 进行访问。
6. 把节点 C 标记为已访问。
7. 查找节点 C 的邻居节点,并选择其中一个未访问的节点进行访问。由于节点 D 未访问过,因此选择节点 D 进行访问。
8. 把节点 D 标记为已访问。
9. 查找节点 D 的邻居节点,并选择其中一个未访问的节点进行访问。由于节点 F 未访问过,因此选择节点 F 进行访问。
10. 把节点 F 标记为已访问。
11. 查找节点 F 的邻居节点,并选择其中一个未访问的节点进行访问。由于节点 E 未访问过,因此选择节点 E 进行访问。
12. 把节点 E 标记为已访问。
13. 没有其他未访问的节点,结束遍历。
深度优先遍历的顺序为:A -> B -> C -> D -> F -> E。
广度优先遍历过程:
1. 从节点 A 开始。
2. 把节点 A 标记为已访问,并将其加入队列中。
3. 从队列中取出首个节点 B,并查找其邻居节点。
4. 把节点 B 的邻居节点 C 和节点 D 标记为已访问,并将其加入队列中。
5. 从队列中取出首个节点 C,并查找其邻居节点。
6. 把节点 C 的邻居节点 A、节点 D 和节点 F 标记为已访问,并将其加入队列中。
7. 从队列中取出首个节点 D,并查找其邻居节点。
8. 把节点 D 的邻居节点 B 和节点 C 标记为已访问,并将其加入队列中。
9. 从队列中取出首个节点 F,并查找其邻居节点。
10. 把节点 F 的邻居节点 C、节点 E 和节点 B 标记为已访问,并将其加入队列中。
11. 从队列中取出首个节点 E,并查找其邻居节点。
12. 把节点 E 的邻居节点 F 标记为已访问,并将其加入队列中。
13. 队列为空,结束遍历。
广度优先遍历的顺序为:A -> B -> C -> D -> F -> E。
阅读全文