深度优先搜索(DFS)

深度优先搜索(DFS)

深度优先搜索,是从起点v0开始,优先往下v1,v2级搜索下去,同样的举例子:

假设有一个这样的文件夹:

里面有着大大小小的文件以及子文件夹,当你需要搜索一个名字为:仙士可.txt的文件时

你需要怎么遍历呢?

首先,我们把/text下的文件及文件夹称作为v0级文件,以此同理,vo级文件夹下的子文件为v1级...v2

广度优先搜索

在广度优先搜索中,我们是这样遍历的:

先遍历v0的所有文件,存储v1的所有需要遍历的文件夹,再遍历v1的所有文件,同时存储v2的文件夹....

深度优先搜索

深度优先搜索的做法为:

1:保存v0级别的所有文件,1,2,3,4,5,测试文本01.txt,测试文本02.txt,

2:先遍历v0级别的目录1,判断为目录,而不是目标文件

3:保存目录1的v1级子文件 11,12,测试文本11.txt

4:继续保存目录11的子文件 111,测试文本111.txt,

5:继续遍历目录11的第一个子文件夹111,由于111文件夹没有内容,则返回

6:继续遍历目录11的第二个文本测试文本111.txt,由于不匹配 仙士可.txt,则返回

7:目录11遍历完毕,返回

8:继续遍历12文件夹

...

深度优先搜索的做法是,从一个起点开始,一直遍历下去,直到满足条件或者没有数据遍历,则开始第二个点开始遍历,直到最后一个vo级数据遍历完毕

广度优先搜索和深度优先搜索

现在我们已经知道了广度优先搜索以及深度优先搜索的搜索步骤,

那么,它们之间的优缺点有哪些呢?什么时候要用广度优先什么时候要用深度优先呢?

我们根据它们之间的特性进行分析:

内存消耗

当子节点过多的时候,广度优先搜索需要保存更多的子节点数据以便于下次遍历,而深度优先搜索只需要保存当前节点的上下级节点

例如,

当v0级文件夹有10个文件夹,同时每个子文件夹也有10个文件夹(空文件夹)的时候.

广度优先在遍历到第20次的时候(vo级和v1级都遍历完),这时候的队列已经保存了10*10-20(已经遍历过)需要遍历的数据

而深度优先在这个时候,只保存了10(v0级文件夹)+0(v1级第一个已经遍历完毕)+10(v1级第二个遍历的栈)

深度优先由于只需要记录当前遍历的上下级节点,并且每次遍历完可以及时回收,所以内存消耗较少

广度优先由于需要记录上级所有节点以及当前的下级节点,在子节点数过多的时候,需要消耗更多的内存

最优解

之前的那个搜索文件的需求,我们稍微改一改:

一个文件夹里面有n级的子文件夹,有着5,6个名字为"仙士可.txt"的文件,现在我们需要找到层级最高(离v0最近的)的那个"仙士可.txt"文件

这个时候,该怎么找呢?

深度优先搜索的做法是这样的:

找到该文件之后,记录该文件的层级(假设为v5)以及路径

继续查找,找到之后,如果层级大于v5,则忽略,如果小于v5,则覆盖之前的层级以及路径

...

这样子,我们就可以找到层级最高的"仙士可.txt"

而在广度优先搜索中,我们只需要v0下去逐层查找,找到之后立即返回即可

深度优先搜索可以在消耗少量内存的情况下找到一个解,但这个解并不一定是最优解,如果需要找最优解,需要遍历全部数据,消耗更多的时间

广度优先搜索消耗更多的内存,消耗相对较少的时间,找出的是最优解,

算法实现

深度优先准备工作如下:

1:结果集数组,将匹配正确的结果集数组保存

2:递归函数,栈实现深度搜索

3:创建一个数组,用于记录已经遍历的文件夹(通用写法,当你的v2级文件夹,有一个是v0级的快捷方式的时候,需要判断一下是否已经遍历过了,如果有就不再遍历)

由于深度优先搜索的特性,需要通过一个全局的结果集数组保存结果值,在栈里面判断该次搜索任务是否完成

算法需求拆分:

1:递归函数,foreach当前级别的文件数组的时候,继续调用该函数,去foreach下一个级别的文件数组,直到找到结果集数组或者遍历全部完成

2:获取子级数据 在调用一个文件夹的时候,去获取他的子级并且开始下一次循环

3:根据结果集判断搜索任务是否完成

4:判断任务数据  判断当前数据是否已经遍历过,是否跳过

php实现如下:

<?php
$resultData = [];
$ergodic = [];//通过php的hash数组特性,直接$ergodic[hash(文件夹名)]=1; 进行表示该文件夹名已遍历
$rootPath = '/www/easyswoole/tioncico_demo/test';


search($rootPath,$ergodic,$resultData);

/**
 * search
 * @param     $path  //需要搜索的目录
 * @param     $ergodic //已遍历数据存储
 * @param     $resultData //结果数据存储
 * @param int $level
 * @author Tioncico
 * Time: 11:51
 */
function search($path,&$ergodic,&$resultData,$level=1){

    //判断目录是否已经遍历过
    if (checkTask($ergodic, $path)) {
        return null;
    }
    //标记该目录已经遍历过
    $ergodic[md5($path)] = 1;

    //获取目录的数据
    $fileData = getDirData($path);
    //判断是文件,还是文件夹
    foreach ($fileData as $file) {
        //判断是否完成搜索,在这里,只要$resultData不为空就当成成功搜索
        if (!empty($resultData)){
            break;
        }
        //过滤本级目录以及上级
        if ($file == '.' || $file == '..') {
            continue;
        }
        $filePath = "{$path}/$file";
        echo "当前遍历文件:{$filePath}\n";
        if (is_file($filePath)) {//如果是文件,则处理文件
            //判断文件终止情况
            if (checkFile($filePath)) {
                $resultData[] = $filePath;
                echo "文件搜索成功,路径为:{$filePath}\n";
                return $filePath;
            }
        } elseif (is_dir($filePath)) {//如果是目录,则继续遍历
            search($filePath,$ergodic,$resultData,$level+1);
        } else {
            continue;
        }
    }
    return null;
}


/**
 * 扫描文件夹(获取子级数据)
 * 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);
}

输出:

\

去除终止条件时候的输出:

以广度优先搜索对比:

我的博客即将同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2hrq8tku2rqco