08-图相关

总结

实践避坑

代码避坑

一维数组初始化

存储数字、字符串、布尔值等不可变对象：
用乘法是安全的，比如 indegrees = [0] * n。

多维数组初始化

内部元素是列表、字典等可变对象
绝不能用乘法，必须用列表推导式 [[0] * m for _ in range(n)] 或 [[] for _ in range(n)]。

前缀树

特征

根节点不存数据，数据/字符都在叶子节点上。
路径即字符串。
is_end：仅节点可作为单词结束，才为True。

优点

前缀匹配：搜索引擎自动补全、拼写检查、输入法等。

bash

			(根节点 root)
       /       \
     'c'       'd'
     /           \
   'a'           'o'
   / \             \
[t]   [r]           [g]
       \
       [t]

题目

01-200-岛屿数量

leetcode-200

输入：二维网格，1代表陆地，0代表水
输出：岛屿数量。岛屿被水包围。岛屿相连：仅水平和竖直方向算连接，斜方向不算。

DFS深度搜索岛屿

核心思想

遍历每一个位置，遇到陆地则：
- 岛屿数量 +1
- 向四周做DFS搜索：把陆地1变成水0，遇到0则停止DFS。

关键实现

定义dfs(i, j)函数：
- 递归终止条件：超出范围或当前[i,j] 已为水
- 当前位置 由陆地1变水0
- 上下左右dfs探索
循环遍历每一个网格：第一次遇到陆地，岛屿数量+1
- 因为dfs后，相邻陆地已经都变成水

python

def numIslands_dfs(self, grid: List[List[str]]) -> int:
    """dfs 搜索岛屿数量，第1次遇到1则数量+1，进行dfs搜索，把相邻的1置为0"""
    if not grid:
        return 0

    # 岛屿数量
    res = 0

    # 地图，m行，n列
    m, n = len(grid), len(grid[0])

    def dfs(i, j):
        """进行dfs搜索，把能接触到的1置为0"""

        # 递归终止条件: 超出范围，或者当前已为水
        if i >= m or j >= n or i < 0 or j < 0 or grid[i][j] == '0':  
            return 

        # 当前位置置为水，岛屿下沉
        grid[i][j] = '0'

        # 上下左右dfs探索
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j-1)
        dfs(i, j+1)

    # 循环遍历每一个网格，第一次遇到陆地，岛屿数量+1，因为dfs后，周围的陆地已经都变成水
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                res += 1
                dfs(i, j)

    return res

02-994-腐烂的橘子

leetcode-994

输入：m*n网格。值含义：0 空单元格，1 新鲜橘子，2 烂橘子。
特点：每分钟，周围四个方向上相邻橘子都会腐烂。
输出：直到单元格没有新鲜橘子所需的最小分钟数。如果不可能 返回-1

队列BFS逐层扩散

逐层扩散腐烂橘子

核心思想

使用队列，记录每个烂橘子的位置 入队；统计新鲜橘子的数量。
队列有值&&有新鲜橘子，执行循环
- 分钟数 +1
- 计算当前队列长度，出队n次
  - 队首出队，向上下左右四个方向扩散。
  - 如果是新鲜橘子，则变烂，加入队列，新鲜橘子-1
最终：若有新鲜橘子，返回-1；若无新鲜橘子，返回已用分钟数。

python

def orangesRotting_bfs(self, grid: List[List[int]]) -> int:
    """使用队列记录烂橘子位置，上下左右四个方向扩展，直到没有新鲜橘子"""

    if not grid:
        return 0

    # 网格范围
    m, n = len(grid), len(grid[0])
    # 队列，烂橘子入队
    queue = deque()
    # 新鲜橘子数量
    fresh_cnt = 0

    # 初始化
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                # 新鲜橘子数量
                fresh_cnt += 1
            elif grid[i][j] == 2:
                # 烂橘子位置
                queue.append((i, j))  

    if fresh_cnt == 0:
        return 0

    minutes = 0

    directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    # 队列有烂橘子 且 有新鲜橘子
    while queue and fresh_cnt > 0:
        minutes += 1

        # 队列出队qsize次
        qsize = len(queue)
        for _ in range(qsize):  
            # 对首出队
            i, j = queue.popleft()  

            # 向上下左右四个方向扩展
            for di, dj in directions:
                # 可扩展位置
                ni, nj = i+di, j+dj
                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1: 
                    # 新鲜橘子-1，新鲜橘子变烂，入队
                    fresh_cnt -= 1
                    grid[ni][nj] = 2
                    queue.append((ni, nj))  
    if fresh_cnt > 0:
        return -1
    return minutes

03-207-课程表

leetcode-207

输入：必须选修n门课程，以及部分课程的前置依赖。如[[0,1]]，学课程0，需先学课程1
输出：能否完成所有课程的学习，True/False

有向图是否存在环

