PHP 函数中如何使用递归来实现深度优先搜索？-php教程-PHP中文网

PHP 函数中如何使用递归来实现深度优先搜索？

WBOY

发布： 2024-09-02 22:36:04

原创

1616人浏览过

使用 php 函数中的递归实现深度优先搜索 (dfs) 算法。该算法以树或图形的根节点开始，递归地遍历相邻节点，直到达到树的底部或没有更多路径可探索。dfs 的 php 实现：标记节点已访问。迭代节点所有相邻节点。如果相邻节点未访问，则递归调用 dfs 来探索该节点。

PHP 函数中如何使用递归来实现深度优先搜索？

PHP 函数中使用递归实现 DFS (深度优先搜索)

深度优先搜索 (DFS)是一种遍历算法，用于遍历图形或树。此算法使用递归来探索节点的路径，直到到达树的底部或没有更多路径可探索为止。

DFS 的 PHP 实现

立即学习“PHP免费学习笔记（深入）”；

以下是使用 PHP 实现 DFS 的步骤：

<?php
function DFS($node, $visited = [])
{
    // 标记节点已访问
    $visited[] = $node;

    // 迭代节点所有相邻节点
    foreach ($node->neighbors as $neighbor) {
        if (!in_array($neighbor, $visited)) {
            // 递归调用 DFS 来探索相邻节点
            DFS($neighbor, $visited);
        }
    }
}
?>

登录后复制

实战案例

考虑一个以下面的方式组织的图形：

百度文心百中

百度大模型语义搜索体验中心

查看详情

       A
      / \
     B   C
    /   / \
   D   E   F

登录后复制

要执行 DFS，我们将从节点 A 开始。

<?php
// 初始化图中节点
$A = new Node('A');
$B = new Node('B');
$C = new Node('C');
$D = new Node('D');
$E = new Node('E');
$F = new Node('F');

// 连接节点
$A->neighbors = [$B, $C];
$B->neighbors = [$D];
$C->neighbors = [$E, $F];

// 执行 DFS 从节点 A 开始
DFS($A);
?>

登录后复制

执行 DFS 后，访问的节点顺序为：