关于广度优先搜索(BFS),以下描述哪个是正确的?
答案解析
核心考点:广度优先搜索(BFS)的实现方式和特点。
解题思路:BFS使用队列进行遍历,是一种非递归的层次遍历方式。
选项A:BFS使用队列而不是栈来实现节点访问,栈常用于深度优先搜索(DFS),这是对BFS实现机制的错误理解,属于干扰项。问题是混淆了BFS和DFS。
选项B:BFS是一种非递归的遍历方式,通过队列实现,不使用递归,这是对BFS实现方式的错误理解。问题是错误理解BFS的实现方式。
选项C:BFS会先访问一个顶点的所有邻接点,然后才访问这些邻接点的邻接点,这是BFS的核心特点,是正确答案的依据。
选项D:BFS虽然可以遍历整个图,但它不是专门用于检测环的算法,发现环通常采用其他方法,如深度优先搜索(DFS)结合回边判断,这是对BFS功能的错误认识,属于干扰项。问题是高估了BFS的功能。
易错点提醒:需要区分BFS和DFS的实现方式和特点,BFS是使用队列的非递��层次遍历,主要用于访问所有可达节点。
正确答案:C