Question

一道数据结构题，这里是深度优先搜索过程中的(b)图，是怎么画出来的？求较为详细的解释，谢谢

Answer 1

你这个图实在是看不清楚啊，我重新标记了一下，简单给你回答一下吧。

深度优先搜索属于图算法的一种，核心是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次，简单地说就是，选定一个出发节点后一直往更深的节点走，没有路了就返回，再选择另一个节点继续遍历。

按照我重新标注的节点，深度搜索从a出发，先选择b，然后一路深入e、d、c，这时没有可选的了，原路返回到a；再选择 f，然后一路深入h、g，又没有可选的了，再返回到节点a；此时没有其他节点可选，遍历结束。

深度优选的访问顺序并不是唯一的，上面只是解释了一种，还可以有其他的顺序，例如：a->b->c->d->e（返回a），a->f->g->h（返回a）,结束。这个也是可以的。