广度优先搜索(BFS)
广度优先搜索,顾名思义,就是在搜索的时候,广度优先,优先遍历当前的子节点,进行搜索.比如:
有一个文件夹/test
里面有着大大小小的文件以及子文件夹,当你需要搜索一个名字为:仙士可.txt的文件时
你需要怎么遍历呢?
首先,我们把/text下的文件及文件夹称作为v0级文件,以此同理,vo级文件夹下的子文件为v1级...v2
1:遍历v0级文件,判断是否有仙士可.txt
2:保存v0级文件夹
3:遍历vo级文件夹的第一个文件夹,获取v1级所有文件,判断
4:保存v1级所有文件夹
5:继续遍历第2步v0级第二个文件夹,获取v1级,判断
6:保存v1级所有文件夹
7:继续遍历第2步v0级第三个文件夹.....
...
8:v0级文件夹遍历完毕,继续遍历第4步获取到的v1级文件夹...
...
在这个过程中,优先遍历上层文件(v0全部遍历完成才会遍历v1)的搜索方法,就叫做广度优先搜索
算法实现
广度优先算法实现具体实现如下:
准备工作:
1:创建一个数组,用于记录已经遍历的文件夹(通用写法,当你的v2级文件夹,有一个是v0级的快捷方式的时候,需要判断一下是否已经遍历过了,如果有就不再遍历)
2:创建一个队列,用于记录需要遍历的文件夹 (队列的特性是先进先出,优先遍历的v0级会全部先出列,然后是v0级的第一个v1,以此类推,)
注意:
记录以及遍历的文件夹是广度优先搜索的通用写法,在这个文件夹遍历的需求中可能看不出作用,这个一般应用于当子级可以链接到上一级的数据的时候才用到,进行判断过滤
算法需求拆分
1:队列, 用于记录需要处理的搜索工作
2:获取子级数据 根据出列的数据,进行获取它的子级数据
3:判断搜索任务 判断这个搜索算法的任务是否完成(例如这里面的是,只要找到了仙士可.txt文件即完成任务,可退出遍历,当然也可以设定任务为遍历全部数据(队列为0时代表遍历完成),用于统计层级数据等需求)
4:判断任务数据 判断当前数据是否已经遍历过,是否跳过
5:子级数据入列 当该子级的文件判断完毕时,需要将子级可以继续遍历的数据入列,等待遍历
php实现如下:
<?php $queue = \[\];//通过数组,数组函数array\_push(入队列),array\_shift(出队列) 实现伪队列 $ergodic = \[\];//通过php的hash数组特性,直接$ergodic\[hash(文件夹名)\]=1; 进行表示该文件夹名已遍历 $rootPath = '/www/easyswoole/tioncico_demo/test'; //顶级目录入列 array_push($queue, $rootPath); while ($path = array_shift($queue)) { //判断目录是否已经遍历过 if (checkTask($ergodic, $path)) { continue; } //标记该目录已经遍历过 $ergodic\[md5($path)\] = 1; //获取目录的数据 $fileData = getDirData($path); //判断是文件,还是文件夹 foreach ($fileData as $file) { //过滤本级目录以及上级 if ($file == '.' || $file == '..') { continue; } $filePath = "{$path}/$file"; echo "当前遍历文件:{$filePath}\\n"; if (is_file($filePath)) {//如果是文件,则处理文件 //判断文件终止情况 if (checkFile($filePath)) { echo "文件搜索成功,路径为:{$filePath}\\n"; break 2; } } elseif (is_dir($filePath)) {//如果是目录,则入队列,继续处理 //入列 pushQueue($queue, $filePath); } else { continue; } } } /** * 扫描文件夹(获取子级数据) * getDirData * @param $path * @return array * @author Tioncico * Time: 11:55 */ function getDirData($path) { //扫描文件夹 $file = scandir($path); return $file; } //判断遍历条件是否完成 function checkFile($data) { if (basename($data) == '仙士可.txt') { return true; } return false; } //判断该任务是否已经遍历过 function checkTask($ergodic, $path) { return isset($ergodic\[md5($path)\]); } //子级数据入队列 function pushQueue(&$queue, $data) { array_push($queue, $data); }
输出:
如果不需要遍历条件,则会遍历所有目录:
其他
在最短路径-Dijkstra算法 文章中,为了查找效率,使用了 广度优先搜索 ,从起点开始扩散查找,而不是从起点开始一直深入查找
