深度优先搜索

Question

在从顶点a开始的图上执行深度优先搜索。当你遍历邻居时，按字母顺序处理它们。

问题是找到每个顶点的DFI，Level和父级。

这是它的一张图片：

​

​

我不确定如何继续，这是一个即将到来的考试的练习题。我知道对于深度优先搜索，它使用一个堆栈，它将从顶点a开始，并在堆栈中按字母顺序排列，但我不确定如何获得每一列的值。有没有人能进一步解释或帮助我？

Answer 1

所以你从'a‘开始，必须按字母顺序遍历节点，所以从a开始，你可以选择转到b或g，所以你选择b，因为它是按字母顺序排列的第一个。从b开始，你唯一的选择是g，以此类推。

现在来看看你的价值观。A的父节点为空，因为之前没有节点，所以b的父节点是a，g的父节点是b，依此类推。

dfs级别是它最终会出现在树上的级别。所以想象一下，你进行了遍历，然后删除了所有不属于遍历的行。然后你把你的根“摇出来”，我的意思是你重新排列它，让它看起来像一棵树。(这个特定的图表非常无趣)，然后您可以根据该树分配级别。

dfs索引只是您接触节点的顺序。

下面的是你的图表，但使用g作为起点……我认为这会让它更有趣一些。

​

这些数字是获取边的顺序。

​

​

这就是我所说的“摇出来”，这是你的树的样子，蓝色的我显示了每个节点的级别(从0开始)。我希望图片能让它变得更容易理解。

​

​

我画的那个(可怕的徒手画)是通过删除所有不使用的边，然后重新排列它们，使它们看起来像一棵树形成的。

你可以把深度想象成我从根到当前节点需要走多少步。所以从g到b是1步，所以从g到i的深度是1，因为我们从g->c->d->i ->3步开始。在完成遍历之后，您忽略了一个事实，即您实际上可以通过两个步骤(g->h->i)获得从g到i的结果，因为这不是遍历的一部分

Answer 2

索引仅仅是访问节点的顺序的编号。a是第一个，在那里写1。像你这样知道深度优先搜索，你应该知道第二个节点是什么；所以在它下面写2。深度是节点的高度；每加深一次，它就增加一次，每当你变浅的时候，它就减少一次。因此a位于深度1；下一个节点及其姊妹节点将位于深度2上，依此类推。父节点是标识您刚来自的节点的字母；因此a没有父节点，具有索引2的节点将具有a作为父节点。

如果您的类使用从零开始的编号系统，请将上面段落中的2替换为1，并将1替换为0。如果你不知道什么是“基于零的编号系统”，忽略这一段。