DFS详解

DFS算法详解-LeetCode相关题

首先我们来了解一下基础的DFS算法

DFS：深度优先搜索，从字面上我们可以理解，搜索是优先深度的，也就是说一条路走到底再试另一条。

void dfs(int src) {
    if (终止条件) {
        return;
    }
    for (int nex : graph[src]) {
        dfs(nex);
    }
}
/* 这是DFS基本模板 */

DFS一般用来解决以下几种问题:

1. 连通分量
2. 判断是否有环

我们先来看一道DFS的入门题(模板题)

---

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。 –LeetCode 200

我们理解几个概念：

• 岛屿 –被“0”包围的“1”块
• 连通分量 – 对于一个无向图而言，连通块的各个点之间可达，可以理解成一个岛，岛内的人为一个整体，岛与岛之间不相连

因此这题显然就是让我们求连通分量的个数，这是DFS的最简单应用，下面给出模板

class solution {
    public int numIslands(int[][] grid) {
        int res = 0;
        int m = grid.length, n = grid[0].length;
        boolean[][] vis = new boolean[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1 && !vis[i][j]) {
                    res++;
                    dfs(grid, vis, i, j);
                }
            }
        }
    }

    void dfs(int[][] grid, boolean[][] vis, int x, int y) {
        int m = grid.length, n = grid[0].length;
        
        // 不在grid范围内
        if (x < 0 || y < 0 || x >= m || y >= n) {
            return;
        }

        // 为海洋无法访问
        if (grid[x][y] == 0) {
            return;
        }

        // 已被访问
        if (vis[x][y]) {
            return;
        }
        vis[x][y] = true;

        for (int[] dir : dirs) {
            dfs(grid, vis, x + dir[0], y + dir[1]);
        }
    }

    static int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
}

很简单对吧，这里简单解释一下代码

• dirs: 代表着上下左右的方向
• 这里每次访问到一个1时进行DFS自然就将整个连通分量全遍历过(visit)， 因此这样计算出来的就是连通分量的数量

掌握这个模板之后，我们就可以应付很多基础的DFS题，比如求岛屿的面积、周长等

图论题中往往还会有另一种形式，像上述的题目已经将图帮我们建完了，因此

---

给你一个整数 n 。现有一个包含 n 个顶点的 无向 图，顶点按从 0 到 n - 1 编号。给你一个二维整数数组 edges 其中 edges[i] = [ai, bi] 表示顶点 ai 和 bi 之间存在一条 无向 边。

返回图中 完全连通分量 的数量。

如果在子图中任意两个顶点之间都存在路径，并且子图中没有任何一个顶点与子图外部的顶点共享边，则称其为 连通分量 。

如果连通分量中每对节点之间都存在一条边，则称其为 完全连通分量 。 – LeetCode 2685

这题没有直接给出网格图，因此首先我们需要自己建图，这里介绍一种我喜欢的建图方式

List<Integer>[] graph = new List[n];
Arrays.setAll(graph, i -> new ArrayList<>());
for (int[] edge : edges) {
    int x = edge[0];
    int y = edge[1];
    graph[x].add(y);
    graph[y].add(x);
}
/* 该是双向图的建图法，单向图需要注意边的方向*/

下面给出该题的解题思路和解法：
题目已经说明完全连通分量的概念，这里存在一个公式 e = v * (v - 1) / 2; 这是很显然的因为每个点之间都存在一条边,因此我们只需要通过dfs遍历得到连通分量判断是否是完全连通分量即可

class solution {
    public int countCompleteComponents(int n, int[][] edge) {
        // 套建图模板
        List<Integer>[] graph = new List[n];
        Arrays.setAll(graph, i -> new ArrayList<>());
        for (int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];
            graph[x].add(y);
            graph[y].add(x);
        }
        boolean[] vis = new boolean[n];
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (vis[i]) {
                continue;
            }
            e = 0, v = 0;
            dfs(graph, i, vis);
            if (e == v * (v - 1)) {
                res++;
            }
        }
        return res;
    }

    // 边
    int e;
    // 点
    int v;

    void dfs(List<Integer>[] graph, int cur, boolean[] vis) {
        if (vis[cur]) {
            return；
        }
        vis[cur] = true;
        v++;
        e += graph[cur].size();
        for (int nex : graph[cur]) {
            dfs(graph, nex, vis);
        }
    }

    /* 值得注意的是其实在我们的dfs函数中，每条边被算了两次*/
}

接下来再介绍两种用DFS判环的方法

/* Method 1*/
boolean dfs(List<Integer>[] graph, int cur, boolean[] vis, boolean[] path) {
    if (path[cur]) return true;
    if (vis[cur]) return false;
    vis[cur] = true;
    path[cur] = true;
    for (int nex : graph[cur]) {
        if(dfs(graph, nex, vis, path)) {
            return true;
        }
    }
    path[cur] = false;
    return false;
} 

/*Method 2*/
boolean dfs(List<Integer>[] graph, int cur, int fa, boolean[] vis) {
    if (vis[cur]) {
        return true;
    }
    vis[cur] = true;
    for (int nex : graph[cur]) {
        if (nex == fa) continue;
        if(dfs(graph, nex, cur, vis)){
            return true;
        }
    }
    return false;
}

/*Method 3*/
/*三色标记法*/
/*0 代表未访问 1代表正在访问 2代表已访问*/
boolean dfs(List<Integer> graph, int cur, int[] color) {
    if (color[cur] == 1) {
        return true;
    }
    if (color[cur] == 2) {
        return false;
    }
    color[cur] = 1;
    for (int nex : graph[cur]) {
        if(dfs(graph, cur, color)) {
            return false;
        }
    }
    color[cur] = 2;
}

核心思路就是DFS不能访问到仍在递归栈的数，比如1 -> 2 -> 3 -> 1, 这条DFS路线，当1往下递归时又遇到了自己这代表形成了环

---

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。 – *LeetCode 207

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<Integer>[] graph = new List[numCourses];
    Arrays.setAll(graph, i -> new ArrayList<>());
    for (int[] edge : prerequisites) {
        int x = edge[0];
        int y = edge[1];
        graph[x].add(y);
        /* 单向图 */
    }
    int[] color = new int[numCoureses];
    for (int i = 0; i < numCoureses; ++i) {
        if (color[i] == 2) continue;
        if (dfs(graph, i, color)) {
            /* 存在环不能完成课程 */
            return false;
        }
    }
    return false;
}

boolean dfs(List<Integer>[] graph, int cur, int[] color) {
    if (color[cur] == 1) {
        return true;
    }
    if (color[cur] == 2) {
        return false;
    }
    color[cur] = 1;
    for (int nex : graph[cur]) {
        if(dfs(graph, nex, color)) {
            return true;
        }
    }
    return false;
}