depth-first-search - 有向图问题的不可能 DFS

Question

考虑以下有向图。对于给定的 n，图的顶点对应于整数 1 到 n。如果 i 除以 j，则从顶点 i 到顶点 j 有一条有向边。绘制 n = 12 的图。对上图执行 n = 12 的 DFS。根据你的 DFS 记录每个顶点的发现和完成时间，并将图的所有边分类为树、后、前和交叉边缘。您可以选择任何起始顶点（顶点）和访问顶点的任何顺序。

由于包含的规定，我看不出如何遍历该图。不可能得到后沿，因为将较小的数字除以较大的数字不会产生整数并且永远不会有效。

假设我们按照这个逻辑并使用给定的指令创建一个有向图。顶点 1 能够到达顶点 2，因为 2 / 1 是一个整数。但是，不可能到达顶点 3，因为顶点 2 只能到达顶点 4、6、8 或 10。由于您不能除以更大的数字，因此一旦取其中之一，就永远不可能访问较低的顶点路径，因此无法到达顶点 3。

标签： depth-first-searchdirected-graph

Answer 1

您对回溯的假设是正确的。你不能有回溯，因为你没有任何圈子。考虑以下示例：

当我们开始时，我们2会发现边2->4、4->8、4->12和。边和是前边，它们就像前进得更快的捷径。边缘是交叉边缘，因为您正在从一个分支切换到另一个分支。而且由于我们没有圆圈可以以某种方式返回到前一个节点，因此我们没有任何后向边。2->62->102->82->126->12