1. 矩阵或图上的DFS

200. 岛屿数量

from collections import deque

class Solution:
    # #        x-1,y
    # # x,y-1    x,y      x,y+1
    # #        x+1,y
    # # 方向数组，它表示了相对于当前位置的 4 个方向的横、纵坐标的偏移量，这是在图上进行DFS和BFS的常见技巧
    directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]    
     

    ### DFS 时间：O(mn) 空间最坏：O(mn)整个图全为1
    def numIslands(self, grid: List[List[str]]) -> int:
        m=len(grid)
        if m==0: ###边界条件判断，必须放在n之前, 因为m=0时grid[0]就不存在，n就会报错
            return 0        
        n=len(grid[0])
        marked=[[False]*n for _ in range(m)] #标记数组，初始化为所有点最开始都未被访问过
        count=0 #统计一共有几个点可以进行一次完整的DFS就有有几个岛屿
        ## 从第 1 行、第 1 格开始，对每一格尝试进行一次 DFS 操作
        for i in range(m):
            for j in range(n):
                if not marked[i][j] and grid[i][j]=='1': #要想进行DFS需要是 未被标记过的’1‘ ，每进入DFS的’1‘会影响grid中之后点的marked，所以整个grid中可能只有n个’1‘可以进行DFS(也就有n个岛屿)
                    self.dfs(i, j, m, n, marked, grid) #####self.  ，这里只有传入的marked数组List需要进行修改
                    count+=1
        return count
    def dfs(self, i, j, m, n, marked, grid):
        marked[i][j]=True #每个进入DFS的点都要首先被标记访问过了
        ### 注意：这里没有注明nonlocal就可以直接改变marked, 是因为marked是数组List而List是可变的对象， 但若要修改int，string就必须要首先声明unlocal
        for d in self.directions: ###########注意是 self.directions，因为directions是在类里面定义的，每个位置有四种选择
            new_i=i+d[0]
            new_j=j+d[1]
            if 0<= new_i <m and 0<= new_j <n and not marked[new_i][new_j] and grid[new_i][new_j]=='1': #???????????之前写成grid[i][j]=='1'也能通过不知道怎么回事
                self.dfs(new_i, new_j, m, n, marked, grid) #这样递归使每次都可以沿一个方向一直找下去



    
    ### BFS  时间：O(mn) 空间最坏：O(min(m,n))整个图全为1
    def numIslands(self, grid: List[List[str]]) -> int:
        m=len(grid)
        if m==0:
            return 0
        n=len(grid[0])
        marked=[[False]*n for i in range(m)]
        count=0
        for i in range(m):
            for j in range(n):
                if not marked[i][j] and grid[i][j]=='1': #能进入这个if就说明该点可以进行一次BFS（就是一个岛屿）
                    next_queue=[(i,j)]#以该点为起始点进行BFS，
                    marked[i][j]=True #并且该点首先被标记访问过了
                    while next_queue:
                        now_i, now_j=next_queue.pop(0)
                        for d in self.directions:
                            new_i=now_i+d[0]
                            new_j=now_j+d[1]
                            if 0<= new_i <m and 0<= new_j <n and not marked[new_i][new_j] and grid[new_i][new_j]=='1':
                                next_queue.append((new_i,new_j))
                                marked[new_i][new_j]=True              
                    count+=1
        return count
        
    ### BFS详解
    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        # 特判
        if m == 0:
            return 0
        n = len(grid[0])
        marked = [[False for _ in range(n)] for _ in range(m)]
        count = 0
        # 从第 1 行、第 1 格开始，对每一格尝试进行一次 BFS 操作
        for i in range(m):
            for j in range(n):
                # 只要是陆地，且没有被访问过的，就可以使用 BFS 发现与之相连的陆地，并进行标记
                if not marked[i][j] and grid[i][j] == '1':
                    # count 可以理解为连通分量，你可以在广度优先遍历完成以后，再计数，
                    # 即这行代码放在【位置 1】也是可以的
                    count += 1
                    queue = deque()   ################### from collections import deque
                    queue.append((i, j))
                    # 注意：这里要标记上已经访问过
                    marked[i][j] = True
                    while queue:
                        cur_x, cur_y = queue.popleft()
                        # 得到 4 个方向的坐标
                        for direction in self.directions:
                            new_i = cur_x + direction[0]
                            new_j = cur_y + direction[1]
                            # 如果不越界、没有被访问过、并且还要是陆地，我就继续放入队列，放入队列的同时，要记得标记已经访问过
                            if 0 <= new_i < m and 0 <= new_j < n and not marked[new_i][new_j] and grid[new_i][new_j] == '1':
                                queue.append((new_i, new_j))
                                #【特别注意】在放入队列以后，要马上标记成已经访问过，语义也是十分清楚的：反正只要进入了队列，你迟早都会遍历到它
                                # 而不是在出队列的时候再标记
                                #【特别注意】如果是出队列的时候再标记，会造成很多重复的结点进入队列，造成重复的操作，这句话如果你没有写对地方，代码会严重超时的
                                marked[new_i][new_j] = True
                    #【位置 1】
        return count

