图的深度优先遍历+图的广度优先遍历.ppt

图的遍历回顾其他数据结构的遍历: ?顺序表的遍历?单链表的遍历?二叉树、树和森林的遍历问题: 那么对于图,我们怎样进行遍历呢? (需要记录访问过顶点的信息,引入 visited[0 … n-1 ]) ?图的深度优先遍历?图的广度优先遍历这两个算法是后面拓扑排序、求关键路径算法的基础 . 连通图的深度优先遍历?类似于树的先根遍历,是其推广 v开始的连通图①访问 v②分别深度优先遍历 v的各个未被访问的邻接点算法描述: v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0v2v3 v1v4v5 v1v6v7 v2v8 v2v8 v3v7 v3v6 v4v5 v1 v2v3 v4v5v6v7 v8 例图及其邻接表表示演示开始,以 v1 为遍历的起点 v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0v2v3 v1v4v5 v1v6v7 v2v8 v2v8 v3v7 v3v6 v4v5 v1 v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0v2v3 v1v4v5 v1v6v7 v2v8 v2v8 v3v7 v3v6 v4v5 ,v1 v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0v2v3 v1v4 v5 v1v6v7 v2v8 v2v8 v3v7 v3v6 v4v5 ,v1v3 v2 v8 8 v7 7 v6 6 v5 5 V4 4 V3 3 v2 2 v1 1 0v2v3 v1v4v5 v1v6v7 v2v8 v2v8 v3v7 v3v6 v4v5 ,v1v3 ,v2