graph 题目type
status
date
slug
summary
tags
category
icon
password
Property
岛屿数量
题目：给一个由
'1'（陆地）和 '0'（水）组成的的二维网格，请计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，可以假设该网格的四条边均被水包围。示例：
可以将二维网格看成一个无向图，竖直或水平相邻的1之间有边相连。为了求出岛屿的数量，可以扫描整个二维网格。如果一个位置为1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的1都会被重新标记为0。最终岛屿的数量就是进行深度优先搜索的次数。
岛屿的最大面积
题目：给你一个大小为
m x n 的二进制矩阵 grid 。岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。岛屿的面积是岛上值为 1 的单元格的数目。计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。示例：
课程表
题目：
你这个学期必须选修
numCourses门课程，记为0到numCourses - 1 。在选修某些课程之前需要一些先修课程。 先修课程按数组
prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。请判断是否可能完成所有课程的学习？如果可以，返回
true ；否则，返回 false 。示例：
输入：3，[ [0,1] , [1,2] , [2,0] ]
总共有 3 门课程。学习课程 2 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。学习课程 1 之前，你需要先完成课程 2。这是不可能的。
仔细观察就发现，这个图是有向图，并且形成了一个环。（从n点出发，最终还能回到n点），所以返回false。那这个题目就变成了： 判断有向图，是否有环。 有返回false，没有返回true
课程表II
题目：
现在你总共有
numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
示例：
只有有向无环图才存在拓扑排序。每次寻找图中入度为0的节点，将其删除后再找下一批入度为0的节点，这样的顺序叫做拓扑序；
计算每门课的入度，找出所有入度为0的课程将它们放入队列中；
每个循环删除一个入度为0的课程，并将对应的后置课程的入度减1，若其中有入度变为0的后置课程，继续把它加入到队列中。