133. 克隆图
需要对无向图进行遍历，可以通过深度优先搜索实现（递归/栈迭代），也可以通过广度优先搜索实现（队列迭代），与二叉树的遍历不同的是，需要使用HashMap存储已访问过的节点，避免陷入死循环。
210. 课程表 II
有向图的拓扑排序。拓扑排序是一个序列，图中任意一条有向边a->b，a在该序列中都排在b的前面。有环图不存在拓扑排序；拓扑排序可能不止一种。
拓扑排序的具体实现同样存在深度优先搜索与广度优先搜索两种思路：
深度优先搜索：
- 对一个节点而言，深度优先搜索的过程会使其在所有的出边节点都遍历结束后才入栈，因此从栈顶到栈底的顺序就是拓扑排序。注意，该栈只起记录拓扑排序结果的作用，不对确定迭代顺序有帮助，因此如果不想用递归想用迭代法还需要额外维护一个栈用来确定遍历顺序。
- 由于在迭代中需要知道有向边的情况，用List
- 为了防止有环时深度优先出现死循环，要用一个数组记录每个节点的三种状态（未搜索，搜索中，已完成），搜索所有未搜索的节点，对其连接的节点进行递归遍历，如果遍历到的节点在搜索中，则说明图中有环，return；如果遍历到的节点为未搜索，继续递归遍历。
广度优先搜索：
- 采用顺序确定拓扑排序的方法，将所有没有入边的节点加入队列，从前向后提出节点进行遍历，对每个遍历的节点的连接节点，取消他们的有向边，如果取消有向边后的连接节点入度为0，则将其加入队列，可以保证每次加入队列的节点都已经没有依赖的前驱节点了，因此队列的顺序就是拓扑排序。注意，该队列即是记录拓扑排序结果，也是确定遍历顺序的依据，即便不需要写出拓扑排序也不能省。
- 由于在迭代中需要知道有向边的情况，用List
- 要用一个数据子路每个节点的入度（入边的数量）
417. 太平洋大西洋水流问题
一个二维矩阵，上左边缘是P，下右边缘是A，需要判断哪些土地上如果有水是可以既流进P，也能流进A。
采用逆向思维，让两边的水倒流，分别用两个矩阵存储哪些陆地是可以被P倒流，被A倒流的，最后取交集。矩阵只是表现形式，本质上是一个网状的图，图的遍历用深度优先。注意，存储了是否能倒流的结果信息的二维矩阵，其实就包含了该节点是否已访问的信息，在遍历递归函数中根据其值进行判断，防止死循环发生。
200. 岛屿数量
一个二维矩阵，由01组成，1代表陆地，边缘视为水，求连通岛屿的数量。
思路一：深度优先搜索
对每个点为起点进行搜索，所有能搜索到的都是连通的，因此总搜索次数为岛屿的数量。对于深度优先遍历的死循环陷阱， 417. 太平洋大西洋水流问题 采用结果矩阵存储了是否访问过的信息。该题与之不同，采用改写已访问节点值的方式避免死循环，如果题目要求不允许修改原数组，则需要另创建一个标记矩阵。
思路二：并查集
并查集的核心思想是，当两拨人相遇，问他们分别的老大是谁，如果相同则是一伙儿的。类中，需要变量：count, rank[], parent[]。其中rank[] 存储父节点的级别，在合并时遵循低级别认高级别为父的原则。需要方法：find() 递归查找节点的老大； union() 合并两节点。
对每个陆地，让其和相邻的陆地进行union() ；同样需要改写矩阵防止死循环。
若有收获，就点个赞吧
0 人点赞
