宽度优先搜索代码java,广度优先搜索代码

宽度优先搜索算法(pascal)

以走迷宫为例,就是一群人一起出发,然后遇到叉路口就分开走,只要有一个人走出就把所有人带走

目前创新互联已为上千多家的企业提供了网站建设、域名、雅安服务器托管网站托管运营、企业网站设计、南明网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。

宽度优先搜索的伪代码实现

下面的宽度优先搜索过程BFS假定输入图G=(V,E)采用邻接表表示,对于图中的每个顶点还采用了几种附加的数据结构,对每个顶点u∈V,其色彩存储于变量color[u]中,结点u的父母存于变量π[u]中。如果u没有父母(例如u=s或u还没有被检索到),则 π[u]=NIL,由算法算出的源点s和顶点u之间的距离存于变量d[u]中,算法中使用了一个先进先出队列Q来存放灰色节点集合。其中head[Q]表示队列Q的队头元素,Enqueue(Q,v)表示将元素v入队, Dequeue(Q)表示对头元素出队;Adj[u]表示图中和u相邻的节点集合。

BFS(G,S)

foreachu∈V[G]-{s}

do

color[u]←White;

d[u]←∞;

π[u]←NIL;

end;

color[s]←Gray;

d[s]←0;

π[s]←NIL;

Q←{s}

while(Q≠φ)

do

u←head[Q];

for each v∈Adj[u]

do

if(color[v]=White)

then

color[v]←Gray;

d[v]←d[u]+1;

π[v]←u;

Enqueue(Q,v);

end;

Dequeue(Q);

color[u]←Black;

end;

end;

end;

图1展示了用BFS在例图上的搜索过程。黑色边是由BFS产生的树 枝。每个节点u内的值为d[u],图中所示的队列Q是第9-18行while循环中每次迭代起始时的队列。队列中每个结点下面是该结点与源结点的距离。

图1 BFS在一个无向图上的执行过程

过程BFS按如下方式执行,第1-4行置每个结点为白色,置d[u]为无穷大,每个结点的父母置为NIL,第5行置源结点S为灰色,即意味着过程开始时源结点已被发现。第6行初始化d[s]为0,第7行置源结点的父母结点为NIL,第8行初始化队列0,使其仅含源结点s,以后Q队列中仅包含灰色结点的集合。

程序的主循环在9-18行中,只要队列Q中还有灰色结点,即那些已被发现但还没有完全搜索其邻接表的结点,循环将一直进行下去。第10行确定队列头的灰色结点为u。第11-16行的循环考察u的邻接表中的每一个顶点v。如果v是白色结点,那么该结点还没有被发现过,算法通过执行第13-16行发现该结点。首先它被置为灰色,距离d[v]置为d[u]+1,而后u被记为该节点的父母,最后它被放在队列Q的队尾。当结点u的邻接表中的所有结点都被检索后,第17 -18行使u弹出队列并置成黑色。

7.3实现宽度优先搜索

在单词关系图建立完成以后,需要继续在图中寻找词梯问题的最短序列,需要用到“宽度优先搜索Breadth First Search”算法对单词关系图进行搜索

BFS是搜索图的最简单算法之一,也是其它一些重要的图算法的基础给定图G,以及开始搜索的起始顶点s。BFS搜索所有从s可到达顶点的边而且在达到更远的距离k+1的顶点之前,BFS会找到全部距离为k的顶点可以想象为以s为根,构建一棵树的过程,从顶部向下逐步增加层次宽度优先搜索能保证在增加层次之前,添加了所有兄弟节点到树中。

BFS算法过程

❖为了跟踪顶点的加入过程,并避免重复顶点,要为顶点增加3个属性

1.距离distance:从起始顶点到此顶点路径长度;

2.前驱顶点predecessor:可反向追溯到起点;

3.颜色color:标识了此顶点是尚未发现(白色)、已经发现(灰色)、还是已经完成探索(黑色)

❖还需要用一个队列Queue来对已发现的顶点进行排列

决定下一个要探索的顶点(队首顶点)

❖从起始顶点s开始,作为刚发现的顶点,标注为灰色,距离为0,前驱为None,加入队列,接下来是个循环迭代过程:

从队首取出一个顶点作为当前顶点;遍历当前顶点的邻接顶点,如果是尚未发现的白

色顶点,则将其颜色改为灰色(已发现),距离增加1,前驱顶点为当前顶点,加入到队列中遍历完成后,将当前顶点设置为黑色(已探索过),循环回到步骤1的队首取当前顶点

算法分析

BFS算法主体是两个循环的嵌套

while循环对每个顶点访问一次,所以是O(|V|),而嵌套在while中的for,由于每条边只有在其起始顶点u出队的时候才会被检查一次,而每个顶点最多出队1次,所以边最多被检查1次,一共是O(|E|)综合起来BFS的时间复杂度为O(V+E)

词梯问题还包括两个部分算法

建立BFS树之后,回溯顶点到起始顶点的过程,最多为O(|V|),创建单词关系图也需要时间,最多为O(|V|2)


网页题目:宽度优先搜索代码java,广度优先搜索代码
本文网址:http://scyanting.com/article/hsihpo.html