深度优先搜索和广度优先搜索都是图形搜索算法。有相似但有不同，在不同的地方也有使用。 我们一起讨论一下，以便比较。 一、深度优先搜索(depth-first search)，图算法的一种，是对图和树的遍历算法，英文缩写是DFS或Depth First Search。 深度优先搜索是图论中的经典算法。利用深度优先搜索算法，可以生成目标图对应的拓扑排序表，利用拓扑排序表可以方便地处理许多相关的图论问题，如最大路径问题。 使用通用堆数据结构来帮助实现DFS算法。 简而言之，这个过程就是尽可能地深入每个可能的分支路径，每个节点只能被访问一次。 基本步骤(1)对于下面的树，DFS方法从根节点1开始，其搜索节点顺序为1，2，3，4，5，6，7，8(假设左分支和右分支中优先选择左分支) (2)从堆栈中访问堆栈顶部的点；(3)找出与该点相邻且未遍历的点，标记后放入栈中，依次进行；(4)如果没有没有遍历过的相邻点，这个点会从栈中弹出，然后依次按照(3)进行；(5)直到遍历完整棵树，栈中所有元素都会弹出，最后栈为空，DFS遍历完成。 二、广度优先搜索广度优先搜索(也叫广度优先搜索，缩写为BFS，以下简称广度)是连通图的遍历算法。这个算法也是很多重要图算法的原型。 Dijkstra的单源最短路径算法和Prim的最小生成树算法都采用了类似宽度优先搜索的思想。 它的别名也叫BFS，属于一种盲搜索方法。其目的是系统地执行和检查图中的所有节点，以找到结果。 换句话说，它不考虑结果的可能位置，对整个图片进行彻底搜索，直到找到结果。 基本上，BFS从根节点开始，沿着树(图)的宽度遍历树(图)的节点 如果所有节点都被访问，则算法停止。 使用通用队列数据结构来帮助实现BFS算法。 基本步骤(1)给出一个连通图，如图，初始化全白(未访问)；(2)搜索起点V1(灰色)；(3) V1(黑色)已搜索，即V2、V3、V4(标灰色)将被搜索；(4)对V2、V3和V4重复上述操作；(5)直到终点V7沾灰，终点终止；(6)最短路径是V1、V4和V7。