广度优先搜索(BFS)
广度优先搜索(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算法 文章中,为了查找效率,使用了 广度优先搜索 ,从起点开始扩散查找,而不是从起点开始一直深入查找
- 点赞
- 收藏
- 关注作者
评论(0)