130. 被围绕的区域

class Solution:
    ### DFS : 从图的四个边界处（四条边）值为 ”O“ 的地方出发，找到所有与它们联通的”O“并替换成”*“，
    #之后图中剩下没有被替换的”0“就是中间被”X“包围的，将它们替换成”X“， 之前已经替换成”*"的再换成“O”即可
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board:
            return 
        m,n = len(board),len(board[0])
        directions=[(-1,0),(0,1),(1,0),(0,-1)]
        def dfs(i,j):
            if 0<= i <m and 0<= j <n and board[i][j]=='O': #满足该条件才可以进行DFS
                board[i][j]='*' #原地替换
                for d in directions:
                    dfs(i+d[0], j+d[1])

        for i in range(m): #在左右两列边界进行DFS
            dfs(i,0)
            dfs(i,n-1)
        for j in range(n): #在上下两行边界进行DFS
            dfs(0,j)
            dfs(m-1,j)

        # for i, j in zip(range(m), range(n)): ### m和n的大小不一定一样（图不一定是方阵），所以这样写不行
        #     dfs(i,0)
        #     dfs(i,n-1)
        #     dfs(0,j)
        #     dfs(m-1,j)        
 
        for i in range(m):
            for j in range(n):
                if board[i][j]=='*': #把与边界处“o"联通的”o“恢复成”o“
                    board[i][j]='O'
                elif board[i][j]=='O': ###这里只能是elif不能是if, 否则上面刚修改的”O“在这里又会被改成”X“
                    board[i][j]='X'

695. 岛屿的最大面积

class Solution:
    ### DFS
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        directions=[(-1,0),(0,1),(1,0),(0,-1)]
        m,n = len(grid), len(grid[0])
        marked=[[False]*n for _ in range(m)]

        def dfs(i,j):
            nonlocal count #要想在内层函数里面改变外层函数中的不可变的Int类型, 必须要先声明nonlocal
            # count+=1
            marked[i][j]=True
            for d in directions:
                new_i, new_j = i+d[0], j+d[1]
                if 0<= new_i <m and 0<= new_j <n and not marked[new_i][new_j] and grid[new_i][new_j]==1:
                    count+=1 #只要能满足进行dfs的条件就是一片不重复的陆地
                    dfs(new_i, new_j)
        
        max_count=0
        for i in range(m):
            for j in range(n):
                if not marked[i][j] and grid[i][j]==1:
                    count=1  #（0+1）只要能满足进行dfs的条件就是一片不重复的陆地
                    dfs(i,j)
                    max_count=max(max_count,count)
        return max_count


    ### BFS
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        if not grid:
            return 0
        directions=[(-1,0),(0,1),(1,0),(0,-1)]
        m,n = len(grid), len(grid[0])
        marked=[[False]*n for _ in range(m)]

        max_count=0
        for i in range(m):
            for j in range(n):
                if not marked[i][j] and grid[i][j]==1:
                    count=1
                    queue=[(i,j)]
                    marked[i][j]=True

                    while queue:
                        now=queue.pop(0)
                        for d in directions:
                            new_i, new_j = now[0]+d[0], now[1]+d[1]
                            if 0<= new_i <m and 0<= new_j <n and not marked[new_i][new_j] and grid[new_i][new_j]==1:
                                count+=1
                                queue.append((new_i, new_j))
                                marked[new_i][new_j]=True
                    max_count=max(max_count, count)
        
        return max_count

