当前位置:C++技术网 > 资讯 > 数据结构笔记分享:12 图的遍历深度优先搜索算法

数据结构笔记分享:12 图的遍历深度优先搜索算法

更新时间:2015-11-24 21:48:01浏览次数:1+次

从图G中某个顶点v出发,深度优先搜索图的DFS算法如下:

1)访问顶点v并打上标记。

2)依次从v的未访问过的邻接点出发,深度优先搜索图G.


    DFS在访问图中某一起始顶点v后,由v出发,访问它的任一邻接顶点w1;再从w1出发,访问与 w1邻接但还没有访问过的顶点w2;然后再从w2出发,进行类似的访问,… 如此进行下去,直至到达所有的邻接顶点都被访问过的顶点u为止。接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止



    对有向图G,从A出发DFS,访问的次序是A,B,D,C; 另选一个顶点出发搜索图G的其余部分;结果得到一个生成森林。