单选题
适中
#19743
对连通无向图执行Kruskal算法。已按边权从小到大依次扫描到某条边e=(u,v)。此时在已经构建的部分MST结构中, (u,v)已在同一连通块内。关于边 的处…
对连通无向图执行Kruskal算法。已按边权从小到大依次扫描到某条边e=(u,v)。此时在已经构建的部分MST结构中, (u,v)已在同一连通块内。关于边 的处理,下列说法正确的是( )。
答案与解析
正确答案:B
解析
Kruskal算法基于边权递增顺序处理边,维护当前选中边构成的森林连通性。每条边处理时需判断其两端顶点是否已存在于同一连通块中。该判断通过并查集等数据结构实现,用于检测加入该边是否会形成环。若两端已在同一连通块内,则该边连接的是同一树内两节点。此时该边可被跳过而不立即加入MST结构。算法继续处理下一条边,后续选择仅依赖未处理的边及其权值顺序。已舍弃的边不会影响后续连通性决策,且不触发回溯机制。边的选取与否完全由当前连通状态和边权顺序决定。