广度优先搜索(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条评论
  • 本站由白俊遥博客程序搭建
    © 2017-1-17 php20.cn 版权所有 ICP证:闽ICP备17001387号
  • 联系邮箱:1067197739@qq.com