图2：图的搜索（遍历）
图的表达能力很强，图的搜索算法在实际生产中有巨大的用出，不论是游戏寻路，地图导航，路径规划等等方向都有普遍应用。我们生活中很多场景都可以抽象为图结构，这使得图算法一直是一个重点，难点也是热点。
为了更好的实现搜索，定义接口如下：
package cn.lishiyuan.algorithm.graph;
import java.util.List;
/**
* 图的遍历（搜索）
* @param <V>
*/
public interface GraphSearch<V> {
/**
* 从from到to的路径，包含节点from 和 to，empty表示无法从from到to
* @param from
* @param to
* @return
*/
List<V> search(V from, V to);
}广度优先搜索
广度优先搜索（Breadth-First-Search），我们平常都简称 BFS。它的策略是先检查全部的邻接节点是否是目标节点，再检查邻接节点的邻接节点是否是目标节点，依次类推，层层递进查找目标节点，如果查找到则构建返回。BFS算法获取到的路径是最短路径。
[[图1：图的表示与存储]]中，邻接表的搜索方法并未实现，这里使用广度优先搜索补全实现：
package cn.lishiyuan.algorithm.graph;
import cn.lishiyuan.algorithm.queue.LeeQueue;
import cn.lishiyuan.algorithm.queue.LinkedQueue;
import java.util.*;
/**
* 邻接表
*/
public class AdjacencyList<V> implements Graph<V> {
// 顶点
private Set<V> vertices;
// 边
private Map<V,Map<V,Integer>> edges;
private GraphType type;
/// 省略其他方法
@Override
public List<V> search(V from, V to) {
return bfs(from,to);
}
// 广度优先搜索
private List<V> bfs(V from, V to){
if(Objects.equals(from,to)){
return Collections.singletonList(to);
}
// 队列存储待处理的顶点
LeeQueue<V> queue = new LinkedQueue<>();
queue.enqueue(from);
// 已经访问过的顶点
Set<V> visited = new HashSet<>();
visited.add(from);
// 节点的前向顶点
Map<V,V> prev = new HashMap<>();
// 如果队列不为空，则遍历查找
while (!queue.isEmpty()){
V node = queue.dequeue();
// 与边相连的节点
Map<V, Integer> edgeInfo = edges.getOrDefault(node,new HashMap<>());
for (V v : edgeInfo.keySet()){
if (!visited.contains(v)){
// 存储前向节点
prev.put(v,node);
// 已找到，返回数据
if(v.equals(to)){
// 已找到
List<V> result = new ArrayList<>();
result.add(v);
V prevV = prev.get(v);
while (prevV != null){
result.add(prevV);
prevV = prev.get(prevV);
}
Collections.reverse(result);
return result;
}
// 将节点加入对列尾部
queue.enqueue(v);
// 标记为已处理
visited.add(v);
}
}
}
//
return Collections.emptyList();
}
}
这里使用到了线性表2：栈和队列实现的队列用来模拟遍历过程，由于队列的先进先出特性，使得我们在查找过程中，可以先遍历当前顶点的邻接节点，所有的领接节点遍历完成后才会接着遍历邻接顶点的邻接顶点。
用Set存储已访问的顶点，保证了不会在成环的时候进入死循环，一直循环遍历。
使用Map存储节点的前向节点，当我们查找到目标节点的时候，通过它来回溯，可以复原搜索路径。
时间复杂度与空间复杂度
时间复杂度是O(v+e)，v是顶点数量，e是边数量。极端情况是没有路径，遍历所有的边和节点。
空间复杂度是O(v)，v是顶点数量。这里使用到的额外的queue、set和map都是一个和顶点数量相关的数据结构。
深度优先搜索
深度优先搜索（Depth-First-Search），简称 DFS。策略是如果遍历邻接节点，如果邻接节点存在邻接顶点，则先遍历邻接节点的邻接节点，依此类推，先将一条路走到黑，如果没查找到节点再回退，如果查找到了则构建返回。
[[图1：图的表示与存储]]中，邻接矩阵的搜索方法并未实现，这里使用深度度优先搜索补全实现：
package cn.lishiyuan.algorithm.graph;
import cn.lishiyuan.algorithm.stack.LeeStack;
import cn.lishiyuan.algorithm.stack.LinkedStack;
import java.util.*;
/**
* 邻接矩阵
*
*/public class AdjacencyMatrix<V> implements Graph<V>{
/**
* 顶点,可以使用 Map 存储元素与index的关系
*/
private V[] vertices;
/**
* 边
*/
private int[][] edges;
private GraphType type;
/// 省略其他方法
@Override
public List<V> search(V from, V to) {
if(Objects.isNull(from) || Objects.isNull(to)){
throw new IllegalArgumentException("顶点不能为空");
}
int fromIndex = indexOfVertex(from);
int toIndex = indexOfVertex(to);
if (fromIndex == -1 || toIndex == -1){
throw new IllegalArgumentException("顶点不存在");
}
if(Objects.equals(from,to)){
return Collections.singletonList(from);
}
return dfs(fromIndex, toIndex);
}
/**
* 深度优先搜索
* @param from
* @param to
*/
private List<V> dfs(int from, int to){
if(from == to){
return Collections.singletonList(vertices[to]);
}
// 用栈模拟
LeeStack<Integer> stack = new LinkedStack<>();
stack.push(from);
// 已访问的节点
boolean[] visited = new boolean[vertices.length];
Arrays.fill(visited, false);
visited[from] = true;
// 前向节点
int[] prev = new int[vertices.length];
Arrays.fill(prev, -1);
while (!stack.isEmpty()){
int vertex = stack.pop();
for (int i=0;i<vertices.length;i++){
// 存在边且未经过
if(edges[vertex][i] > 0 && !visited[i]){
visited[i] = true;
stack.push(i);
prev[i]= vertex;
// 已找到节点
if(i == to){
int p = prev[i];
List<V> result = new ArrayList<>();
result.add(vertices[i]);
while (p!=-1){
// 已找到
result.add(vertices[p]);
p = prev[p];
}
Collections.reverse(result);
return result;
}
}
}
}
return Collections.emptyList();
}
private int indexOfVertex(V v){
for(int i=0;i<vertices.length;i++){
if(v.equals(vertices[i])){
return i;
}
}
return -1;
}
}
这里使用到了线性表2：栈和队列中栈的实现来模拟遍历过程。由于栈的先进后出特性，在遍历节点有邻接节点的时候会优先取出这些邻接顶点进行查找，所有的该节点邻接节点查找完成，才会查找该节点的兄弟节点。
使用一个Boolean数组存储已经访问过的节点，保证成环的时候不会进入死循环。
使用int数组存储顶点的前向顶点，用来回溯查找路径。
时间复杂度和空间复杂度
时间复杂度是O(v^2)，v是顶点数量，stack长度最大为v，顶点的的边不管存不存在都遍历一遍，长度也是v。
空间复杂度是O(v)，v是顶点数量，栈、boolean数组和int数组都是一个和顶点数量相关的额外空间。