GESP 八级 · GESP 202406 C++ 八级第 4 题

选择题 · 答案 C · 考点：图的遍历、算法

题目

有 $V$ 个顶点、$E$ 条边的图的深度优先搜索遍历时间复杂度为（）。

答案：C

图的遍历算法

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】图的遍历｜时间复杂度｜DFS 算法

GESP 八级《算法与数据结构》中"图的遍历"专项。命题人放这道题，就是卡住"只记树遍历 O(V) 和图遍历 O(V+E) 的区别"这一认知断层——多数考生把 DFS 想成树的递归，忘了图还要走边。

第 18 题· NOIP 2013 提高组初赛试题 · 答案 CD看解析 →
第 28 题· NOIP 2016 提高组初赛试题 · 答案 dist[1]=0dist[x]+weight[j]<dist[point[j]]weight[j]+dist[x]<dist[point[j]]dist[point[j]]>weight[j]+dist[x]dist[point[j]]>dist[x]+weight[j]visit[x]=0weight[j]+dist[x]==dist[point[j]]dist[x]+weight[j]==dist[point[j]]visit[point[j]]=1看解析 →
第 28 题· NOIP 2017 提高组初赛试题 · 答案 degree[b]=degree[b]+1degree[b]++++degree[b]degree[i]==0!degree[i]degree[i]=degree[i]-1degree[i]----degree[i]head=head+1head++++headans<len[a]len[a]>ans看解析 →
第 12 题· CSP 2023 提高级第一轮 · 答案 C看解析 →
第 9 题· GESP 七级样题（C++ 组） · 答案 C看解析 →

在 OI伴学里做这道题

登录后可计时作答、查看完整六段式解析，并按你的错题自动生成同类练习。