数据结构问题,有关深度优先遍历的,第13小题.我知道abc三个选项不对,但是觉得d也不对.总觉得应该是aedcfb求大神指点.图会画.

来源:学生作业帮助网 编辑:作业帮 时间:2024/11/28 14:08:55
数据结构问题,有关深度优先遍历的,第13小题.我知道abc三个选项不对,但是觉得d也不对.总觉得应该是aedcfb求大神指点.图会画.
xVMSV+̴+UdYZ6,Lwt MNgM'|8`!v2Iɮt&2 }wιךZpOpeu0Akg ԽZKs(Vk>Zcq6X~jdPW LNR% "s8ɚ 7tμ~9 ̃@;ꥱ[ݴXLߡK=\28c{n^tNs@mP!9;`"tÏ=3P'ŧ'$ ˀdpGy{ 6[G+(Jnao7n2@w7pӰxxl~u4alI? ߨ:;]q5M`? zCNN;evx ~l-WpVIm}8X^B΢LAH@u IYvP`iJat\*>챲 ,uMD#&Jh2#Qtڗ#T [C4j)!R(%Guz06"Mf3qr~wTI&Y|zmA'g;KCMl%Izw+PQpc\f".Ɉz]G[i:Lq1o[Met @ilrmEy(ݥ]mx@W㏢±E 4 ^'Kf#P_#m|]VFN*^-0rr}N3C9+Mcl>{ B&bZ..)84^Nпb

数据结构问题,有关深度优先遍历的,第13小题.我知道abc三个选项不对,但是觉得d也不对.总觉得应该是aedcfb求大神指点.图会画.
数据结构问题,有关深度优先遍历的,第13小题.我知道abc三个选项不对,但是觉得d也不对.总觉得应该是aedcfb求大神指点.图会画.

数据结构问题,有关深度优先遍历的,第13小题.我知道abc三个选项不对,但是觉得d也不对.总觉得应该是aedcfb求大神指点.图会画.

你上传的题目看得不是很清,不知道是(e,f)还是(c,f),所以我画了两个图,真的很纠结啊.
PS:图片传正啊,看歪的图要得颈椎病的- -
好了回到正题,ABC三个选项确实都是错的,但D是正确的.至于LZ说的aedcfb是不正确的,不管是哪个图这个答案都是不正确的.深度优先遍历就是只要有路就选一条一直往下走,如果没有后继节点或者继续走回到之前走过的节点就返回上一个节点再看有没有路径走.首先解释D选项aedfcb为什么是正确的,a->e->d->f题主应该都能理解,现在开始分左右图说:
1、左图来看到了f只有d与e与f相连,而d,e都已经走过了,于是返回d,到了d碰到与f一样的情况,于是返回e,此时与e相连的有b和a,a已经走过,所以选b.b只与a,e相连且这两个节点都走过,于是返回e,e返回a,与a相连的还有个没有被访问过的c,所以最后一个节点是c.如果左图是对的,则D也不对,正确的序列应该是aedfbc.
2、右图来看,到了f后f还有一个尚未被访问过的节点c,所以会访问f的下一个节点c,到了c后与c相连的节点均已经访问过,于是返回f,同理返回d,e.到了e,还有一个与e相连的尚未被访问的节点b,于是访问.所以D的序列aedfcb是正确的.
之所以说题主的aedcfb是错误的是因为a->e->d到了d之后,应该继续访问与d相连的且并未访问过的节点,节点c不符合这个条件,符合这个条件的只有f.一条路径只要能继续走就走下去,这就是“深度优先”为什么叫深度优先.
深度优先的正确序列不只一个,最主要是要理解这个算法.不知道这么回答题主可满意,大半年没有看书了有些东西不是很肯定,若有疑问可以一起继续探讨