图论是数学的一个分支，主要研究图的结构、性质以及图的应用。图论中的图是由顶点（也称为节点）和边组成的抽象结构，可以用来表示现实世界中的各种关系和结构，如社交网络、交通网络、电路网络等。以下是图论的一些基本概念：1. **顶点（Vertex）**：图中的基本
摘要：图论 (1) 岛屿数量 """ 给你一个由 '1'（陆地）和 '0&#39
图论
(1) 岛屿数量
"""
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
"""
res = 0
def dfs(grid, i, j):
if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] == "0":
return
grid[i][j] = "0"
dfs(grid, i-1, j)
dfs(grid, i+1, j)
dfs(grid, i, j-1)
dfs(grid, i, j+1)
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == "1":
dfs(grid, i, j)
res += 1
return res
(2) 腐烂的橘子
"""
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
- 值 0 代表空单元格；
- 值 1 代表新鲜橘子；
- 值 2 代表腐烂的橘子。
每分钟，腐烂的橘子周围 4 个方向上相邻 的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
"""
row = len(grid)
col = len(grid[0])
rotten = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 2}
fresh = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 1}
time = 0
while fresh:
if not rotten: return -1
rotten = {(i + di, j + dj) for i, j in rotten for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)] if (i + di, j + dj) in fresh}
fresh -= rotten
time += 1
return time
(3) 课程表
"""
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi]，表示如果要学习课程 ai 则 必须 先学习课程 bi。例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
"""
indegrees = [0 for _ in range(numCourses)]
adjacency = [[] for _ in range(numCourses)]
queue = collections.deque()
for cur, pre in prerequisites:
indegrees[cur] += 1
adjacency[pre].append(cur)
for i in range(len(indegrees)):
if not indegrees[i]:
queue.append(i)
while queue:
pre = queue.popleft()
numCourses -= 1
for cur in adjacency[pre]:
indegrees[cur] -= 1
if not indegrees[cur]:
queue.append(cur)
return not numCourses
(4) 前缀树
"""
请你实现 Trie 类：
- Trie() 初始化前缀树对象。
- void insert(String word) 向前缀树中插入字符串 word。
- boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false。
- boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix，返回 true ；否则，返回 false。
"""
class Trie:
def __init__(self):
self.children = {}
self.is_end_of_word = False
def insert(self, word: str) -> None:
current = self
for char in word:
if char not in current.children:
current.children[char] = Trie()
current = current.children[char]
current.is_end_of_word = True
def search(self, word: str) -> bool:
current = self
for char in word:
if char not in current.children:
return False
current = current.children[char]
return current.is_end_of_word
def startsWith(self, prefix: str) -> bool:
current = self
for char in prefix:
if char not in current.children:
return False
current = current.children[char]
return True
回溯
(1) 全排列
"""
给定一个不含重复数字的数组 nums，返回其所有可能的全排列。你可以按任意顺序返回答案。
"""
res = []
def dfs(x):
if x == len(nums):
res.append(nums.copy())
return
for i in range(x, len(nums)):
nums[i], nums[x] = nums[x], nums[i]
dfs(x+1)
nums[i], nums[x] = nums[x], nums[i]
dfs(0)
return res
(2) 子集
"""
给你一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。
"""
res = []
path = []
def dfs(i):
if i == len(nums):
res.append(path.copy())
return
# 不选 nums[i]
dfs(i+1)
# 选 nums[i]
path.append(nums[i])
dfs(i+1)
path.pop()
dfs(0)
return res
(3) 电话号码的字母组合
"""
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
"""
MAPPING = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
res = []
path = []
def dfs(i):
if i == len(digits):
res.append("".join(path.copy()))
return
for x in MAPPING[int(digits[i])]:
path.append(x)
dfs(i+1)
path.pop()
dfs(0)
return res
(4) 组合总和
"""
给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合 ，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
"""
res = []
path = []
def dfs(i, left):
if left == 0:
res.append(path.copy())
return
if i == len(candidates) or left < 0:
return
# 不选
dfs(i+1, left)
# 选
path.append(candidates[i])
dfs(i, left-candidates[i])
path.pop()
dfs(0, target)
return res
(5) 括号生成
"""
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
"""
res = []
path = []
def dfs(i, left, right):
if i == 2*n:
res.append("".join(path.copy()))
return
if right < left:
return
if 0 < left <= n:
path.append("(")
dfs(i+1, left-1, right)
path.pop()
if 0 < right <= n:
path.append(")")
dfs(i+1, left, right-1)
path.pop()
dfs(0, n, n)
return res
(6) 单词搜索
"""
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
"""
m = len(board)
n = len(board[0])
visited = [[0 for _ in range(n)] for _ in range(m)]
def dfs(k, i, j):
if not 0 <= i < m or not 0 <= j < n or board[i][j] != word[k] or visited[i][j]:
return False
if k == len(word)-1:
return True
visited[i][j] = 1
if dfs(k+1, i+1, j) or dfs(k+1, i-1, j) or dfs(k+1, i, j+1) or dfs(k+1, i, j-1):
return True
visited[i][j] = 0
for i in range(m):
for j in range(n):
if dfs(0, i, j):
return True
return False
(7) 分割回文串
"""
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
"""
res = []
path = []
def dfs(i):
if i == len(s):
res.append(path.copy())
return
for j in range(i, len(s)):
t = s[i:j+1]
if t == t[::-1]:
path.append(t)
dfs(j+1)
path.pop()
dfs(0)
return res
(8) n 皇后问题
"""
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
"""
res = []
path = []
exist = []
def valid(i, j):
for x, y in exist:
if j == y or i+j == x+y or i-j == x-y:
return False
return True
def dfs(i):
if i == n:
res.append(path.copy())
return
for j in range(n):
if valid(i, j):
path.append("".join(['Q' if k == j else '.' for k in range(n)]))
exist.append((i, j))
dfs(i+1)
path.pop()
exist.pop()
dfs(0)
return res