数据结构中图的有向图深度优先搜索

图的深度优先搜索类似。但是对于有向图或有向图，我们可以找到一些类型的边。DFS算法形成一棵称为DFS树的树。有四种类型的边，称为 -

  • 树边 (T) - 存在于DFS树中的那些边

  • 前向边 (F) - 与一组树边平行。（从较小的DFS编号到较大的DFS编号，以及较大的DFS完成编号到较小的DFS完成编号）

  • 后向边 (B) - 从较大的DFS编号到较小的DFS编号，以及较小的DFS完成编号到较大的DFS完成编号。

  • 横向边 (C) - 较大的DFS编号到较小的DFS编号，以及较大的DFS完成编号到较小的DFS完成编号。

假设我们有一个如下所示的图 -

现在我们将以A作为初始顶点执行DFS，并输入DFS编号和DFS完成编号。因此，树将如下所示 -

所以DFS遍历是A、B、F、D、G、C、E

树边为 - T = {(A, B), (B, F), (F, D), (F, G), (A, C), (C, E)}

前向边为 - F = {(A, G)}

后向边为 - B = {(G, B)}

横向边为 -C = {(G, D)}

更新于: 2020年8月10日

549 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告