关于图:算法图
图的基础知识图是一种十分重要的数据结构，用来示意物体与物体之间的关系。图由若干节点及节点之间的边组成。确定图中的节点和边是利用图相干算法解决问题的前提。通常，物体对应图中的节点，如果两个物体存在某种关系，那么它们在图中对应的节点有一条边相连。 图能够分为有向图和无向图。如果给图的每条边规定一个方向，那么这样的图就是有向图，它的边为有向边。有向边就像城市里的单向路，只能沿着一个方向后退。与之相同的是无向图，无向图中的边都没有方向，它的边称为无向边。 通常，图能够用邻接表或邻接矩阵示意。邻接表为图中的每个节点创立一个容器，第i个容器保留所有与第i个节点相邻的节点。 邻接表如果一个图中有n个节点，那么它的邻接矩阵M的大小是n×n。如果节点i和节点j之间有一条边，那么Mi等于1；反之，如果节点i和节点j之间没有边，那么Mi等于0。 邻接矩阵如果一个图是用邻接矩阵示意的，那么判断两个节点之间是否有边相连就非常简单，只须要判断矩阵中对应地位是1还是0即可，工夫复杂度为O（1）。但如果一个图中的节点数目十分大但比拟稠密（大部分节点之间没有边），那么邻接表的空间效率更高。 图还能够分为有权图和无权图。在有权图中，每条边都有一个数值权重，用来示意两个节点的某种关系，如两个节点的间隔等。在无权图中所有的边都没有权重。 图的搜寻在图中搜寻，如找出一条从起始节点到指标节点的门路或遍历所有节点，是与图相干的最重要的算法。依照搜寻程序不同能够将搜索算法分为广度优先搜寻和深度优先搜寻。 广度优先搜寻深度优先搜寻技巧广度优先搜寻和深度优先搜寻在算法面试中都是十分有用的工具，很多时候应用任意一种搜索算法就能解决某些与图相干的面试题。如果面试题要求在无权图中找出两个节点之间的最短距离，那么广度优先搜寻可能是更适合的算法。如果面试题要求找出符合条件的门路，那么深度优先搜寻可能是更适合的算法。 后面介绍了如何实现树的广度优先搜寻和深度优先搜寻。树也能够看成图。实际上，树是一类非凡的图，树中肯定不存在环。但图不一样，图中可能蕴含环。 防止死循环的方法是记录曾经搜寻过的节点，在拜访一个节点之前先判断该节点之前是否曾经拜访过，如果之前拜访过那么这次就略过不再反复拜访。 假如一个图有v个节点、e条边。不论是采纳广度优先搜寻还是深度优先搜寻，每个节点都只会拜访一次，并且会沿着每条边判断与某个节点相邻的节点是否曾经拜访过，因而工夫复杂度是O（v+e）。 最大的岛屿陆地岛屿地图能够用由0、1组成的二维数组示意，程度或竖直方向相连的一组1示意一个岛屿，请计算最大的岛屿的面积（即岛屿中1的数目）。例如，在图15.5中有4个岛屿，其中最大的岛屿的面积为5。 深度优先遍历/** * @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)