【算法解惑】DFS/BFS

和树的遍历类似，图的遍历也是从图中某点出发，然后按照某种方法对图中所有顶点进行访问，且仅访问一次。

但是图的遍历相对树而言要更为复杂。因为图中的任意顶点都可能与其他顶点相邻，所以在图的遍历中必须记录已被访问的顶点，避免重复访问。

根据搜索路径的不同，我们可以将遍历图的方法分为两种：广度优先搜索和深度优先搜索。

图的概念

无向图和有向图

顶点对(u，v)是无序的，即（u，v）和（v，u）是同一条边。常用一对圆括号表示。

顶点对<u,v>是有序的，它是指从顶点u到顶点 v的一条有向边。其中u是有向边的始点，v是有向边的终点。常用一对尖括号表示。

权和网

图的每条边上可能存在具有某种含义的数值，称该数值为该边上的权。而这种带权的图被称为网。

连通图和非连通图

• 连通图：在无向图G中，从顶点v到顶点v'有路径，则称v和v'是联通的。若图中任意两顶点v、v'∈V，v和v'之间均联通，则称G是连通图。上述两图均为连通图。
• 非连通图：若无向图G中，存在v和v'之间不连通，则称G是非连通图。

广度优先搜索（BFS）

可以参考图解
整体的思想就是用一个队列来保存当前的节点，当要访问该节点的临近节点时，出队该节点，并把相邻节点压入队列。有几点需要注意：

• 出队是先进的节点先出，所以先判断头节点的临近节点
• 判断临近关系时，和二叉树不一样，二叉树是单向从上至下，但如果是图，我们则需要开辟一块数组保存访问状态，因为我们的临近节点可能哪个方向都有，通过访问状态可以辅助我们跳过已访问的节点。

深度优先搜索（DFS）

可以参考图解
和广度优先搜索相比，DFS可以少一个队列来存数据，只需要一个记录状态的栈即可。我们选择一个根结点出发，对访问的节点在栈中置1，然后一直往下搜索，直到到某个节点，它没有相邻节点，或者他的相邻节点都被访问的时候，回溯到上一个节点在判断。直到所有节点被访问。

总结

像搜索最短路径这些的很显著是用广搜，因为广搜的特征就是一层一层往下搜的，保证当前搜到的都是最优解

• 深搜的实现近似于栈，
• 广搜则是操作了队列，边进队，边出队。

优缺点：

• BFS:对于解决最短或最少问题特别有效，而且寻找深度小，但缺点是内存耗费量大（需要开大量的数组单元用来存储状态）。
• DFS：对于解决遍历和求所有问题有效，对于问题搜索深度小的时候处理速度迅速，然而在深度很大的情况下效率不高