深度和广度优先究竟是什么？

我们收可以看下面这幅图，用深度和广度两种方法来遍历这个图形的点。

题目.png

使用深度优先搜索来遍历这个图的过程具体是：首先从一个未走到过得顶点作为起始顶点，比如以1号作为起点，沿1号顶点的边去尝试访问其它未走到过得顶点，首先发现2号顶点还没有走到过，于是来到2号顶点。再以2号顶点作为出发点继续尝试访问其它未走到过得顶点，这样又来到了4号顶点。再以4号顶点作为出发点继续尝试访问其它未走到过得顶点。但是，此时沿4号顶点的边，已经不能访问到其它未走到过得顶点了，所以需要返回2号顶点。返回到2号顶点后，发现沿2号顶点的边也不能在访问到其它未走到过得顶点。因此还需要继续返回到1号顶点。在继续沿1号顶点的边看看还能否访问到其它未走到过的顶点。此时又会来到3号顶点，再以3号顶点作为出发点继续访问其它未走到过的顶点，于是又来到5号顶点。到此，所有顶点都已经走到过了，遍历结束。如下图显示路径：

深度广义搜索.png

现在来总结一下深度优先搜索的主要思想就是：首先以一个未被访问过得顶点作为起始顶点，沿当前顶点的边走到未访问过得顶点；当没有未访问过的顶点时，则回到上一个顶点，继续试探访问别的顶点，直到所有顶点都被访问过。显然，深度优先遍历是沿着图的某一条分支遍历直到末端，然后回溯，再沿着另一条进行同样的遍历，直到所有的顶点都被访问过为止。

接下来就来说说广度优先搜索怎么来遍历这个图，首先以一个未被访问过得顶点作为起始顶点，比如以1号顶点作为起点。将1号顶点放入到队列中，然后将与1号顶点相邻的未被访问过的顶点即2号、3号和5号顶点依次再放入队列中。接下来再将2号顶点相邻的未访问过的顶点4号顶点4号放入到队列中。到此所有顶点都被访问过，遍历结束。

广度优先搜索.png

广度优先遍历的主要思想就是：首先以一个未被访问过的顶点作为起始顶点，访问其所有相邻的顶点，然后对每个相邻的顶点，再访问它们相邻的未被访问过的顶点，直到所有顶点都被访问过，遍历结束。

以上就深度优先和广度优先的主要思想。