DFS & BFS
二叉树遍历
- 和二叉树有关的数据结构有Binary Heap和Binary Search Tree
- 我们通常从（二叉）树的最重要的顶点：根节点 开始。
- 如果给定的树不是"rooted"，我们可以选择任何一个顶点并将其指定为根。并让中立向下拉动其余部分之后，我们有一个有根的（向下）树。
- 二叉树的遍历：前序（中左右），中序（左中右），后序（左右中）
一般图 vs 二叉树
在一般图中，我们没有根节点的概念。相反，我们需要选择一个不同的节点作为遍历的起始点，即源点 s 。 我们还有一个节点的 0, 1, ..., k 个邻点，而不仅仅是 ≤ 2。 我们可能（或者实际上很可能）在我们的一般的图具有循环，无论是像 u → v → u 那样的简单的环，还是像 a → b → c → a 这样的不简单的环。 但不用担心，图的遍历是一个具有两种经典算法的简单问题：DFS 和 BFS。
spanning Tree生成树 也就是说，生成树是在不破坏原图（无向连通图）连通性的前提下，选出的一组边，使得：
- 没有环（避免冗余的连接）；
- 能连接所有节点（确保通信/连接性）；
- 边的数量是固定的：对于有
n个顶点的图，生成树总有n-1条边。
DFS
Graph实现方法
def dfs(graph, start, target):
stack = [start] # 用栈来模拟深度优先
while stack:
node = stack.pop() # 每次取栈顶元素
print(f"Visiting: {node}")
if node == target:
print(f"Found {target}!")
return True
# 把相邻节点放进去（注意，这里可以逆序放保证顺序一致）
stack.extend(reversed(graph[node]))
print(f"{target} not found.")
return False
避免循环
DFS的基本形式用一个大小为 V 个顶点的数组 status[u] 来确定两种情况 分别为 u 已经被访问过了 或者没有被访问过。只有当 u 还没有被访问过的时候 DFS才可以访问顶点 u.
记住路径
DFS 用另一个大小为 V 个顶点数组 p[u] 来记住在DFS遍历路径上每一个顶点 u 的 parent/predecessor/previous（父/祖先/前）顶点。
最开始的顶点的祖先也就是 p[s] 被设定为-1也就是说它没有祖先 (因为最低的顶点是顶点0).
时间复杂度
DFS 的时间复杂度是 O(V+E) ，因为：
- 每个节点只访问过一次，因为 DFS 将仅递归地探索节点 u 如果
status[u] = unvisited — O(V) - 每次访问完一个节点，都会探索其所有 k 个邻点，因此在访问所有节点之后，我们已检查了所有 E 边 — （O(E) ，因为i每个节点的邻点总数等于 E）。
- V 表示图中的顶点数（Vertices），用 E 表示图中的边数（Edges）
- ==Adjecent list==保证了时间复杂度, Graph里面有介绍
BFS
想象一下静止的水，然后你扔石头。石头撞击水面的第一个位置是源点的位置，并且随后在水面上的波纹效应类似于 BFS 遍历模式。
实现方法
BFS 从源点 s 开始，但它在更深入之前使用 queue 尽最宽可能地将访问序列排序。
from collections import deque
def bfs(graph, start, target):
queue = deque([start]) # 用队列来模拟广度优先
while queue:
node = queue.popleft() # 每次取队头元素
print(f"Visiting: {node}")
if node == target:
print(f"Found {target}!")
return True
queue.extend(graph[node]) # 把邻居们加到队列尾部
print(f"{target} not found.")
return False
# 测试
bfs(Graph, 'A', 'E')
时间复杂度
BFS的时间复杂度是 O(V+E)，因为:
- 每一个顶点都被访问一次 因为它们只能进入队列一次— O(V)
- 每当一个顶点从队列中出队时，所有它的 k 个邻居都会被探索 所以当所有的顶点都被访问过后，我们一共探索了 E 条路径 — (O(E) 因为每个顶点的邻居总数为 E). 对于DFS来说 O(V+E) 只有在用邻接表时和DFS分析相同
DFS&BFS 应用
可达性检测
测试图中的节点 s 和一个（不同的）节点 t 是否可达，即直接连接（通过一条边）或间接连接（通过简单的非环路径），则可以调用 O(V+E) DFS(s) (或 BFS(s)) 并检查是否 status[t] = visited
显示遍历路径
- 使用 DFS（深度优先搜索） 或 BFS（广度优先搜索） 来遍历一个图。在遍历过程中，每当从某个顶点
u到达一个新顶点v，你就可以记录路径，比如：p[v]=u - 遍历结束后，你想打印从起点到某个目标点 t 的路径。你可以使用一个递归函数来"倒着走"，从
t一步步回溯到起点.(回溯法)
method backtrack(u)
if (u == -1) stop
backtrack(p[u])
output vertex u
假设你从 s = 0 出发，目标是 t = 4。
- 用 DFS 或 BFS 得到前驱数组
p。 - 调用
backtrack(4)，它会打印出路径，比如：0 → 1 → 3 → 4。
分辨/计数/标记 一个无向图的连通分量(CCs)
通过简单地调用 O(V+E) DFS(s) (或 BFS(s)) ，并枚举所有 status[v] = visited 的节点 v，来枚举从无向图中的节点 s 可到达的所有节点。
status[{0,1,2,3,4}] = visited，因此它们都是从节点 0 可到达的节点，即它们形成一个连通分量（CC）。
CC = 0
for all u in V, set status[u] = unvisited
for all u in V
if (status[u] == unvisited)
CC++ // 我们可以用CC计数器的数量来作为CC的标记
DFS(u) // 或者 BFS(u), 来标记它的成员为已访问
output CC // 上面的示例图的答案是3
// CC 0 = {0,1,2,3,4}, CC 1 = {5}, CC 2 = {6,7,8}
探测图是否有圈（cyclic）
为了判断是否有环，我们引入一个变量：status[u]，用于记录每个顶点在 DFS 中的状态。
- 未访问（unvisited）
- 初始状态。DFS 还没有访问过这个节点。
- 探索中（exploring）
- DFS 现在访问到了这个节点，正在递归地探索它的邻居。
- 说明我们正沿着某条路径往下探，当前在处理
u。
- 已探索完（explored）
- 这个节点的所有邻居也都已经被递归访问完了，DFS 已经从它返回了。
- 也就是说，整条路径探索完毕，
u可以"放心退休"了 207-课程表-DFS解法
def has_cycle(V, adj_list):
# 状态数组：0=未访问，1=探索中，2=已探索
status = [0] * V # 初始都未访问
def dfs(u):
status[u] = 1 # 标记为探索中
for v in adj_list[u]:
if status[v] == 1:
# 发现回边，说明有环
return True
elif status[v] == 0: # 只判断了0和1 跳过了完全探索的2
if dfs(v):
return True
status[u] = 2 # 所有邻居都探索完了
return False
# 处理可能不是连通图的情况
for i in range(V):
if status[i] == 0:
if dfs(i):
return True
return False
拓扑排序（只在有向无圈图 DAG中）
什么是拓扑排序
拓扑排序是：对一个有向无环图（DAG）中的所有顶点排序，使得每一条有向边 u → v 中，u 都出现在 v 的前面。 亦可理解为对某点 v 而言，只有当 v 的所有源点均出现了，v 才能出现。
- 如果图表示的是"先做这个，再做那个"的任务依赖关系，
- 那么拓扑排序就是安排任务的一个合法顺序，先做前置任务，再做后续任务。
应用举例
-
课程安排（有前置课程的课程计划）
-
编译依赖（文件 A 依赖于 B，先编译 B）
-
任务调度（某任务必须在另一任务之后）