读书人

有向图的DFS跟BFS遍历序列

发布时间: 2012-09-20 09:36:50 作者: 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)遍历出来的结果分别是什么?(我知道不唯一,每种给一种序列就可以了)。

读书人网 >软件架构设计

热点推荐