读书人

有向图的DFS和BFS遍历序列,该怎么解决

发布时间: 2013-01-26 13:47:02 作者: rapoo

有向图的DFS和BFS遍历序列
如果有一个有向图,他有始点无法到达的顶点,即始点不存在到达次顶点的路径,那么此时dfs和bfs应该怎么处理呢?
比如有一个有向图G,他有8个顶点(1-8),邻接矩阵如下。

0 0 1 0 0 0 0 1
0 0 1 0 0 1 1 0
0 0 0 0 1 0 0 0
G 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0


他如何进行DFS和BFS遍历?无法到达的顶点怎么处理?遍历出来的结果分别是什么?(我知道不唯一,每种给一种序列就可以了)。
不要代码~~~因为不是代码问题。
[解决办法]
通过始点遍历完成后,如果还存在没有被访问的点,那么在这些没有被访问过的点中随机选一个继续开始遍历就行了吧
[解决办法]
这个包含多个子图而已,对所有子图一一遍历
[解决办法]
对所有子图一一进行遍历就好了
[解决办法]

引用:
1)他如何进行DFS和BFS遍历?
2)无法到达的顶点怎么处理?
3)遍历出来的结果分别是什么?(我知道不唯一,每种给一种序列就可以了)。


对于1)DFS深度优先遍历(逐个节点递归遍历),BFS广度优先遍历(按层次遍历,可以考虑队列实现);
对于2)你是采用邻接矩阵的存储结构,显然1代表可达,0代表自己到自己或不可达,对于深度优先遍历比如从顶点0(假设顶点依次为0->7)开始遍历。
01234567
000100001
100100110
200001000
300001000
400000000
500001000
600000100
700010000

选择节点
初始起点0第0步
01234567
2第一步0001√00001

4第二步200001√000

7第三步0001√00001√

3第四步700010000

1第五步1√00100110

5第六步1001√001√10

6第七步1001√001√1√0
我画图递推了DFS遍历,BFS只是另一种思路。可以借鉴画图,然后再写程序的思路。
希望对你有帮助!

读书人网 >软件架构设计

热点推荐