广度优先搜索的基本思想

如题所述

广度优先搜索的基本思想具体如下:

一、简述

广度优先搜索BFS(Breadth First Search)也称为宽度优先搜索,它是一种先生成的结点先扩展的策略。

二、具体情况

1、在广度优先搜索算法中,解答树上结点的扩展是按它们在树中的层次进行的。首先生成第一层结点,同时检查目标结点是否在所生成的结点中,如果不在,则将所有的第一层结点逐一扩展,得到第层结点,并检查第二层结点是否包含目标结点,......。

2、对层次为n+1的任一结点进行扩展之前,必须先考虑层次完层次为n的结点的每种可能的状态。因此,对于同一层结点来说,求解问题的价值是相同的,可以按任意顺序来扩展它们。通常采用的原则是先生成的结点先扩展。

3、为了便于进行搜索,要设置一个表存储所有的结点。由于在广度优先搜索算法中,要满足先生成的结点先扩展的原则,所以存储结点的表一般采用队列这种数据结构。

三、程序

1、在编写程序时,可用数组q模拟队列。front和rear分别表示队头指针和队尾指针,初始时front=rear=0。元素x入队操作为q[rear++]=x;元素x出队操作为x=g[front++];广度优先搜索算法的搜索步骤。

2、从队列头取出一个结点,检查它按照扩展规则是否能够扩展,如果能则产生一个新结点;检查新生成的结点,看它是否已在队列中存在,如果新结点已经在队列中出现过,就放弃这个结点,然后回到前一步。

3、否则,如果新结点未曾在队列中出现过,则将它加入到队列尾。检查新结点是否目标结点。如果新结点是目标结点,则搜索成功,程序结束;若新结点不是目标结点,则回到第一步,再从队列头取出结点进行扩展

温馨提示:答案为网友推荐,仅供参考