首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

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

2013-01-26 
有向图的DFS和BFS遍历序列如果有一个有向图,他有始点无法到达的顶点,即始点不存在到达次顶点的路径,那么此

有向图的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只是另一种思路。可以借鉴画图,然后再写程序的思路。
希望对你有帮助!

热点排行