深度优先搜索DFS的非递归算法——PHP实现

概念

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

——维基百科

正文

递归实现树的DFS非常简单，其实非递归与递归的算法没有本质差别，只是递归算法是高级语言底层实现堆栈，而非递归的算法就是自己管理一个堆栈来模拟这个过程，如果脑海中对递归的调用栈有一个清晰的掌握。相信不难写出这个算法。

非递归的优点也体现在对栈的掌控，由于递归过程中的堆栈很难做查询和控制（比如保存附加信息和控制深度），所以非递归的优点包括以下：

• 可以随时回溯反查整个栈的数据。
• 也可以控制栈里面只保存一些我们必要的信息，优化内存。
• 通过控制栈的长度来控制遍历树的最大深度，避免因为树过深导致递归过程中的栈溢出。

本例以DOM树解析为应用场景，因为只是演示算法，故没有引入XML解析库，只是手动构建一个DOM树做遍历算法。在运行过程中可以打开$stack->debug(); 查看栈的数据，任何一个节点在进栈的时候栈内所有数据就是他的所有上级节点，如果想要知道该节点具有哪些样式只需要把所有上级节点的样式合并覆盖即可。

本例运行结果是输出这个树的后根遍历结果。如果要输出先根遍历可以在push的地方输出。但是算法中有一个push是在循环外的，所以需要在两个地方输出。如果想避免冗余，可以给DOM树的根节点上方再加一个无意义的节点即可忽略处理循环外的push。

<?php

/**
 * 节点类，可以是标签节点或文本节点
 */
class node{
    const  TYPE_TAG = 0;  //标签节点
    const  TYPE_TEXT = 1; //文本节点

    private $type;
    private $content;
    private $tag;

    private $children = array();
    private $currentChild = 0;  

    /**
     * 构造函数
     * @param [type] $type    节点类型
     * @param string $tag     标签类型时指定是什么标签
     * @param string $content 指定文本
     */
    function __construct($type, $tag="", $content=""){
        $this->type = $type;
        $this->tag = $tag;
        $this->content = $content;
    }
    
    function getNextChild(){
        if($this->currentChild >= count($this->children)){
            return false;
        }
        return $this->children[$this->currentChild++];
    }

    function pushChild($node){
        array_push($this->children, $node);
        return $this;
    }

    //打印节点
    function content(){
        if($this->type == self::TYPE_TAG){
            return sprintf("<%s>", $this->tag);
        }
        return $this->content;
    }
}

/**
 * 栈
 */
class stack{
    private $_stack = array();

    function notEmpty(){
        return !empty($this->_stack);
    }

    function push($node){
        array_push($this->_stack, $node);
    }

    function pop(){
        return array_pop($this->_stack);
    }

    function top(){
        return end($this->_stack);
    }

    function debug(){
        echo "stack:";
        foreach ($this->_stack as $key => $value) {
            echo $value->content();
        }
        echo "\n";
    }
}

/**
 * 深度优先遍历
 * @param [node] $root 传入根节点
 */
function DFS(node $root){
    $stack = new stack();
    $stack->push($root);
    while($stack->notEmpty()){
        // $stack->debug();
        $top = $stack->top();
        $child = $top->getNextChild();
        if(!empty($child)){
            $stack->push($child);
        }else{
            $pop = $stack->pop();
            echo $pop->content()."\n";
        }
    }
}


// 生成测试数据
// <h4>你<a>好<strong>世界</strong>!</a></h4>

$h4 = new node(node::TYPE_TAG, 'h4');
$a = new node(node::TYPE_TAG, 'a');
$br = new node(node::TYPE_TAG, 'br');
$strong = new node(node::TYPE_TAG, 'strong');

$ni = new node(node::TYPE_TEXT, '', '你');
$hao = new node(node::TYPE_TEXT, '', '好');
$shijie = new node(node::TYPE_TEXT, '', '世界');
$sym = new node(node::TYPE_TEXT, '', '!');

$h4->pushChild($ni)->pushChild($a);
$a->pushChild($hao)->pushChild($br)->pushChild($strong)->pushChild($sym);
$strong->pushChild($shijie);


DFS($h4);