实现图的广度优先搜索算法需使用的辅助数据结构为( ) A. 栈 B.队列 C. 二叉树 麻烦解释一下,谢谢

还有深度优先,也顺便解释一下

第1个回答  推荐于2018-06-02
广度优先用队列,深度优先用栈。简单说明如下:
广度优先:当一个节点被加入队列时,要标记为已遍历,遍历过程中,对于队列第一个元素,遍历其所有能够能一步达到的节点,如果是标记未遍历的,将其加入队列,从第一个元素出发所有能一步直接达到的节点遍历结束后将这个元素出列。
深度优先:当遍历到某个节点A时,如果是标记未遍历,将其入栈,遍历它能够一步直接达到的节点,如果是标记未遍历,将其入栈且标记为已遍历,然后对其进行类似A的操作,否则找能够一步直接达到的节点进行类似操作。直到所有能够一步直接达到的节点都已遍历,将A出栈。
这里使用“能够能一步达到的节点”而非“与其相邻的节点”是考虑到有向图因素。
具体可以找个图,然后使用广度和深度算法搜索一遍,每步自己手工修改队列和栈就明白怎么回事了。本回答被提问者和网友采纳
相似回答