札记之PHP实现图的深度优先遍历(DFS)

基本思想

• 访问顶点v；
• 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
• 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

存储结构

实现方式

邻接表非递归实现

• 根据指定的输入方式，把各节点的关系生成图。
• 深度优先算法：采用栈（后进先出LIFO）的思想，遍历节点时，被遍历的节点出栈，再遍历其子节点，将子节点逐一进栈。

对照上图看栈的变化

邻接表实现

/**
 * 图的深度优先遍历
 * 图的存储结构--邻接表
 */
class Node
{
    public $value = null;
    public $next = [];

    public function __construct($value = null)
    {
        $this->value = $value;
    }
}

class Graph
{
    // 记录节点是否已被遍历
    public $visited = [];
    // 图的邻接表数组
    public $graph = [];

    /**
     * 为顶点添加邻接点
     * @param $vertex 顶点v
     * @param $adjvex 顶点v的邻接点
     */
    public function addVertex($vertex, $adjvex)
    {
        $this->graph[$vertex][] = $adjvex;
    }

    // 将邻接表数组转为邻接链表
    public function buildGraph()
    {
        $result = [];
        $vertices = array_keys($this->graph);

        foreach ($vertices as $vertex) {
            $result[$vertex] = new Node($vertex);
        }
        foreach ($this->graph as $vertex => $adjvex) {
            foreach ($adjvex as $v) {
                if (isset($result[$v]) && is_object($result[$v])) {
                    $result[$vertex]->next[] = $result[$v];
                }
            }
        }
        return $result;
    }

    //递归实现
    public function dfs($v) 
    {
        $this->visited[$v] = 1;
        echo $v . PHP_EOL;
        for ($i = 0; $i < count($this->graph[$v]); $i++) {
            if ($this->visited[$this->graph[$v][$i]] == 0) {
                $this->dfs($this->graph[$v][$i]);
            } else {
                continue;
            }
        }
    }

    //非递归实现
    public function deepFirstSearch($v) 
    {
        // 初始化节点遍历标记
        $vertices = array_keys($this->graph);
        foreach ($vertices as $vertex) {
            $this->visited[$vertex] = 0;
        }
        
        $stack[] = $v;
        while (!empty($stack)) {
            $current = array_pop($stack);
            if ($this->visited[$current->value] == 0) {
                echo $current->value . PHP_EOL;
                $this->visited[$current->value] = 1;
            }
            //遍历节点的next数组，找出所有的子节点
            for ($i = count($current->next) - 1; $i >= 0; $i--) {
                //判断不在栈内，则进栈
                if ($this->visited[$current->next[$i]->value] == 0) {
                    $stack[] = $current->next[$i];
                }
            }
        }
    }
}
$vertices = ['a', 'b', 'c', 'd', 'e', 'f'];
$graph = new Graph($vertices);

$graph->addVertex('a', 'b');
$graph->addVertex('a', 'c');
$graph->addVertex('b', 'a');
$graph->addVertex('b', 'd');
$graph->addVertex('b', 'c');

$graph->addVertex('d', 'b');
$graph->addVertex('d', 'f');
$graph->addVertex('d', 'e');
$graph->addVertex('d', 'c');

$graph->addVertex('f', 'd');

$graph->addVertex('e', 'd');
$graph->addVertex('e', 'c');

$graph->addVertex('c', 'e');
$graph->addVertex('c', 'd');
$graph->addVertex('c', 'b');
$graph->addVertex('c', 'a');

// 递归
$graph->dfs('a');

// 非递归
$data = current($graph->buildGraph());
$graph->deepFirstSearch($data);

结果

a
b
d
f
e
c

邻接矩阵实现

class Graph 
{
    // 存储节点信息
    public $vertices;
    // 存储边信息
    public $arcs;
    // 图的节点数
    public $vexnum;
    // 记录节点是否已被遍历
    public $visited = [];

    // 初始化
    public function __construct($vertices)
    {
        $this->vertices = $vertices;
        $this->vexnum = count($this->vertices);
        for ($i = 0; $i < $this->vexnum; $i++) {
            for ($j = 0; $j < $this->vexnum; $j++) {
                $this->arcs[$i][$j] = 0;
            }
        }
    }

    // 两个顶点间添加边(无向图)
    public function addEdge($a, $b) 
    {
        if ($a == $b) { 
            return;
        }
        $this->arcs[$a][$b] = 1;
        $this->arcs[$b][$a] = 1;
    }

    // 从第i个节点开始深度优先遍历
    public function traverse($i) 
    {
        // 标记第i个节点已遍历
        $this->visited[$i] = 1;
        // 打印当前遍历的节点
        echo $this->vertices[$i] . PHP_EOL;
        // 遍历邻接矩阵中第i个节点的直接联通关系
        for ($j = 0; $j < $this->vexnum ; $j++) {
            // 目标节点与当前节点直接联通，并且该节点还没有被访问，递归
            if ($this->arcs[$i][$j] == 1 && $this->visited[$j] == 0) {
                $this->traverse($j);
            }
        }
    }

    // 递归
    public function dfs() 
    {
        // 初始化节点遍历标记
        for ($i = 0; $i < $this->vexnum; $i++) {
            $this->visited[$i] = 0;
        }
        // 从没有被遍历的节点开始深度遍历
        for ($i = 0; $i < $this->vexnum; $i++) {
            if ($this->visited[$i] == 0) {
                // 若是连通图，只会执行一次
                $this->traverse($i);
            }
        }
    }

    // 非递归
    public function deepFirstSearch() 
    {
        // 初始化节点遍历标记
        for ($i = 0; $i < $this->vexnum; $i++) {
            $this->visited[$i] = 0;
        }
        $stack = [];
        for ($i = 0; $i < $this->vexnum; $i++) {
            if (!$this->visited[$i]) {
                $stack[] = $i;
                while (!empty($stack)) {
                    $current = array_pop($stack);
                    // 如果该节点还没有被遍历，则遍历该节点并将子节点入栈
                    if ($this->visited[$current] == 0) {
                        echo $this->vertices[$current] . PHP_EOL;
                        $this->visited[$current] = 1;
                        // 没遍历的子节点入栈
                        for ($j = $this->vexnum - 1; $j >= 0; $j--) {
                            if ($this->arcs[$current][$j] == 1 && $this->visited[$j] == 0) {
                                $stack[] = $j;
                            }
                        }
                    }
                }
            }
        }
    }
}
$vertices = ['a', 'b', 'd', 'f', 'e', 'c'];
$graph = new Graph($vertices);
$graph->addEdge(0, 1);
$graph->addEdge(0, 2);
$graph->addEdge(1, 0);
$graph->addEdge(1, 3);
$graph->addEdge(1, 2);
$graph->addEdge(2, 4);
$graph->addEdge(2, 3);
$graph->addEdge(2, 1);
$graph->addEdge(2, 0);
$graph->addEdge(3, 1);
$graph->addEdge(3, 5);
$graph->addEdge(3, 4);
$graph->addEdge(3, 2);
$graph->addEdge(4, 3);
$graph->addEdge(4, 2);
$graph->addEdge(5, 3);

$graph->dfs();

结果

a
b
d
f
e
c