【算法】图

图的基础知识

图是一种非常重要的数据结构,用来表示物体与物体之间的关系。图由若干节点及节点之间的边组成。确定图中的节点和边是应用图相关算法解决问题的前提。通常,物体对应图中的节点,如果两个物体存在某种关系,那么它们在图中对应的节点有一条边相连。

图可以分为有向图和无向图。如果给图的每条边规定一个方向,那么这样的图就是有向图,它的边为有向边。有向边就像城市里的单向路,只能沿着一个方向前进。与之相反的是无向图,无向图中的边都没有方向,它的边称为无向边。

通常,图可以用邻接表或邻接矩阵表示。邻接表为图中的每个节点创建一个容器,第i个容器保存所有与第i个节点相邻的节点。

【算法】图_第1张图片

邻接表

如果一个图中有n个节点,那么它的邻接矩阵M的大小是n×n。如果节点i和节点j之间有一条边,那么Mi等于1;反之,如果节点i和节点j之间没有边,那么Mi等于0。

【算法】图_第2张图片

邻接矩阵

如果一个图是用邻接矩阵表示的,那么判断两个节点之间是否有边相连就非常简单,只需要判断矩阵中对应位置是1还是0即可,时间复杂度为O(1)。但如果一个图中的节点数目非常大但比较稀疏(大部分节点之间没有边),那么邻接表的空间效率更高。

图还可以分为有权图和无权图。在有权图中,每条边都有一个数值权重,用来表示两个节点的某种关系,如两个节点的距离等。在无权图中所有的边都没有权重。

图的搜索

在图中搜索,如找出一条从起始节点到目标节点的路径或遍历所有节点,是与图相关的最重要的算法。按照搜索顺序不同可以将搜索算法分为广度优先搜索和深度优先搜索。

  • 广度优先搜索
  • 深度优先搜索

技巧

广度优先搜索和深度优先搜索在算法面试中都是非常有用的工具,很多时候使用任意一种搜索算法就能解决某些与图相关的面试题。如果面试题要求在无权图中找出两个节点之间的最短距离,那么广度优先搜索可能是更合适的算法。如果面试题要求找出符合条件的路径,那么深度优先搜索可能是更合适的算法。

前面介绍了如何实现树的广度优先搜索和深度优先搜索。树也可以看成图。实际上,树是一类特殊的图,树中一定不存在环。但图不一样,图中可能包含环。

避免死循环的办法是记录已经搜索过的节点,在访问一个节点之前先判断该节点之前是否已经访问过,如果之前访问过那么这次就略过不再重复访问。

假设一个图有v个节点、e条边。不管是采用广度优先搜索还是深度优先搜索,每个节点都只会访问一次,并且会沿着每条边判断与某个节点相邻的节点是否已经访问过,因此时间复杂度是O(v+e)。

  1. 最大的岛屿
海洋岛屿地图可以用由0、1组成的二维数组表示,水平或竖直方向相连的一组1表示一个岛屿,请计算最大的岛屿的面积(即岛屿中1的数目)。例如,在图15.5中有4个岛屿,其中最大的岛屿的面积为5。

【算法】图_第3张图片

  • 深度优先遍历
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
    const rows = grid.length;
    const cols = grid[0].length
    let visited  =  new Array(rows).fill().map(() =>new Array(cols).fill(0));

    let maxArea = 0;
    for(let i = 0; i < rows; i++) {
        for(let j = 0;  j < cols; j++) {
            if(grid[i][j] == 1 && !visited[i][j]) {
                const area = getArea(grid, visited, i, j)
                maxArea = Math.max(maxArea, area)
            }
        }
    }
    return maxArea;

};

var getArea = function(grid, visited, i, j) {

    let area = 1;
    visited[i][j] = true;
    let dirs = [
        [-1, 0],
        [1, 0],
        [0, -1],
        [0, 1]
    ]
    for(const dir of dirs) {
        const r = i + dir[0];
        const c = j + dir[1];
        if(r>=0 && r < grid.length && c>=0 && c < grid[0].length && grid[r][c] === 1 && !visited[r][c]) {
            area += getArea(grid, visited, r, c)
        }
    }
    return area;
};
  • 广度优先遍历

拓扑排序(TODO)

并查集(TODO)

你可能感兴趣的