如何在广度优先搜索中选择起点？

Question

在我正在阅读的书中，它告诉我选择深度为0的顶点，但我不了解图形中深度的计算方式。

[看上面的例子，它选择顶点A作为起点，并解释说它的深度为0。在我的理解中，它的深度为0，因为它的度数为0（没有入射边）。

但是如果图形是无向的，我们如何计算其深度呢？

[如果我将其视为以A为根的树，在我看来，我将G指定为根，因此这次G的深度为0，因此成为起点。

我看过讲座，看过文章，但无法弄清楚如何在无向图中找到起点，对有向图来说，我的理解正确吗（0深度=> 0度）？

提前感谢。

Answer 1

不，您的理解不正确。因为没有for图的深度。在图中，我们使用起点，它由问题设定者给出。

图中没有深度。

让我们举一个例子：-您的例子中节点E的深度是多少？>

-如果我们遵循路径A-> B-> E

然后2

-如果我们遵循路径A-> C-> D-> E

然后3

如果在任何节点中都没有传入的边，并且您没有选择它，那么它就不会遍历。因此，您选择A作为起点（深度0）

并且在无向图中，您可以根据算法选择任何节点作为起始节点。

希望，现在您明白我在说什么。

而且我能够消除您的困惑。