为何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
相关产品推荐
相关产品推荐

