vlambda博客
学习文章列表

前言

这是系列文章【 Java 面试八股文 】数据结构与算法篇的第四期。

【 Java 面试八股文 】系列会陆续更新 Java 面试中的高频问题，旨在从问题出发，带你理解 Java 基础，数据结构与算法，数据库，常用框架等。该系列前几期文章可以通过下方给出的链接进行查看～

往期文章

深度优先遍历与广度优先遍历

1、图论与图

什么是图

图论（ graph theory ），是组合数学分支，和其他数学分支，如群论、矩阵论、拓扑学有着密切关系。图是图论的主要研究对象。图是由若干给定的顶点( Vertex )及连接两顶点的边( Edge )所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。

图可以分为四大类：

1. 无向无权图

   

2. 有向无权图

   

3. 无向有权图

   

4. 有向有权图

   

图的基本概念

1. 有向完全图

   有向完全图是指，有向图中有 个顶点，有 条边，即：图中的每个顶点和其余 个顶点都相连。

   

2. 无向完全图

   无向完全图是指，无向图中有 个顶点，有 条边，即：图中的每个顶点和其余 个顶点都相连。

   

3. 子图

   设有两个图 G = (V,{E})和 G' = (V',{E'})，若满足 且 ，则称图 G' 为 G 的子图。

   示例：

   

4. 邻接点

   如果顶点 和顶点 存在一条边，则称顶点 和顶点 互为邻接点。

5. 路径和环

• 路径：从顶点 到 顶点 的连续线段序列
• 路径长度：顶点序列上经过的边的个数
• 环：路径起点和路径终点相同

6. 自环边与平行边

   自环边是指，若一条边的两个顶点相同（即顶点自己指向自己），就将该边称为自环边；平行边是指从一个顶点连接到另一个顶点的多余边。

   

7. 联通图与联通分量

   对于图中的两个顶点 和 ，有路径，则称 和 联通。如果图中任意两个顶点都是联通的，则称该图为联通图。那么什么是联通分量呢？联通分量是指无向图中的极大联通子图。

   对于上面的图中，存在两个联通分量。

8. 度

   对于无向图，顶点 的度是指和顶点 相连的边的个数。

   对于有向图，顶点 的度分为出度和入度两部分；顶点 被箭头指向的个数就是它的入度，从顶点 指出去的箭头个数就是它的出度。

9. 生成树

   树是一种特殊的图，当一棵树包含联通图的所有顶点，且这棵树的边为该图的边的子集时，我们就称该树是这个联通图的生成树。

   假设联通图有 个顶点，那么，联通图的生成树的边的个数为 个。

图的基本表示

邻接矩阵

我们可以使用邻接矩阵的方式来表示一个图。

而我们在做图论相关的算法题时，一个图的信息往往是这么给定的：

7 9
0 1
0 3
1 2
1 6
2 3
2 5
3 4
4 5
5 6

第一行，7 代表图有 7 个顶点，9 代表图中有 9 条边；第一行后面每一行的信息均表示顶点 v 和顶点 w 相邻。

邻接表

使用邻接矩阵来表示一个图会耗费大量的存储空间，其空间复杂度为 。

试想一下，如果一个图是稀疏图，假设图中包含 3000 个节点，仅仅有 10 条边，我们就需要使用 3000 的平方大小的空间去存储及表示图，并且求解一个顶点的相邻节点的算法也需要遍历所有的顶点，毫无疑问，这是低效的。

我们通过举例分析了邻接矩阵这种图的表示方法带来的问题，对于边的数量相对于顶点数量很少的稀疏图，邻接矩阵会极大浪费存储空间。

除了邻接矩阵这种表示方法之外，图还有另外一种表示方法：邻接表。

邻接表对每一个顶点都使用一个链表存储，每个链表存储与该顶点相邻的顶点：

使用邻接表的话，有多少个顶点，就需要使用多少个链表，每个链表存储相邻节点。在简单图中（不考虑平行边和自环边），每个边计算了两次，所以邻接表存储的空间复杂度为 ，省略掉常数项，空间复杂度为 。这样一来，就可以解决邻接矩阵带来的空间浪费问题。

如果大家熟悉 Java 语言中，HashMap 的底层原理，就很快地可以想到，我们可以使用红黑树来替换线性的链表结构，来进一步提升邻接表的性能。

2、图的深度优先遍历

图的遍历整体可以分为两大类：深度优先遍历与广度优先遍历。

我们知道，树结构的遍历也分为深度优先与广度优先。我们可以认为树是一种“不存在任何回路的图”。

而图则存在回路，如果使用树的深度优先遍历的方式来遍历一个图，那么因为回路，就会导致产生重复遍历。

所以，在对图进行遍历时，我们需要记录，哪个节点被遍历过。

从树的深度优先遍历到图的深度优先遍历

拿树的前序遍历来说，树的前序遍历代码如下：

preorder(root);

preorder(TreeNode node){
    if(node != null) {
     list.add(node.val);
        preorder(node.left);
        preorder(node.right);
    }
}

而图的深度优先遍历伪代码如下：

visited[0...V-1] = false;
dfs(0);
dfs(int v){
    visited[v] = true;
    list.add(v);
    for(int w : adj(v))
        if(!visited[w])
            dfs(w);
}

我们会声明一个数组，记录哪个节点已经被遍历过，在逻辑上与树的深度优先遍历其实并没有本质上的不同，只是我们访问了一个节点，就要在声明的数组中，将访问的节点标记为已访问的状态，这是通过设置 visited[v] 是 true 或 false 来实现的。

接下来，我们就来看一下，对于如下这个图来说，深度优先遍历的过程是怎样的?

我们从 dfs(0) 开始：

<<< 左右滑动见更多 >>>

深度优先遍历的具体实现

代码如下：

visited[0...V] = false;

for(int v = 0; v < V; v++)
    if(!visited[v])
        dfs(v);

dfs(int v) {
 visited[v] = true;
    list.add(v);
    for(int w : adj(v))
        if(!visited[w])
            dfs(w);
}

上面的代码是图的深度优先遍历的前序遍历；和树的遍历相同，图也有深度优先遍历的后序遍历：

visited[0...V] = false;

for(int v = 0; v < V; v++)
    if(!visited[v])
        dfs(v);

dfs(int v) {
 visited[v] = true;
    for(int w : adj(v))
        if(!visited[w])
            dfs(w);
    list.add(v);
}

如果使用非递归的方式来实现图的深度优先遍历，我们则可以使用栈这种数据结构：

visited[0...V] = false;

for(int v = 0; v < V; v++)
    if(!visited[v])
        dfs(v);

dfs(int v) {
 Stack<Integer> stack = new Stack<>();
    stack.push(v);
    visited[v] = true;
    while (!stack.isEmpty()) {
        int cur = stack.pop();
        list.add(cur);
        for (int w : G.adj(cur)) {
            if (!visited[w]) {
                stack.push(w);
                visited[w] = true;
            }
        }
    }
}

图的深度优先遍历的应用

岛屿数量

题目链接🔗：https://leetcode-cn.com/problems/number-of-islands/

题目给定了我们一个由 1 和 0 组成的二维网格，其中 1 代表陆地，0 代表水，要求我们计算网格中岛屿的数量。

我们可以使用 FloodFill 算法来求解该问题。

什么是 FloodFill 算法呢？FloodFill 算法是从一个区域中提取若干个联通的点与其他相邻区域区分开（或类似于染色）的经典算法。因为其思路类似于洪水从一个区域扩散到所有能到达的区域而得名。FloodFill 这个名字看起来高大上，不过其本质就是 DFS/BFS。

题目给定的二维数组 grid 就是一个图，我们将 grid 直接看作是一个图，并且在 grid 这张“图”上进行 DFS，使用一个二维数组 visited 用来记录每一个点是否被遍历过。

Java 代码如下：DFS

class Solution {
    private int r,c;
    private boolean[][] visited;
    private char[][] grid;
    private int[][] dirs = {{-1,0},{0,1},{1,0},{0,-1}};

    public int numIslands(char[][] grid) {
        r = grid.length;
        c = grid[0].length;
        visited = new boolean[r][c];
        this.grid = grid;

        int res = 0;
        for(int x = 0; x < r; x++){
            for(int y = 0; y < c; y++){
                if(!visited[x][y] && grid[x][y] == '1'){
                    res++;
                    dfs(x,y);
                }
            }
        }
        return res;
    }

    private void dfs(int x,int y){
        visited[x][y] = true;

        for(int d = 0; d < 4; d++){
            int nextX = x + dirs[d][0];
            int nextY = y + dirs[d][1];
            if(isValid(nextX,nextY) && grid[nextX][nextY] == '1' && !visited[nextX][nextY])
                dfs(nextX,nextY);
        }
    }

    private boolean isValid(int x,int y){
        return x >= 0 && x < r && y >= 0 && y < c;
    }
}

复杂度分析：

• 时间复杂度： 我们需要遍历整个二维数组 grid， 和 分别表示二维数组的行数和列数，所以时间复杂度为
• 空间复杂度： 我们申请了一个额外的辅助数组 visited，并且 DFS 的递归深度最大可以达到 ，所以额外空间复杂度为

判断二分图

题目链接🔗：https://leetcode-cn.com/problems/is-graph-bipartite/

什么是二分图呢？二分图又称作为二部图，是图论中一种特殊的模型，其具有以下的特性：

• 顶点 可以分成不相交的两部分
• 所有的边的两个端点隶属不同的部分

像上面的这个图，就是一个二分图。

那么，如何检测一个图是否是二分图呢？

二分图检测这个问题的核心就是在 DFS（深度优先遍历）的过程中进行“染色操作”。我们再来回顾一下二分图的特性，其中有一条为 “所有的边的两个端点隶属不同的部分”，我们可以在 DFS 遍历的过程中，对顶点进行“染色”，具体的染色步骤为：我们使用一个数组 colors 用来表示每个节点的颜色，colors 数组中只有两种数字，一个是 0，一个是 1 。0 和 1 分别代表两种不同的颜色。我们在 DFS 的过程中，对每一个顶点进行染色，如果满足二分图的“所有的边的两个端点隶属不同的部分”这个特性，那么相邻的两个节点必然为两种不同的颜色。遍历结束后，如果符合这一特性，说明该图就是一个二分图。

Java 代码如下：

DFS

class Solution {
    
    private int[][] graph;
    private boolean[] visited;
    private int[] colors;
    
    public boolean isBipartite(int[][] graph) {
        this.graph = graph;
        visited = new boolean[graph.length];
        colors = new int[graph.length];
        for(int i = 0; i < graph.length; i++)
            colors[i] = -1;
        
        for(int v = 0; v < graph.length; v++)
            if(!visited[v])
                if(!dfs(v,0))
                    return false;
        
        return true;
    }
    
    private boolean dfs(int v,int color){
        visited[v] = true;
        colors[v] = color;
        
        for(int w : graph[v])
            if(!visited[w]){
                if(!dfs(w,1 - color))
                    return false;
            }else if(colors[w] == colors[v]){
                return false;
            }
        
        return true;
    }
}

复杂度分析：

• 时间复杂度：

  DFS 的时间复杂度为 ，其中 代表图的顶点个数， 代表图的边数。

• 空间复杂度：

  我们的算法中，额外开辟了 colors 数组，和 visited 数组，并且，递归需要使用栈的额外空间，又占用了 的空间大小，所以 DFS 算法的额外空间复杂度为 ， 代表图的顶点个数。

3、图的广度优先遍历

从树的广度优先遍历到图的广度优先遍历

对于一棵树来说，广度优先遍历是使用一个队列来实现的：

其实图的广度优先遍历和树的优先遍历的本质是一样的，只不过，和 DFS 一样，图的广度优先遍历也需要记录哪个节点被遍历过。

我们来看一下图的广度优先遍历的具体过程。

对于上面这样一个图，我们使用一个辅助的队列，其遍历过程如下所示：

<<< 左右滑动见更多 >>>

广度优先遍历的具体实现

结合上面的分析过程，我们可以使用队列这种数据结构写出 BFS（广度优先遍历）的代码实现，这里我给出伪代码提供大家参考：

图的广度优先遍历的应用

岛屿数量

题目链接🔗：https://leetcode-cn.com/problems/number-of-islands/

仍然是该问题，我们这次使用 BFS 进行求解。

代码思路如下：

1. 遍历矩阵，当遇到 grid[i][j] == '1' 时，便从这个点开始做 BFS，并使岛屿数量加一
2. 创建一个辅助队列，判断队首元素是否没有越界且为 1；如果是则将该点置为零，并将该点的上下左右相邻点加入到队列中，如果不是则跳过该点
3. 循环出队首节点，直至队列为空，结束循环

Java 代码如下：BFS

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1'){
                    bfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    private void bfs(char[][] grid, int i, int j){
        Queue<int[]> list = new LinkedList<>();
        list.add(new int[] { i, j });
        while(!list.isEmpty()){
            int[] cur = list.remove();
            i = cur[0]; j = cur[1];
            if(0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1') {
                grid[i][j] = '0';
                list.add(new int[] { i + 1, j });
                list.add(new int[] { i - 1, j });
                list.add(new int[] { i, j + 1 });
                list.add(new int[] { i, j - 1 });
            }
        }
    }
}

