深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图.在深度优先搜索中,对于最新发现的节点,如果它还有以此为起点而未搜索的边,就沿此边继续搜索下去.当节点v的所有边都己被探寻过,搜索将回溯到发现节点v有那条边的始节点.这一过程一直进行到已发现从源节点可达的所有节点为止.如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被发现为止.
这种在搜索过程中,深度大的结点先进行扩展的算法,我们就称它为深度优先搜索法.英语称之为Depth-First-Search,简称为DFS法.
二、深度优先搜索法有两个显著特点
（1）对已产生的结点按深度排序存储,深度大的先得到扩展,即先产生它的子结点；
（2）深度大的结点是后产生的,但先得到扩展,即“后产生先扩展”.因此该算法应该用堆栈作为的主要数据结构存储产生的结点：先把产生的数入栈,然后产生栈顶（即深度最大的结点）的子结点.子结点产生完后,出栈（pop）再产生栈顶的子结点.
如果在搜索中把算法改为按结点的层次进行搜索,本层的结点没有搜索处理完时,不能对下层结点进行处理,即深度越小的结点越先得到扩展,也就是说先产生的结点先得以扩展处理,这种搜索算法称为广度优先搜索法.英语中用Breadth-First-Search表示,所以我们也把广度优先搜索法简称为BFS.
广度优先搜索基本算法：
1）从某个顶点出发开始访问,被访问的顶点作相应的标记,并输出访问顶点号；
2）从被访问的顶点出发,依次搜索与该顶点有边的关联的所有未被访问的邻接点,并作相应的标记.
3）再依次根据2）中所有被访问的邻接点,访问与这些邻接点相关的所有未被访问的邻接点,直到所有顶点被访问为止.