一、相关概念
1.有向图：图中边是有方向的
2.无向图：图中边没有方向
3.加权有向图：图中边是有权值的
4.无向图的度：无向图中有几条边连接该节点，该节点就有几度
5.有向图的出度和入度：出度：从该节点出发的边的个数；入度：指向该节点边的个数。
6.连通图：在无向图中，任何两个节点都是可以到达的称之为连通图，如果有节点不能到达其他节 点，则为非连通图
7.强连通图：在有向图中任何两个节点是可以相互到达
8.连通分量：在无向图中的极大连通子图称之为该图的一个连通分量。
9.强连通分量：在有向图中极大强连通子图称之为该图的强连通分量。
10.邻接矩阵：使用二维数组来表示图结构，邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。
11.邻接表：使用 数组 + 链表的方式来表示，邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表。
二、深度优先搜索
递归 DFS
def dfs(node, visited):
if node in visited:
return # 如果已经访问过，直接返回，避免死循环
visited.add(node) # 标记当前节点为已访问
print(node) # 处理当前节点（例如打印）
# 遍历所有邻接节点
for neighbor in graph[node]:
dfs(neighbor, visited) # 递归访问邻接节点
非递归 DFS（使用显式栈）
def dfs_stack(start):
visited = set()
stack = [start] # 初始化栈，将起始节点放入栈中
while stack:
node = stack.pop() # 弹出栈顶元素
if node in visited:
continue # 已访问就跳过
visited.add(node)
print(node) # 处理当前节点
# 将未访问的邻接节点加入栈（注意倒序保证顺序一致）
for neighbor in reversed(graph[node]):
if neighbor not in visited:
stack.append(neighbor)
visited集合必须添加在遍历节点之前或出栈/出队之后DFS 中若涉及回溯（如路径恢复），用
path.append()和path.pop()成对出现避免多次访问同一个节点（循环），用
visited来剪枝非递归 DFS 的
stack.append()顺序要注意（一般用reversed()）
三、广度优先搜索
BFS：
from collections import deque
def bfs(start):
visited = set()
queue = deque([start]) # 初始化队列，将起点入队
visited.add(start) # 标记起点为已访问
while queue:
node = queue.popleft() # 队首出队
print(node) # 处理当前节点
# 遍历当前节点的所有邻接节点
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor) # 标记为已访问
queue.append(neighbor) # 入队以备后续处理
四、所有可达路径（Kamacoder 98）
使用邻接矩阵深搜：
def dfs(graph, x, n, path, result):
# 递归终点：当前节点为终点节点 n，说明找到一条完整路径
if x == n:
result.append(path.copy()) # 添加当前路径的副本到结果集中
return
# 遍历所有可能的下一跳节点
for i in range(1, n + 1):
if graph[x][i] == 1: # 如果存在从 x 到 i 的边
path.append(i) # 将节点 i 加入当前路径
dfs(graph, i, n, path, result) # 递归搜索从 i 开始的路径
path.pop() # 回溯，将 i 从路径中移除
def main():
# 读取节点数量 n 和边数 m
n, m = map(int, input().split())
# 初始化邻接矩阵，graph[i][j] == 1 表示存在一条从 i 到 j 的有向边
graph = [[0] * (n + 1) for _ in range(n + 1)]
# 读取边的信息，构建图
for _ in range(m):
s, t = map(int, input().split())
graph[s][t] = 1 # 表示从 s 到 t 有一条边
result = [] # 用于保存所有从 1 到 n 的路径
dfs(graph, 1, n, [1], result) # 从节点 1 开始 DFS，初始路径为 [1]
# 如果找不到任何路径，输出 -1
if not result:
print(-1)
else:
# 输出所有路径，每条路径占一行，数字之间用空格分隔
for path in result:
print(' '.join(map(str, path)))
if __name__ == "__main__":
main()
使用邻接表深搜：
from collections import defaultdict
result = [] # 用于收集所有符合条件的路径（从1到n）
path = [] # 当前正在探索的路径
def dfs(graph, x, n):
if x == n: # 如果当前节点是目标节点 n
result.append(path.copy()) # 保存当前路径的副本
return
for i in graph[x]: # 遍历当前节点 x 所有可以到达的邻接点 i
path.append(i) # 将 i 添加到当前路径中
dfs(graph, i, n) # 递归搜索从 i 出发的路径
path.pop() # 回溯：撤销 i，尝试其他路径分支
def main():
# 读取输入的节点数量 n 和边数 m
n, m = map(int, input().split())
graph = defaultdict(list) # 使用邻接表表示图结构
for _ in range(m):
s, t = map(int, input().split())
graph[s].append(t) # 在图中添加一条有向边 s -> t
path.append(1) # 所有路径都是从节点 1 出发
dfs(graph, 1, n) # 启动 DFS 搜索路径
# 输出结果
if not result:
print(-1) # 没有找到任何从 1 到 n 的路径
else:
for pa in result:
print(' '.join(map(str, pa))) # 输出每条路径
if __name__ == "__main__":
main()