---

DFS

DFS即深度优先搜索，在图论中是一种用于遍历或搜索树或图的算法。其核心思想是尽可能深地搜索树的分支，当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。

一、DFS遍历模板

使用递归实现DFS是最直观的方法。递归函数会访问当前节点，然后递归地访问其未被访问的相邻节点。
递归三部曲：1.确定递归函数 2.确认终止条件 3.处理目前搜索节点出发的路径

public 函数类型 dfs(int node,boolean[] visited,int[][] graph){
        if (终止条件) {
            存放结果;
            return;
            }
        visited[node]=true;
        for(int next:graph[node]){//访问相邻节点
            if(!visited[next]){
                dfs(next,visited,graph);//递归
            }
        }

二、DFS模板应用

1.省份数量(Leetcode547)

思路：省份数量即连通块，本题采用DFS或者并查集均可，采用DFS的话，即依次遍历相邻节点直至连通块的节点全部访问完，最后连通块的数量即省份数量。

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n=isConnected.length;
        boolean[] visited=new boolean[n];
        int res=0;
        for(int i=0;i<n;i++){
            if(visited[i]){
                continue;
            }
            dfs(i,isConnected,visited);//未访问的节点经过dfs后必是一个连通块
            res+=1;
        }
        return res;
    }
    public void dfs(int i,int[][] isConnected,boolean[] visited){//套用模板
        //这里不需要终止条件
        int n=isConnected.length;
        visited[i]=true;//访问节点
        for(int j=0;j<n;j++){
            if(isConnected[i][j]==1 && !visited[j]){//相邻且未被访问，继续深搜
                dfs(j,isConnected,visited);
            }
        }
    }
}

2.寻找图中是否存在路径(Leetcode1971)

思路：source到destination是否存在路径即souce能否搜索到destination，采用DFS搜索

class Solution {
    private List<List<Integer>> adj;
    private boolean[] visit;
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        adj=new ArrayList<>(n);
        for(int i=0;i<n;i++){
            adj.add(new ArrayList<>());
        }
        for(int[] edge:edges){
            int x=edge[0];
            int y=edge[1];
            adj.get(x).add(y);
            adj.get(y).add(x);
        }
        visit=new boolean[n];
        return dfs(source,destination);
    }
    public boolean dfs(int source,int destination){//套用模板
        //需要终止条件
        if(source==destination){//起点等于终点
            return true;
        }
        visit[source]=true;//访问过
        for(int next:adj.get(source)){
            if(!visit[next] && dfs(next,destination)){
                return true;
            }
        }
        return false;
    }
}

BFS

广度优先搜索（BFS）是一种用于遍历或搜索树或图的算法。它从根节点开始，逐层访问所有相邻节点，直到找到目标节点或遍历完整个图。BFS通常使用队列来实现，确保按照层次顺序访问节点。

一、BFS遍历模板

1.选择一个起始节点，将其标记为已访问，并将其加入队列。
2.从队列中取出一个节点，访问其所有未访问的相邻节点，并将这些节点标记为已访问后加入队列。
3.重复上述过程，直到队列为空。

public 函数类型 bfs(List<List<Integer>> g,int start){
        boolean[] visit=new boolean[n];//设置是否访问过
        Queue<Integer> q=new LinkedList<>();
        q.add(start);//先将初始节点入队
        while(!q.isEmpty()){
        //注意，这里如果涉及到遍历层级就需要另外每次获取队列的大小，再去遍历
            int size=q.size();
            for(int i=0;i<size;i++){
                int cur=q.poll();//出队
                for(int f:g.get(cur){//遍历相邻节点
                    if(!visit[f]){
                        visit[f]=true;//设置访问过
                        q.add(f);//入队
                    }
                }
            }
        }
    }

一、BFS模板应用

1.新增道路道路查询后的最短距离1（Leetcode1568）

思路：题目本质是每次加入一条新建的单向道路后起点到终点的最短距离是多少，很简单，写个bfs模板，然后每次都更新就可以了。

class Solution {
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        List<List<Integer>> g=new ArrayList<>();
        for(int i=0;i<n;i++){
            g.add(new ArrayList<>());
        }
        for(int i=0;i<n-1;i++){
            g.get(i).add(i+1);
        }
        int[] ans=new int[queries.length];
        for(int i=0;i<queries.length;i++){
            g.get(queries[i][0]).add(queries[i][1]);
            ans[i]=bfs(g,n);
        }
        return ans;
    }
    public int bfs(List<List<Integer>> g,int n){
        int[] dist=new int[n];
        for(int i=1;i<n;i++){//初始化到0的距离
            dist[i]=-1;
        }
        Queue<Integer> q=new LinkedList<>();
        q.add(0);
        while(!q.isEmpty()){//模板
            int x=q.poll();
            for(int y:g.get(x)){
                if(dist[y]>=0){
                    continue;
                }
                q.add(y);
                dist[y]=dist[x]+1;
            }
        }
        return dist[n-1];
    }
}

2.获取你好友已观看的视频（Leetcode1311）

题意：本题就是一道很直观的bfs，根据相邻朋友找到对应观看的视频，题目还多了个按照频次排序，另外加两段代码即可。

class Solution {
    public List<String> watchedVideosByFriends(List<List<String>> watchedVideos, int[][] friends, int id, int level) {
        int n=friends.length;
        boolean[] visit=new boolean[n];
        Queue<Integer> q=new LinkedList<>();
        visit[id]=true;
        q.add(id);//bfs模板
        while(!q.isEmpty() && level>0){
            level-=1;
            int size=q.size();
            for(int i=0;i<size;i++){
                int cur=q.poll();
                for(int f:friends[cur]){
                    if(!visit[f]){
                        visit[f]=true;
                        q.add(f);
                    }
                }
            }
        }
        HashMap<String,Integer> res=new HashMap<>();
        while(!q.isEmpty()){//统计频次
            int x=q.poll();
            List<String> list=watchedVideos.get(x);
            for(String y:list){
                res.put(y,res.getOrDefault(y,0)+1);
            }
        }
        List<String> ans=new ArrayList<>(res.keySet());
        Collections.sort(ans,(a,b)->{//自定义按照频次排序
            int cnt1=res.get(a),cnt2=res.get(b);
            if(cnt1!=cnt2){
                return cnt1-cnt2;
            }else{
                return a.compareTo(b);
            }
        });
        return ans;
    }
}