深度优先算法

定义

深度优先算法即深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。 当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。 这一过程一直进行到已发现从源节点可达的所有节点为止。

具体思想

当我们想使用通过深度优先搜索算法遍历一个图的时候，我们首先需要做以下几个步骤

1. 从最开始的节点A开始，获取与它相邻的节点B
2. 判断这个节点是否被访问过，如果访问过，那么就不再重复访问，如果没有则进行下一步
3. 已当前的节点B为当前节点，进行深度优先搜索算法
   3.1. 将当前节点的访问状态设为已访问
   3.2. 获取当前节点的下一个相邻节点C
   3.3. 判断相邻节点C是否是终止节点，如果是终止节点，那么算法结束
   3.4. 判断当前节点是否被访问过，如果没有被访问过，那么重复将访问状态设为已访问，如果访问过了，那么获取下一个相邻节点，然后重复3.1至3.4

广度优先算法

定义

广度优先算法即广度优先搜索算法（英语：Breadth-First-Search，缩写为BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。

具体思想

和深度优先的一条路走到黑不同，广度优先是遍历一个节点时，要遍历完它的所有子节点，具体思想如下

1. 从最开始的节点A开始，获取与它相邻的所有节点B，C等，如果元素没有被访问过就加入队列
2. 从队列获取之前加入的元素B作为当前元素，获取与它相邻的元素D，E等，如果元素是终点就结束，如果元素没有被访问过就加入队列
3. 重复步骤2直到找到终点

深度优先和广度优先的优劣

深度优先算法在计算时，只会考虑这个问题是否有解，并不会考虑这个这个解是否是最优解（即遍历出最短路径），而广度优先算法则可以获得问题的最优解（最短路径），但是在遍历时会保存一些数据信息，如果嵌套太深，那么就会占用较大内存，所以在选择算法时，需要根据实际问题来进行选择，而不能一概而论

（未完待续）