GESP 八级 · GESP 202503 C++ 八级第 24 题

判断题 · 答案 A · 考点：图论算法、搜索

题目

判断无向图中是否有环，可以通过广度优先搜索实现。

答案：A

图论算法搜索

BFS 使用队列，按层次逐层遍历，适合求最短路径（边权为1时）。核心：标记已访问，避免重复入队。

BFS 入队后立即标记已访问，防止重复入队。队列为空时搜索结束。注意区分树的BFS（无需visited标记）和图的BFS。

【考点】图论｜广度优先搜索｜环的判断

GESP 八级《算法与数据结构》模块「图算法」章节。命题人卡住的是「环检测只能靠 DFS 或并查集」的思维定式，其实 BFS 同样能判环——只要在有向图里遇到已访问的非父节点，在无向图里遇到已访问的任意节点（除父节点）即可。

第 13 题· NOIP 2015 提高组初赛试题 · 答案 D看解析 →
第 28 题· NOIP 2015 提高组初赛试题 · 答案 v=-1dist[i]<dist[v]dist[v]>dist[i]dist[i]<=dist[v]dist[v]>=dist[i]v=iused[v]=1dist[v]+w[v][i]<dist[i]dist[i]>dist[v]+w[v][i]dist[v]+w[v][i]<=dist[i]dist[i]>=dist[v]+w[v][i]看解析 →
第 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看解析 →
第 13 题· CSP 2019 提高级第一轮 · 答案 B看解析 →

在 OI伴学里做这道题

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