用于检测构成路径的节点顺序的算法需求

嘿，这个需求我之前做类似链式结构处理时碰到过，核心就是把这些零散的节点串成一条条完整的链对吧？结合你给出的规则（每个节点最多被一个其他节点指向，dest_id可以为null），咱们可以用下面这个高效的方法来实现：

核心思路 #

因为不存在多个节点指向同一目标，所以整个结构其实是多条独立的单向链表，我们只需要找到每条链表的起点，然后顺着dest_id遍历到终点（dest_id为null），就能得到完整的路径顺序了。具体分三步：

1. 建立快速查找索引：把所有节点用id作为键存到一个关联数组里，这样可以O(1)时间找到任意id对应的节点，避免反复遍历原数组浪费时间。
2. 定位所有链的起点：遍历所有节点，找出那些没有被任何其他节点的dest_id指向的节点——这些就是每条链的第一个节点（因为如果有节点指向它，那它就不是起点了）。
3. 遍历生成路径：对每个起点，顺着dest_id依次往下找，直到碰到dest_id为null的节点，把路径上的节点id（或者整个节点）按顺序收集起来。

PHP代码实现 #

下面是针对你给出的数组格式写的具体代码，注释很详细，你可以直接用：

<?php
$nodes = [
    ['id' => 1, 'dest_id' => 2],
    ['id' => 2, 'dest_id' => 3],
    ['id' => 3, 'dest_id' => null],
    ['id' => 4, 'dest_id' => 5],
    ['id' => 5, 'dest_id' => null],
    ['id' => 6, 'dest_id' => null] // 测试单个节点的情况
];

// 第一步：建立id到节点的映射，方便快速查找
$nodeMap = [];
foreach ($nodes as $node) {
    $nodeMap[$node['id']] = $node;
}

// 第二步：找出所有链的起点
$destIds = array_column($nodes, 'dest_id'); // 收集所有dest_id的值
$startNodes = [];
foreach ($nodes as $node) {
    // 如果当前节点的id不在所有dest_id里，说明它没有前驱，是起点
    if (!in_array($node['id'], $destIds)) {
        $startNodes[] = $node;
    }
}

// 第三步：遍历每个起点生成路径
$paths = [];
foreach ($startNodes as $startNode) {
    $currentPath = [];
    $currentNode = $startNode;
    
    while ($currentNode !== null) {
        $currentPath[] = $currentNode['id']; // 这里可以换成$currentNode保存整个节点
        $nextId = $currentNode['dest_id'];
        $currentNode = $nextId ? $nodeMap[$nextId] : null;
    }
    
    $paths[] = $currentPath;
}

// 输出结果
print_r($paths);
?>

运行这段代码后，输出的$paths就是所有完整的路径数组：

Array
(
    [0] => Array
        (
            [0] => 1
            [1] => 2
            [2] => 3
        )

    [1] => Array
        (
            [0] => 4
            [1] => 5
        )

    [2] => Array
        (
            [0] => 6
        )
)

补充说明 #

• 时间复杂度是O(n)，因为每个节点只被遍历了几次，非常高效，适合处理大规模的节点数组。
• 如果需要保存整个节点而不是仅仅id，只需要把$currentPath[] = $currentNode['id'];改成$currentPath[] = $currentNode;就行。
• 对于dest_id为null的单个节点，代码也能正确识别为独立路径，不会遗漏。

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