图的遍历

为了分析和操作图结构，我们常常需要遍历整个图。遍历的目标是在不重不漏的前提下访问图中所有连通的顶点。最基本的两种方法是深度优先搜索（DFS）与广度优先搜索（BFS）。它们分别体现了“深入探索”和“逐层推进”两种基本思想，是后续图算法的基石。

图的深度优先搜索（DFS）

DFS 采用“尽可能向前走”的策略：从起点出发，每次选择尚未访问的邻居继续深入，直到无路可走，再回溯到上一个分叉点继续探索其他邻居。

DFS 能够系统地探索所有可能的路径，可以发现连通性、判断是否有环，甚至为构造拓扑序或生成搜索树做准备。

其实现往往借助递归调用或栈来保存搜索路径。伪代码如下：

python

图 G
def DFS(u): # 访问点 u
  标记 u 为已访问
  for v in u 在 G 中的邻居:
    if v 没有被访问:
    DFS(v) # 递归访问 v

BFS 采用队列来实现“逐层推进”。从起点出发，将其加入队列，每次从队列中取出一个点，访问它的所有未访问邻居，并将这些邻居依次加入队列。这种方式保证了节点按照距离起点的层数依次被访问。伪代码如下：

与 DFS 相比，BFS 更强调“层次性”。在某些问题中，我们不仅希望遍历所有顶点，还希望知道它们距离起点的远近关系，特别是在无权图中，BFS 能够保证第一次到达一个顶点时，路径就是从起点出发的最短路径。

其实现往往借助队列保存待搜索的点。伪代码如下：

python

图 G
def BFS(s): # 从起点 s 出发
  建立队列 q
  标记 s 为已访问并入队
  while q 非空:
    u = q 出队
  for v in u 在 G 中的邻居:
    if v 没有被访问:
    标记 v 为已访问
  q 入队

DFS 和 BFS 一深一广，虽然都是遍历整个图，但是其遍历时加入点的性质不同，分别在不同问题场景中展现出优势。这两种算法会在后续的图论算法中作为重要的基本操作。