大门| 2017大门模拟II |问题20

请考虑以下陈述： S1: 有向图的DFS在遍历过程中总是产生相同数量的边，而与起始顶点无关。 S2： 如果删除了在有向图上进行DFS遍历时发现的所有后边缘，则生成的图是非循环的。

以下哪项陈述是有效的？

（A） S1和S2都有效 （B） 只有S1有效 （C） 只有S2有效 （D） s1和S2都无效 答复: （C） 说明： 语句S1：考虑图

从一个（源顶点）开始，我们将得到两条边 从B开始只能获得1个优势 从C开始，我们没有优势

因此，有向图上的DFS可能不会给出相同数量的边。

语句S2：后边是指将顶点u连接到图形中的祖先u的边（u，v） 深度优先树。自循环被认为是后边缘。后缘描述了从“高”节点到“低”节点的后代到祖先的关系。 假设有一个后缘（u，v）。那么顶点v是深度优先林中顶点u的祖先。因此，在G中有一条从v到u的路径，后缘（u，v）完成一个循环。移除后缘将打破循环。

因此，删除所有的后边缘将使图成为非循环的。所以这句话是真的。 这个问题的小测验