PHP如何高效查找双端关联数组中两节点的所有路径？

嘿，这个问题用图论的思路就能高效解决！先把你的数组转换成有向图的邻接表，再用深度优先搜索（DFS）遍历所有可能路径，处理800个子数组的规模完全没问题。下面是具体的实现方案：

1. 构建邻接表：把原始数组里的side1作为起点、side2作为终点，整理成「每个节点对应其直接可达节点」的结构——这一步是效率的关键，避免每次找相邻节点都遍历整个大数组。
2. DFS遍历路径：从起点出发，递归探索所有未访问过的节点，走到终点就记录当前路径，同时标记已访问节点防止循环（比如A→B→A的无限循环）。

假设你的$arrayx是类的成员变量，我们可以这样实现findAllPaths函数：

class PathFinder {
    private $arrayx;
    private $graph = [];

    public function __construct($arrayx) {
        $this->arrayx = $arrayx;
        // 提前构建邻接表，只初始化一次
        $this->buildAdjacencyGraph();
    }

    private function buildAdjacencyGraph() {
        foreach ($this->arrayx as $edge) {
            $from = $edge['side1'];
            $to = $edge['side2'];
            
            // 初始化节点的邻接列表
            if (!isset($this->graph[$from])) {
                $this->graph[$from] = [];
            }
            // 添加直接可达节点，同时去重避免重复路径
            if (!in_array($to, $this->graph[$from])) {
                $this->graph[$from][] = $to;
            }

            // 如果是无向图（side1和side2可互相通行），取消下面注释
            // if (!isset($this->graph[$to])) {
            //     $this->graph[$to] = [];
            // }
            // if (!in_array($from, $this->graph[$to])) {
            //     $this->graph[$to][] = $from;
            // }
        }
    }

    public function findAllPaths($from, $to) {
        $paths = [];
        // 初始路径为起点，已访问集合标记起点
        $this->dfs($from, $to, [$from], array_flip([$from]), $paths);
        return $paths;
    }

    private function dfs($current, $target, $currentPath, $visited, &$paths) {
        // 到达终点，记录路径
        if ($current === $target) {
            $paths[] = $currentPath;
            return;
        }

        // 当前节点没有后续节点，直接返回
        if (!isset($this->graph[$current])) {
            return;
        }

        // 遍历所有直接可达节点
        foreach ($this->graph[$current] as $nextNode) {
            // 未访问过的节点才继续探索
            if (!isset($visited[$nextNode])) {
                $newPath = $currentPath;
                $newPath[] = $nextNode;
                $newVisited = $visited;
                $newVisited[$nextNode] = true;
                
                $this->dfs($nextNode, $target, $newPath, $newVisited, $paths);
            }
        }
    }
}

// 使用示例
// $arrayx = [
//     ["side1" => "XTSWS", "side2" => "WRXXC", "value" => 1],
//     ["side1" => "XTSWS", "side2" => "TXXBD", "value" => 2],
//     ["side1" => "TXXBD", "side2" => "WRXXC", "value" => 3],
// ];
// $finder = new PathFinder($arrayx);
// $paths = $finder->findAllPaths("XTSWS", "WRXXC");
// print_r($paths);
// 输出结果：
// Array
// (
//     [0] => Array([0] => XTSWS, [1] => WRXXC)
//     [1] => Array([0] => XTSWS, [1] => TXXBD, [2] => WRXXC)
// )

• 邻接表构建：仅需遍历一次原始数组（O(n)时间，n=800），后续查询路径无需再处理原始数组，大幅提升效率。
• DFS遍历：时间复杂度取决于路径数量，只要图中没有大量循环节点，800条边的规模完全能轻松处理。如果担心递归栈溢出（比如超长路径），可以把DFS改成迭代版本，用栈模拟递归过程。
• 额外优化：如果需要同时获取路径对应的value，可以把邻接表改成存储节点+value的关联数组，比如$this->graph[$from][] = ['node' => $to, 'value' => $edge['value']];，遍历的时候就能把value也加入路径结果。

内容的提问来源于stack exchange，提问作者user2984982