据我所知，如果在某个任意有向图上存在从顶点“a”到顶点“b”的路径，则可能存在某种情况，即使用图形上的深度优先搜索，该顶点“b”可以在顶点“a”完成处理后的搜索中发现 . 但是，这对我来说似乎不可能（在绘制出许多图表之后） . 有任何想法吗？
不，你的假设是错的 . 是不可能的 .
使用归纳证明相当容易，当完成顶点“a”的处理时，已经发现了从“a”（例如“b”）可到达的所有顶点 .
(a) ---> (a1) ---->(b) | > | | > | (a2)--------------->(a3)
考虑这个图，顶点（a）有到顶点（b）的路径 .
当我们从顶点（a）开始运行dfs时，输出是（a），（a1），（b），（a2），（a3）
访问（a）后访问顶点（b） .
2 回答
不，你的假设是错的 . 是不可能的 .
使用归纳证明相当容易，当完成顶点“a”的处理时，已经发现了从“a”（例如“b”）可到达的所有顶点 .
考虑这个图，顶点（a）有到顶点（b）的路径 .
当我们从顶点（a）开始运行dfs时，输出是（a），（a1），（b），（a2），（a3）
访问（a）后访问顶点（b） .