在树的那一章节，提到过深度优先和广度优先的思想，具体用在一棵树的遍历上，前面写的前序、中序和后序都是深度优先遍历，而层次 遍历利用一个队列，来依次保存每一层的元素，是一种广度优先的思想。而在图中，深度优先搜索（后面简称DFS）和广度优先搜索（简称 BFS），是一种更加普遍用的算法，
图上的搜索方法，比如从顶点A出发，找出到另一个顶点B的所有路径，简单包暴力的有BFS和DFS，也有一些启发式算法比如A*、IDA* 等。前面也提到了图主要有邻接表和邻接矩阵两种方式来存储，邻接表更加常用，即针对每一个顶点我们都保存了一个和这个顶点相连的所有 顶点，图的代码实现如下：
public class Graph {
private int v; //顶点数目
private LinkedList<Integer> adj[]; //邻接表，每个顶点都有一个list，存储着它连接的顶点
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);
}
}
BFS的代码理解上不算很难，但是借助了几个辅助变量，主要用来标识某个顶点是否被访问过。以及一个 用来记录访问到哪一层的一个队列，还有一个数组记录访问的路径等，代码如下，配合着debug还是可以理解的。
public void bfs(int s, int t) {
List<String> result = new ArrayList<>();
if (s == t) return;
boolean[] visited = new boolean[v]; //标识某一个顶点是否已经被访问过，避免顶点重复访问
visited[s] = true;
Queue<Integer> queue = new LinkedList<>(); //存储已经被访问、但是相连的顶点还没有被访问的节点，因为广度优先搜索是逐层访问的，只有把第k层
//的顶点访问完以后，才能继续访问第k+1层的顶点，这个队列就是用来记录的，同样之前我们层次遍历以及求二叉树
//的高度时候，也用到了一个队列来记录每一层的节点
queue.add(s);
int[] prev = new int[v]; //记录访问的路径，prev[n]存储的是顶点n的前驱顶点，也就是从哪个顶点访问到了顶点n的
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 + " ");
}
DFS要用到回溯的思想，因为当你走到一条死路以后，需要回到上一步，重新选择一条路去尝试。深度优先 搜索找到的不一定是一条最短的路径，这个回溯的思想一般都使用递归来实现，DFS中也用到了标识某个顶点是否 被访问过的数组，一个记录路径的数组，当然不需要用队列了这次，代码如下：
public void dfs(int s, int t) {
found = false;
boolean[] visited = new boolean[v];
int[] prev = new int[v];
for (int i = 0; i < v; i++) {
prev[i] = -1;
}
recurDfs(s, t, visited, prev);
print(prev, s, t);
}
private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
if (found) return;
visited[w] = true;
if (w == t) {
found = true;
return;
}
for (int i = 0; i < adj[w].size(); i++) {
int q = adj[w].get(i);
if (!visited[q]) {
prev[q] = w;
recurDfs(q, t, visited, prev);
}
}
}
DFS和BFS的时间复杂度都是O(E)，E是图的边数目；空间复杂度都是O(V)，V是图的顶点数。