代码随想录第40天：图论1
一、相关概念
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 dequedef 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 和边数 mn, 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]# 如果找不到任何路径，输出 -1if not result:print(-1)else:# 输出所有路径，每条路径占一行，数字之间用空格分隔for path in result:print(' '.join(map(str, path)))if __name__ == "__main__":main()
使用邻接表深搜：
from collections import defaultdictresult = [] # 用于收集所有符合条件的路径（从1到n）
path = [] # 当前正在探索的路径def dfs(graph, x, n):if x == n: # 如果当前节点是目标节点 nresult.append(path.copy()) # 保存当前路径的副本returnfor i in graph[x]: # 遍历当前节点 x 所有可以到达的邻接点 ipath.append(i) # 将 i 添加到当前路径中dfs(graph, i, n) # 递归搜索从 i 出发的路径path.pop() # 回溯：撤销 i，尝试其他路径分支def main():# 读取输入的节点数量 n 和边数 mn, m = map(int, input().split())graph = defaultdict(list) # 使用邻接表表示图结构for _ in range(m):s, t = map(int, input().split())graph[s].append(t) # 在图中添加一条有向边 s -> tpath.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()