有向图属性/深度优先搜索

Question

据我所知，如果在某个任意有向图上存在从顶点 "a" 到顶点 "b" 的路径，则在某些情况下可能会使用深度优先搜索在图表上，顶点 "b" 可以在顶点 "a" 处理完成后在搜索中发现。但是，这对我来说似乎是不可能的（在绘制了许多图表之后）。有什么想法吗？

Answer 1

不，你的假设是错误的。不可能的。

使用归纳法很容易证明当顶点"a"的处理完成时，所有从"a"可达的顶点（例如"b"）已经被发现。

Answer 2

 (a) ---> (a1) ---->(b)
 |                   >
 |                   | 
 >                   |  
(a2)--------------->(a3)   

考虑这个图，顶点 (a) 有到顶点 (b) 的路径。

当我们运行从顶点(a)开始dfs时，输出为(a),(a1),(b),(a2),(a3)

顶点(b)在访问(a)之后被访问。