You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

为何DJ图中节点9→5未被标记为sp-back edge?

关于《Identifying Loops Using DJ Graphs》中DFS边分类的疑问

我正在阅读Sreedhar等人的论文《Identifying Loops Using DJ Graphs》,该论文针对DJ图的深度优先搜索(DFS)排序定义了以下边分类规则:

  • sp-back edge:若y=x,或y是生成树中x的祖先
  • sp-tree edge:若x是生成树中y的父节点
  • sp-forward edge:若x是生成树中y的祖先但非父节点
  • sp-cross edge:若x和y无祖先-后代关系

论文给出的DFS生成树示例如下:

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

示例中sp-back edge的源节点会用气泡标记,已标记的边包括7->3、4->3、5->1。但按照规则,边9→5应该属于sp-back edge(5是生成树中9的祖先,路径为5->7->8->9),却没有被标记。我参照论文规则编写的代码也将9→5归类为sp-back edge,想请教这一矛盾的原因。

补充说明:我采用了通过比较DFS起始时间和结束时间来判断祖先关系的逻辑。


内容的提问来源于stack exchange,提问作者Etten Moor

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.06.17 10:52:09