无环：找到合理学习顺序。
有环： $0 \leftrightarrow 1$ ， [[1,0], [0,1]]，无法完成所有课程学习。

入度BFS拓扑排序(卡恩算法)

入度BFS拓扑排序

统计入度和邻接表
- 入度：指向节点(课程)边的数量。某课程入度为k，则说明需先修k门课程。
- 邻接表：学完当前课程后，后续可以学习哪些课程。
初始化队列：把入度为0的课程，放入队列
BFS 拓扑排序
- 队首出队：从队列弹出1门课程，已修课程+1
- 遍历该课程后续邻接课程：
  - 入度-1
  - 若某课程入度=0，则加入队列
结果判断：队列为空时，已修课程 == 全部课程 ?。

代码避坑

一维数组初始化

存储数字、字符串、布尔值等不可变对象：用乘法是安全的
如 indegrees = [0] * n。

多维数组初始化

存储是列表、字典等可变对象，不能用乘法，必须使用列表推导式
[[0] * m for _ in range(n)] 或 [[] for _ in range(n)]

python

def canFinish_degree_bfs(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
    """入度+邻接表，先放入度为0的节点，再依次出队，邻接节点入度减1，入度为0，则入队。队空后，判断完成课程数。
    """
    n = numCourses

    # 1. 初始化入度数组和邻接表
    # indegress[i] 课程i 还有多少先修课没上
    indegrees = [0] * n
    # adjacency[i] 课程i完成后，可解锁哪些后续课程
    adjacency = [[] for _ in range(n) ]

    # 2. 初始化图结构 [a, b] 表示学习课程a，得先学课程b。b -> a 右边
    for cur, pre in prerequisites:
        indegrees[cur] += 1
        adjacency[pre].append(cur) 

    # 3. 初始化队列，入度为0的课程先入
    queue = deque()
    for i in range(n):
        if indegrees[i] == 0:
            queue.append(i) 

    # 4. BFS 队列遍历，出入度为0的节点
    count = 0  # 已完成课程数
    while queue:
        # 当前课程出队
        cur = queue.popleft()
        count += 1

        # 当前节点的邻接表遍历，更新后续课程
        for next in adjacency[cur]:
            # 入度
            indegrees[next] -= 1
            if indegrees[next] == 0:  
                # 入队
                queue.append(next)  

    # 5. 队列已为空，检查完成课程数是否等于全部课程
    if count == numCourses:
        return True

    return False

04-208-实现Trie前缀树

leetcode-208

实现前缀树的：初始化、插入字符串、搜索字符串、前缀判断。

TrieNode和Trie实现

TrieNode 节点

children={}：key是ch字符，value是TrieNode
is_end: 若节点为插入单词末尾字符，则is_end=True；用于判断单词是否存在

Trie 树

init方法：初始化root节点
插入单词：node=root，遍历字符ch
- 若ch不存在：则插入节点，node往后移。
- 末尾node.is_end=True
搜索单词：node=root，遍历字符ch
- 若ch不存在，则单词不存在
- 最后判断末尾node.is_end
判断前缀：同搜索单词，区别为不用看node.is_end。

TrieNode 节点

python

class TrieNode:

  def __init__(self):
      # key: ch, value: TrieNode
      self.children = {}
      # 是否是结束节点
      self.is_end = False

Trie 树

python

class Trie:

  def __init__(self):
      # 根节点
      self.root = TrieNode()


  def insert(self, word: str) -> None:
      """ 向前缀数中插入world 字符串 """
      node = self.root

      for ch in word:
          if ch not in node.children:
              # 插入节点
              node.children[ch] = TrieNode()
          else:
              pass
          # node 往下走，切换到当前ch的node
          node = node.children[ch]
      # 该节点可结束，是一个完整单词
      node.is_end = True
      return


  def search(self, word: str) -> bool:
      """ 判断word是否在树中 """
      node = self.root

      for ch in word:
          if ch not in node.children:
              return False
          node = node.children[ch]
      # 必须走到结尾，在该节点可结束，才代表找到了这个词。
      return node.is_end

  def startsWith(self, prefix: str) -> bool:
      node = self.root

      for ch in prefix:
          if ch not in node.children:
              return False
          node = node.children[ch]
      return True

总结 ​

实践避坑 ​

前缀树 ​

题目 ​

01-200-岛屿数量 ​

DFS深度搜索岛屿 ​

02-994-腐烂的橘子 ​

队列BFS逐层扩散 ​

03-207-课程表 ​

入度BFS拓扑排序(卡恩算法) ​

04-208-实现Trie前缀树 ​

TrieNode和Trie实现 ​

总结

实践避坑

前缀树

题目

01-200-岛屿数量

DFS深度搜索岛屿

02-994-腐烂的橘子

队列BFS逐层扩散

03-207-课程表

入度BFS拓扑排序(卡恩算法)

04-208-实现Trie前缀树

TrieNode和Trie实现