深度优先搜索算法和广度优先搜索算法都是基于“图”这种数据结构。
图上的搜索算法就是，在图中找出从一个顶点出发，到另一个顶点的路径。图上的搜索算法有深度优先、广度优先搜索算法，和*A**、IDA* 等启发式搜索算法。
广度优先搜索和深度优先搜索是图上的两种最常用、最基本的搜索算法，仅适用于状态空间不大的搜索。它们比*A**、IDA* 等启发式搜索算法要简单粗暴，没有什么优化，所以也叫作暴力搜索算法。
广度优先搜索，采用地毯式层层推进，从起始顶点开始，依次往外遍历。广度优先搜索需要借助队列来实现，遍历得到的路径就是起始顶点到终止顶点的最短路径。
深度优先搜索，采用回溯思想，适合用递归或栈来实现。遍历得到的路径并不是最短路径。
深度优先和广度优先搜索的时间复杂度都是 O(E)，空间复杂度都是 O(V)。其中E代表边，O代表顶点。
下面java语言实现用邻接表来存储无向图：
public class Graph { // 无向图 private int v; // 顶点的个数 private LinkedList<Integer> adj[]; // 邻接表 public Graph(int v) { this.v = v; adj = new LinkedList[v]; for (int i=0; i<v; ++i) { adj[i] = new LinkedList<>(); } } public void addEdge(int s, int t) { // 无向图一条边存两次 adj[s].add(t); adj[t].add(s); }}
广度优先搜索（Breadth-First-Search），简称 BFS。它是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索：
1570497713857
下面的java代码实现基于上面Graph的定义：
bfs() 函数用于搜索一条从 s 到 t 的最短路径，其中 s 表示起始顶点，t 表示终止顶点。
visited是用来记录已经被访问的顶点，用来避免顶点被重复访问。如果顶点 q 被访问，那相应的 visited[q] 会被设置为 true。
queue是一个队列，用来存储已经被访问、但相连的顶点还没有被访问的顶点。
prev用来记录搜索路径。prev[w] 存储的是，顶点 w 是从哪个前驱顶点遍历过来的。比如，通过顶点 2 的邻接表访问到顶点 3，那 prev[3] 就等于 2。为了正向打印出路径需要递归地来打印。
public void bfs(int s, int t) { if (s == t) return; boolean[] visited = new boolean[v]; visited[s]=true; Queue<Integer> queue = new LinkedList<>(); queue.add(s); int[] prev = new int[v]; for (int i = 0; i < v; ++i) { prev[i] = -1; } while (queue.size() != 0) { int w = queue.poll(); for (int i = 0; i < adj[w].size(); ++i) { int q = adj[w].get(i); if (!visited[q]) { prev[q] = w; if (q == t) { print(prev, s, t); return; } visited[q] = true; queue.add(q); } } }}private void print(int[] prev, int s, int t) { // 递归打印 s->t 的路径 if (prev[t] != -1 && t != s) { print(prev, s, prev[t]); } System.out.print(t + " ");}