深度优先&广度优先

在社交网络中，通过用户之间的连接关系，可以实现推荐“可能认识的人”的功能。

“搜索”算法

大部分涉及搜索的场景都可以抽象成图，深度优先算法和广度优先算法都是基于图这种表达能力很强的数据结构。
在图中找出从一个顶点出发，到另一个顶点的路径。简单暴力的深度优先、广度优先；启发式的A、IDA。

图

//无向图
public class Graph {
    //顶点的个数
    private int v;
    //邻接表（声明一个存储LinkedList链表类型的数组）
    //保存每个顶点的邻接链表
    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);
    }
}

广度优先BFS

类似二叉树按层遍历。

广度优先搜索Breadth-First-Search，是一种地毯式层层推进的搜索策略，先查找离起始顶点最近的，然后是次近的，依次往外搜索。

广度优先搜索-借助队列实现

public void bfs(int s, int t) {
    if(s == t) 
        return;
    //记录已经被访问的顶点，避免顶点被重复访问，布尔值默认为false
    boolean[] visited = new boolean[v];
    visited[s] = true;
    //存储已经被访问，但是相连的顶点还没有被访问的顶点
    Queue<Integer> queue = new LinkedList<>();
    queue.add(s);
    //记录搜索路径（路径最大为v,找到t就可以直接返回）
    int[] prev = new int[v];
    for(int i = 0; i < v; i++) {
        prev[i] = -1;//-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);
            }
        }
    }
}
//递归打印s->t的路径
private void print(int[] prev, int s, int t) {
    if(prev[t] != -1 && t != s) {
        print(prev,s,prev[t]);
    }
    System.out.print(t + " ");
}

visited记录已经被访问的顶点，避免顶点被重读访问。
如果顶点q被访问，那相应的visited[q]会被设置为true。

queue用队列存储已经被访问、但相连的顶点还没有被访问的顶点。
只有把k层的顶点都访问完成之后，才能访问第k+1层的顶点。当访问到第k层的顶点时，需要把第k层的顶点记录下来，稍后才能通过第k层的顶点来找第k+1层的顶点。

prev记录搜索路径。
从顶点s开始，广度优先搜索到顶点t后，prev数组中存储的就是搜索的路径。
路径是反向存储的。prev[w]存储的是，顶点w是从哪个前驱顶点遍历过来的。需要递归来打印出正向的路径。

最坏情况下，终止顶点t离起始顶点s很远，需要遍历完整个图才能找到。每个顶点都要进出一遍队列，每个边都会被访问依次，广度优选搜索的时间复杂度是O(V+E)，V表示顶点的个数，E表示边的个数。
对一个连通图来说，图中的所有顶点都是连通的，E>=V-1，广度优先搜索的时间复杂度简化为O(E)。
广度优先搜索的空间消耗主要在几个辅助变量visited数组、queue队列、prev数组上。存储空间的大小都不会超过顶点的个数，整体空间复杂度为O(V)。

深度优先DFS

类似二叉树前序遍历。

深度优先搜索Depth-First-Search，使用回溯思想，解决问题的过程适合用递归来实现。

深度优先搜索-借助栈实现

//全局变量，当找到终止顶点之后，不再递归地继续查找
boolean found = false;
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 == true)
        return;
    //标记当前顶点为已访问
    visited[w] = true;
    if(w == t) {
        found = true;
        return;
    }
    //遍历当前顶点的邻接顶点
    for(int i = 0; i < adj[w].size(); i++) {
        if(found == true)
            return;
        int q = adj[w].get(i);
        //只递归未被访问的顶点
        if(!visited[q]) {
            //将当前顶点记录在当前邻接顶点的访问路径
            prev[q] = w;
            //递归当前邻接顶点
            recurDfs(q,r,visited,prev);
        }
    }
}

prev和visited中元素下标与元素值一致。prev[]

每条边最多会被访问两次，一次是遍历，一次是回退，深度优先搜索算法的时间复杂度是O(E)，E表示边的个数。

深度优先搜索算法的内存消耗主要是visited、prev数组和递归调用栈。vixited、prev数组的大小跟顶点的个数V成正比，递归调用栈的最大深度不会超过顶点的个数，整体空间复杂度是O(V)。