连通图用深度优先和广度优先算法所得的生成树是否唯一？

Question

对图求深度优先和广度优先应该怎么做?对首个访问的节点是否有要求？感觉图中有多个回路的话结果就可以有不同结果

Answer 1

理论上遍历所得的生成树或序列是不唯一的，算法本身并没有对同等条件下哪个点优先访问做要求。但实际写代码的时候肯定要按某种顺序遍历，通常是从小到大，这时首个访问的点肯定是第一个点，当前点与多个未访问点相连时也是优先访问编号小的点，这样所得的结果就是唯一的了。