463. 岛屿的周长

class Solution:
    ### 不管用DFS还是BFS都把这题整复杂了，
    # 因为题目中已经明确指出图中 ”肯定有且只有一块联通的岛屿（意思是所有的 1 默认已经是联通的）“
    # 所以只需要对图中每个1看看它四个方向能不能作为算周长的一条边即可
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        directions=[(-1,0),(0,1),(1,0),(0,-1)] #也是看四个方向是否能构成岛屿边界
        m,n = len(grid), len(grid[0])
        length=0
        for i in range(m):
            for j in range(n):
                if grid[i][j]==1:
                    for d in directions:
                        new_i, new_j = i+d[0], j+d[1]
                        if new_i<0 or new_j<0 or (0<= new_i <m and 0<= new_j <n and grid[new_i][new_j])==0:
                            length+=1                        
        return length


    # ### BFS
    # def islandPerimeter(self, grid: List[List[int]]) -> int:
    #     if not grid:
    #         return 0
    #     m,n = len(grid), len(grid[0])

    #     directions=[(-1,0),(0,1),(1,0),(0,-1)]
    #     marked=[[False]*n for i in range(m)]

    #     for i in range(m):
    #         for j in range(n):
    #             if not marked[i][j] and grid[i][j]==1:
    #                 next_queue=[(i,j)]
    #                 marked[i][j]=True
    #                 length=0
    #                 while next_queue:
    #                     now=next_queue.pop(0)
    #                     for d in directions:
    #                         new_i, new_j = now[0]+d[0], now[1]+d[1]
    #                         #new_i<0 or new_j<0表示now在边界处，可以算有一个边
    #                         if new_i<0 or new_j<0 or (0<= new_i <m and 0<= new_j <n and grid[new_i][new_j])==0:
    #                             length+=1
    #                         if 0<= new_i <m and 0<= new_j <n and not marked[new_i][new_j] and grid[new_i][new_j]==1:
    #                             next_queue.append((new_i, new_j))
    #                             marked[new_i][new_j]=True
    #                 return length
    #     return 0

547. 朋友圈

'''
”无向图的连通分量个数“
题目给出的矩阵实际上是一个邻接矩阵，因此这个题目就抽象成了已知邻接矩阵，求这个无向图的连通分量个数这样一个问题。
'''
#@lc code=start
class Solution:   
    def findCircleNum(self, M: List[List[int]]) -> int:
        ### 一维DFS
        if not M:
            return 0
        n=len(M)
        marked=[False for _ in range(n)] #对每个人作是否访问过的标记（其中行号和列号都代表一个人）

        def dfs(i): 
            marked[i]=True
            for j in range(n): #对第i个人/行（的朋友圈）进行DFS
                if i != j and not marked[j] and M[i][j]==1:
                    dfs(j) #对与i有关系的j朋友的朋友圈继续进行dfs,可以进行标记的人都算是一个朋友圈的 

        count=0
        for i in range(n): #对每个人/行进行遍历看是否可以进行DFS, 有几个可以进行DFS就有几个朋友圈
            if not marked[i]: #只要没有被标记（没有进入前面人的朋友圈，前面可以进行dfs的人在进行dfs时会影响后面人的标记），就可以进行DFS
                count+=1
                dfs(i)
        return count


        ### 一维BFS
        if not M:
            return 0
        n=len(M)
        marked=[False for _ in range(n)]      

        count=0
        for i in range(n):
            if not marked[i]:
                count+=1 #能进行几个bfs就有几个朋友圈
                queue=[i] #为每个人开始的BFS建一个队列
                marked[i]=True
                while queue:
                    new_i=queue.pop(0)
                    for j in range(n): #遍历队列队头元素new_i那一行
                        if new_i!=j and not marked[j] and M[new_i][j]==1: # new_i!=j是要排除自己（对角线上的元素不用考虑）
                            queue.append(j)
                            marked[j]=True
        return count

