为什么此 DJ 图表中的两个特定节点之间没有指示 sp-back 边？

Question

我正在阅读 Sreedhar 等人的论文 Identifying Loops Using DJ Graphs。在本文中，他们在图的深度优先搜索顺序中提出了以下边缘分类（特别是 DJ 图，但区别对于这个问题来说并不是太重要）。

• sp-后边，如果 y = x 或 y 是生成树中 x 的祖先
• sp-树边，如果 x 是生成树中 y 的父节点
• sp-前向边缘，如果 x 是生成树中的祖先但不是 y 的父代
• sp-交叉边，如果x和y没有祖先-后代关系。

我在下面链接的论文中有一个关于图形的 DFS 排序的激励示例。

出于本问题的目的，我们可以忽略点线边缘和实线边缘之间的区别。

根据DFS编号，生成树为：

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> 8 -> 9
                         +--> 6

sp-back 边由源节点末端的气泡表示。所以，7->3、4->3、5->1 是 sp-back 边。

我的问题是：为什么 9->5 不被表示为 sp-back 边？ 它满足 sp-back 边的标准，即节点 5 是节点 9 的祖先（5->7-生成树中 >8->9）。

我已经编写了一些一次性代码来按照本文中规定的标准对边缘进行分类，它符合我的推理。我的代码将 9->5 分类为 sp-back 边缘。

非常欢迎任何指点。

Answer 1

文本并不清楚“y 是生成树中 x 的祖先”的含义。 在这种情况下，这并不意味着您在看到 x 之前先看到 y。 相反，它意味着您在搜索 y 的所有子节点的过程中找到了节点 x。

“5”之后，我们看“6”，“5”就完成了。 我们不调查“1”，因为我们已经去过那里了。 所以即使我们稍后访问“9”，我们也不会因为“5”而访问它。