图的遍历

遍历从一个起点系统访问可达顶点。邻接表适合稀疏图，空间 O(n+m)；邻接矩阵遍历邻居需 O(n)。不连通图要从每个未访问点重新开始。

DFS

深度优先搜索沿一条边尽量深入再回溯，可用于连通块、判环、拓扑排序和 low-link 算法。递归版本简洁，但深链须考虑栈溢出。

void dfs(int u){
  vis[u]=true;
  for(int v:g[u]) if(!vis[v]) dfs(v);
}

BFS

广度优先搜索按距离层次扩展。在无权图中首次访问到 v 时，dist[v]=dist[u]+1 即为最短边数距离；队列保证先处理较近层。

queue<int> q; q.push(s); dist[s]=0;
while(!q.empty()){int u=q.front();q.pop(); for(int v:g[u])
 if(dist[v]==-1) dist[v]=dist[u]+1,q.push(v);}

复杂度

用邻接表时 DFS、BFS 都是 O(n+m) 时间、O(n) 额外空间。遍历无向图时，父子边会被看到两次；有向图的可达性取决于边方向。

整理自 XOJ《遍历》。