2. 树上的DFS

102. 二叉树的层次遍历

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        ### 广度优先遍历BFS： 需要用到辅助队列
        if not root:
            return []

        res=[]
        queue=[root] #记住辅助队列中存放TreeNode
        while queue:
            temp=[] #每次存放树的一层
            #保证每次while循环里queue里只有树中的一层元素
            for _ in range(len(queue)):
                r=queue.pop(0)
                temp.append(r.val)#在弹出的时候加入该层临时temp中
                if r.left: #不为空的时候加入队列
                    queue.append(r.left)
                if r.right:
                    queue.append(r.right)

            res.append(temp)#将该层加入到最终结果res中

        return res


        ### DFS递归实现 
        if not root:
            return []
        res = []
        def dfs(index,r):#每次递归的时候都需要带一个index(表示当前的层数)，如果当前行对应的list不存在，就加入一个空list进去。
            # 假设res是[ [1],[2,3] ]， index是3，就再插入一个空list放到res中
            if len(res)<index:
                res.append([])
            #  将当前节点的值加入到res中，index代表当前层，假设index是3，节点值是99
            # res是[ [1],[2,3] [4] ]，加入后res就变为 [ [1],[2,3] [4,99] ]
            res[index-1].append(r.val)
            # 递归的处理左子树，右子树，同时将层数index+1
            if r.left:
                dfs(index+1,r.left)
            if r.right:
                dfs(index+1,r.right)
        dfs(1,root)
        return res

层次遍历的DFS遍历示意图

2. 拓扑排序之课程表系列

207. 课程表

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        ### 因为本题中课程也就是结点都是用数字编号代表的，所以一维入度表的index和二维邻接表的行index都可以代表一门课
        ins = [0 for _ in range(numCourses)] #入度表，index表示一门课，对应的值是其入度值
        outs = [[] for _ in range(numCourses)] #二维邻接表，每个list是以当前index表示的结点为起点所连的其他结点
        ### 利用 prerequisites 中各个边（cur <-- pre）的信息初始化上面两个表
        for cur, pre in prerequisites:
            ins[cur] += 1
            outs[pre].append(cur)
        ### 把所有入度为0（没有前驱结点/先修课程）的课程结点加入到queue中
        queue = collections.deque()
        for course, in_value in enumerate(ins):
            if not in_value: queue.append(course) ### 注意：把入度为0的index也就是课程加入到queue中
        ### 利用queue依次删除（让以该节点为前驱的结点的入度-1）那些没有前驱结点的结点, 若删到最后numCourses为0，都删完了说明该有向图中不存在环，可以完成所有课程
        while queue:
            start = queue.popleft()
            numCourses -= 1
            for end in outs[start]:
                ins[end] -= 1
                ### 如果当前end结点入度中减去了start导致的入度后，当前入度为0，则end结点也变成了没有前驱结点的结点，需要加入到queue中
                if not ins[end]: queue.append(end)
        return not numCourses

210. 求课程顺序

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        ### 只是把207中的queue每次弹出的结果保存起来就好了 
        ins = [0 for _ in range(numCourses)]
        outs = [[] for _ in range(numCourses)]

        for cur, pre in prerequisites:
            ins[cur] += 1
            outs[pre].append(cur)
        
        queue = collections.deque()
        for course, in_value in enumerate(ins):
            if not in_value: queue.append(course)

        res = [] ###
        while queue:
            start = queue.popleft()
            numCourses -= 1
            res.append(start) ###
            for end in outs[start]:
                ins[end] -= 1
                if not ins[end]: queue.append(end)
        return res if not numCourses else [] ###