DFS树木和DFS森林

Question

我从以下网站了解DfS树：

http://rosalind.info/glossary/algo-depth-first-search/

在“深度优先搜索有向图”一节中，如果我们添加一个节点Z，该节点没有指向它的边缘，而是从Z到C的一个边缘，那么Z在生成的DFS树中会出现在哪里？

它从Z到C的边是树边还是交叉边？

谢谢!

Answer 1

当您为给定的问题构建新的DFS树时，很明显：

1. 目前用于A到H的DFS树是相同的。Z不是它的一部分，因为它没有被任何边缘连接到Z。由于字典顺序在选择顶点时，它不会在A之前被选择。
2. 在访问A到H之后，Z不会被访问，而这些将按字典顺序被选择进行探索。它将是DFS森林中的一棵新树。请注意，在单向情况下，当忽略示例中所示的非树边缘时，这只是DFS林。
3. 术语说交叉边..。导致一个已经完全探索过的节点。Z有一个边到以前探索的C，那些它的边是一个十字边。

你应该自己检查一下这个答案。

Answer 2

树(或林)的外观以及边缘ZC的类型取决于DFS从何处运行，以及首先选择了哪些节点。如果DFS在访问C之前访问Z，那么ZC将是树的边缘，因为它是唯一的，Z将是具有多个节点的树的一部分。如果DFS从Z开始，那么将有一个以Z作为根节点的树。但是，如果只有在访问了C之后才发现Z，那么C也必须已经完成(完全探索)，因为任何其他节点都无法访问Z。因此，在这种情况下，ZC是一个交叉边，Z将在一棵树中本身。