复杂度分析：

• 时间复杂度： 我们需要遍历整个二维数组 grid， 和 分别表示二维数组的行数和列数，所以时间复杂度为
• 空间复杂度： 我们申请了一个额外的辅助队列，该队列最大需要拥有的存储的空间为 ，所以额外空间复杂度为

判断二分图

题目链接🔗：https://leetcode-cn.com/problems/is-graph-bipartite/

回顾 DFS 的解决方法，我们的核心是在 DFS 过程中对每个节点进行染色操作。

BFS 也是一样的，我们只需要在 BFS 遍历的过程中，对顶点进行“染色”操作，如果染色后，满足二分图的“所有的边的两个端点隶属不同的部分”这个特性，就说明该图是一个二分图。

Java 代码如下：BFS

class Solution {
    
    private int[][] graph;
    private boolean[] visited;
    private int[] colors;
    
    public boolean isBipartite(int[][] graph) {
        this.graph = graph;
        this.visited = new boolean[graph.length];
        this.colors = new int[graph.length];
        for(int i = 0; i < colors.length; i++)
            colors[i] = -1;
        
        for(int v = 0; v < graph.length; v++)
            if(!visited[v])
                if(!bfs(v))
                    return false;
        
        return true;
    }
    
    private boolean bfs(int v){
        Queue<Integer> q = new LinkedList<>();
        visited[v] = true;
        colors[v] = 0;
        q.offer(v);
        
        while(!q.isEmpty()){
            v = q.poll();
            
            for(int w : graph[v])
                if(!visited[w]){
                    visited[w] = true;
                    colors[w] = 1 - colors[v];
                    q.offer(w);
                }else if(colors[w] == colors[v]){
                    return false;
                }   
            
        }
        return true;
    }
}

复杂度分析：

• 时间复杂度：

  BFS 的时间复杂度为  ，其中 代表图的顶点个数， 代表图的边数。

• 空间复杂度：

  我们的算法中，额外开辟了 colors 数组，和 visited 数组，并且，BFS 额外使用了一个队列。队列又占用了 的空间大小，所以 BFS 算法的额外空间复杂度为 ， 代表图的顶点个数。

总结

在今天的文章中，我向大家介绍了图的基本概念与深度优先遍历以及广度优先遍历。

当我们将 DFS 转换为非递归写法时，我们发现 DFS 和 BFS 的本质其实就是 DFS 使用了栈这种数据结构，而 BFS 使用了队列这种数据结构。

也就是说，DFS 和 BFS 的本质或思想实际上是相同的，他们的不同只是在于选择的“容器”的不同，从而导致了逻辑上的不同。

好啦，至此为止，这篇文章就到这里了，Java 面试八股文系列后面依旧会继续更新并查缺补漏，感谢您的阅读与支持～～