在说两种算法之前先说说什么叫“搜索”：
可能很多人对搜索的想法有点不对，很多人认为搜索是对已知的一棵树或者是已知的图进行搜索，所以我们常常把搜索和遍历给搞混了，但是其实搜索针对的并不是已知的，这并不代表搜索不能用于已知的，搜索一般用于未知的树，或者未知的图，而我们仅仅是知道这个树或图的产生规则。这个时候才会产生深度优先搜索和广度优先搜索。

然后说一下深度优先搜索和广度优先搜索的区别以及适用范围：
广度优先搜索：广度优先搜索是按照树的层次进行的搜索，如果此层没有搜索完成的情况下不会进行下一层的搜索。
深度优先搜索：深度优先搜索是按照树的深度进行搜索的，所以又叫纵向搜索，在每一层只扩展一个节点，直到为树的规定深度或叶子节点为止。这个便称为深度优先搜索。
我先来说说两种算法的不同点。广度优先搜索，适用于所有情况下的搜索，但是深度优先搜索不一定能适用于所有情况下的搜索。因为由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝（即深度无限），则不可能找到目标节点。所以，深度优先搜索策略是不完备的。

适用范围：这点很重要，因为知道两者的适用范围对于编程人员很有好处，至少可以少走弯路。（这些都是开个人观点，有缺少的欢迎补充）
广度优先搜索适用范围：在未知树深度情况下，用这种算法很保险和安全。在树体系相对小不庞大的时候，广度优先也会更好些。

深度优先搜索适用范围：刚才说了深度优先搜索又自己的缺陷，但是并不代表深度优先搜索没有自己的价值。在树深度已知情况下，并且树体系相当庞大时，深度优先搜索往往会比广度优先搜索优秀，因为比如8*8的马踏棋盘中，如果用广度搜索，必须要记录所有节点的信息，这个存储量一般电脑是达不到的。然而如果用深度优先搜索的时候却能在一个棋盘被判定出来后释放之前的节点内存。

当让具体情况还是根据具体的实际问题而定，并没有哪种绝对的好。所以，理解这两种算法的本质是关键。
最后我说说关于找最优解的问题，这种问题如果不依靠其他的辅助算法来说，其实对于广度优先搜索和深度优先搜索来说是一样的，说白了找最优解就是个遍历过程，所以没有哪种算法找最优解更好。但是如果有辅助的启发式算法或者别的算法就另当别论了。

深度优先算法

和树的遍历相似，若从图中某顶点出发访遍图中每个顶点，且每个顶点仅访问一次，此过程称为图的遍历(Traversing Graph)。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。图的遍历顺序有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。对每种搜索顺序，访问各顶点的顺序也不是唯一的。

1、邻接表及逆邻接表的存储方法

（1）定义

邻接表是图的一种链式存储结构。类似于树的孩子链表表示法。在邻接表中为图中每个顶点建立一个单链表，用单链表中的一个结点表示依附于该顶点的一条边（或表示以该顶点为弧尾的一条弧），称为边（或弧）结点。特征如下：

1) 为每个顶点建立一个单链表，

2) 第i个单链表中包含顶点Vi的所有邻接顶点。

把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做表结点（边结点），邻接点域adjvex保存与该边相关联的另一顶点的顶点下标 ， 链域nextarc存放指向同一链表中下一个表结点的指针 ，数据域info存放边的权。边链表的表头指针存放在头结点中。头结点以顺序结构存储，其数据域data存放顶点信息，链域firstarc指向链表中第一个顶点。

带权图的边结点中info保存该边上的权值。

顶点 Vi 的边链表的头结点存放在下标为 i 的顶点数组中。

在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。

设图中有 n 个顶点，e 条边，则用邻接表表示无向图时，需要 n 个顶点结点，2e 个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需 n 个顶点结点，e 个边结点。

建立邻接表的时间复杂度为O(n*e)。若顶点信息即为顶点的下标，则时间复杂度为O(n+e)。

2、深度优先算法思想

深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先搜索递归调用包含以下操作：

（1）访问搜索到的未被访问的邻接点；
（2）将此顶点的visited数组元素值置1；
（3）搜索该顶点的未被访问的邻接点，若该邻接点存在，则从此邻接点开始进行同样的访问和搜索。

深度优先搜索DFS可描述为：

（1）访问v0顶点；
（2）置 visited[v0]=1；
（3）搜索v0未被访问的邻接点w，若存在邻接点w，则DFS(w)。

遍历过程：     


 DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻 接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。

接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。如下图所示：

广度优先算法

1、  队列

（1）       定义
    队列也是一种运算受限的线性表。在这种线性表上，插入限定在表的某一端进行，删除限定在表的另一端进行。允许插入的一端称为队尾，允许删除的一端称为队头。

    特点：队列中数据元素的入队和出队过程是按照“先进先出” 的原则进行的。因此，队列又称为“先进先出”的线性表，简称FIFO表。

（2）       实现－链队列

队列的链式存储结构简称为链队。它实际上是一个同时带有首指针和尾指针的单链表。头指针指向表头结点，而尾指针则指向队尾元素。从队尾插入，从队首删除。空的链队对列的判决条件是头指针和尾指针均指向头结点。

2、  广度优先搜索的算法思想

广度优先搜索遍历类似于树的按层次遍历。

    对于无向连通图，广度优先搜索是从图的某个顶点v0出发，在访问v0之后，依次搜索访问v0的各个未被访问过的邻接点w1，w2，…。然后顺序搜索访问w1的各未被访问过的邻接点，w2的各未被访问过的邻接点，…。即从v0开始，由近至远，按层次依次访问与v0有路径相通且路径长度分别为1，2，…的顶点，直至连通图中所有顶点都被访问一次。

广度优先搜索的顺序不是唯一的。

具体描述如下：

设图G的初态是所有顶点均未访问，在G 中任选一顶点i作为初始点，则广度优先搜索的基本思想是：

（1）从图中的某个顶点V出发，访问之；并将其访问标志置为已被访问，即visited[i]=1；

（2）依次访问顶点V的各个未被访问过的邻接 点，将V的全部邻接点都访问到；

（3）分别从这些邻接点出发，依次访问它们的未被访问过的邻接点，并使“先被访问的顶 点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有已被访问过的顶 点的邻接点都被访问到。

依此类推，直到图中所有顶点都被访问完为止 。

广度优先搜索在搜索访问一层时，需要记住已被访问的顶点，以便在访问下层顶点时，从已被访问的顶点出发搜索访问其邻接点。所以在广度优先搜索中需要设置一个队列Queue，使已被访问的顶点顺序由队尾进入队列。在搜索访问下层顶点时，先从队首取出一个已被访问的上层顶点，再从该顶点出发搜索访问它的各个邻接点。


如下图（c）中为对图（a）的遍历：