回退

11  •  1个月前


代码为何不需要回退 在欧拉路径或欧拉回路的搜索中,由于每条边只被访问一次,因此每个递归调用实际上是在访问一个新的路径段。这段代码并不需要回退(即在找到路径后撤销上一步)主要是因为以下几点:

边的删除: 每次访问一条边时,该边都会被删除(即 map[i][j]-- 和 map[j][i]--),这确保了每条边只被访问一次,避免了重复访问的问题。

递归的自然回退: 当一个节点的所有邻边都被访问完之后,递归调用自然会回退到上一个节点。因为递归函数 find 在调用时已经对边进行标记(即删除),所以不会再次访问已删除的边。

路径记录: 在递归调用的最后,会将当前节点记录到路径数组 lu 中 (lu[++js] = i;)。这种方式确保了路径是按照从终点回到起点的顺序记录的,符合欧拉路径的逆序输出要求。

奇点的处理: 起点选择是从奇点(度数为奇数的点)开始的,这是构造欧拉路径的一个重要特性,因为欧拉路径必须从一个奇点开始,到另一个奇点结束。如果没有奇点,说明是欧拉回路,可以从任意点开始。


评论:

请先登录,才能进行评论